#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]) {
vector<vector<pair<ll, ll>>> adj(n);
for (ll i = 0; i < m; ++i) {
adj[r[i][0]].push_back({r[i][1], l[i]});
adj[r[i][1]].push_back({r[i][0], l[i]});
}
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
vector<priority_queue<ll>> best2(n);
for (ll i = 0; i < k; ++i) {
pq.push({0, p[i]});
best2[p[i]].push(0);
best2[p[i]].push(0);
}
while (!pq.empty()) {
pair<ll, ll> state = pq.top();
pq.pop();
if (state.first > best2[state.second].top()) continue;
if (!state.second) {
return state.first;
}
for (pair<ll, ll>& edge : adj[state.second]) {
if (best2[edge.first].size() < 2) {
best2[edge.first].push(state.first + edge.second);
if (best2[edge.first].size() == 2) pq.push({best2[edge.first].top(), edge.first});
} else if (state.first + edge.second < best2[edge.first].top()) {
best2[edge.first].pop();
best2[edge.first].push(state.first + edge.second);
pq.push({best2[edge.first].top(), edge.first});
}
}
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4700 KB |
Output is correct |
| 5 |
Correct |
1 ms |
4700 KB |
Output is correct |
| 6 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 7 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 8 |
Correct |
1 ms |
4700 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4700 KB |
Output is correct |
| 5 |
Correct |
1 ms |
4700 KB |
Output is correct |
| 6 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 7 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 8 |
Correct |
1 ms |
4700 KB |
Output is correct |
| 9 |
Correct |
3 ms |
4696 KB |
Output is correct |
| 10 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 11 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 12 |
Correct |
3 ms |
5052 KB |
Output is correct |
| 13 |
Correct |
3 ms |
4956 KB |
Output is correct |
| 14 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 15 |
Correct |
1 ms |
4444 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4700 KB |
Output is correct |
| 5 |
Correct |
1 ms |
4700 KB |
Output is correct |
| 6 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 7 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 8 |
Correct |
1 ms |
4700 KB |
Output is correct |
| 9 |
Correct |
3 ms |
4696 KB |
Output is correct |
| 10 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 11 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 12 |
Correct |
3 ms |
5052 KB |
Output is correct |
| 13 |
Correct |
3 ms |
4956 KB |
Output is correct |
| 14 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 15 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 16 |
Correct |
254 ms |
66504 KB |
Output is correct |
| 17 |
Correct |
51 ms |
20820 KB |
Output is correct |
| 18 |
Correct |
63 ms |
20820 KB |
Output is correct |
| 19 |
Correct |
291 ms |
76744 KB |
Output is correct |
| 20 |
Correct |
178 ms |
53336 KB |
Output is correct |
| 21 |
Correct |
26 ms |
11100 KB |
Output is correct |
| 22 |
Incorrect |
204 ms |
51388 KB |
Output isn't correct |
| 23 |
Halted |
0 ms |
0 KB |
- |
