#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<ll,ll>
#define f first
#define s second
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
ll ans;
ll travel_plan(int n, int m, int r[][2], int l[], int k, int p[]) {
ios::sync_with_stdio(false); cin.tie(0);
vector<vector<pii>> adj(n);
F0R(i,m) {
adj[r[i][0]].pb({r[i][1],l[i]});
adj[r[i][1]].pb({r[i][0],l[i]});
}
vector<pii> mn(n,{LLONG_MAX,LLONG_MAX});
priority_queue<pii,vector<pii>,greater<pii>> pq;
F0R(i,k) {
mn[p[i]] = {0,0};
pq.push({0,p[i]});
}
vector<bool> vis(n,false);
while (pq.size()) {
pii cur = pq.top(); pq.pop();
if (vis[cur.s]) {continue;}
vis[cur.s] = true;
/*
if (cur.f != mn[cur.s].s) {continue;} This line may run twice if the two minimums are the same.
Meaning that one of its children may be updated twice from the same node,
which means there are two directed edges connecting the same pair of nodes,
which doesn't follow the constraints of the escape plan.
*/
for (pii qwerty : adj[cur.s]) {
ll cand = qwerty.s+cur.f, x = qwerty.f;
if (cand < mn[x].s) {
if (cand <= mn[x].f) {
mn[x].s = mn[x].f; mn[x].f = cand;
} else {mn[x].s = cand;}
if (mn[x].s!=LLONG_MAX) {pq.push({mn[x].s,x});}
}
}
}
ans = mn[0].s;
return ans;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
604 KB |
Output is correct |
| 5 |
Correct |
1 ms |
604 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
604 KB |
Output is correct |
| 8 |
Correct |
1 ms |
604 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
604 KB |
Output is correct |
| 5 |
Correct |
1 ms |
604 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
604 KB |
Output is correct |
| 8 |
Correct |
1 ms |
604 KB |
Output is correct |
| 9 |
Correct |
1 ms |
860 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
1 ms |
604 KB |
Output is correct |
| 12 |
Correct |
2 ms |
888 KB |
Output is correct |
| 13 |
Correct |
2 ms |
1116 KB |
Output is correct |
| 14 |
Correct |
0 ms |
348 KB |
Output is correct |
| 15 |
Correct |
1 ms |
464 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
604 KB |
Output is correct |
| 5 |
Correct |
1 ms |
604 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
604 KB |
Output is correct |
| 8 |
Correct |
1 ms |
604 KB |
Output is correct |
| 9 |
Correct |
1 ms |
860 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
1 ms |
604 KB |
Output is correct |
| 12 |
Correct |
2 ms |
888 KB |
Output is correct |
| 13 |
Correct |
2 ms |
1116 KB |
Output is correct |
| 14 |
Correct |
0 ms |
348 KB |
Output is correct |
| 15 |
Correct |
1 ms |
464 KB |
Output is correct |
| 16 |
Correct |
269 ms |
65572 KB |
Output is correct |
| 17 |
Correct |
44 ms |
14416 KB |
Output is correct |
| 18 |
Correct |
60 ms |
16720 KB |
Output is correct |
| 19 |
Correct |
327 ms |
72872 KB |
Output is correct |
| 20 |
Correct |
182 ms |
52564 KB |
Output is correct |
| 21 |
Correct |
24 ms |
6760 KB |
Output is correct |
| 22 |
Correct |
200 ms |
48472 KB |
Output is correct |
