#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]});
}
while (pq.size()) {
pii cur = pq.top(); pq.pop();
if (cur.f != mn[cur.s].s) {continue;}
for (pii qwerty : adj[cur.s]) {
int 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 mn[0].s << '\n';
return ans;
}
/*
int main() {
int n, m, k; cin >> n >> m >> k;
int r[m][2],l[m],p[k];
F0R(i,m) {cin >> r[i][0]>>r[i][1]>>l[i];}
F0R(i,k) {cin >> p[i];}
ll x = travel_plan(n,m,r,l,k,p);
cout<<ans;
}*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4440 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 |
4444 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 |
4444 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4440 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 |
4444 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 |
4444 KB |
Output is correct |
| 9 |
Correct |
2 ms |
4696 KB |
Output is correct |
| 10 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 11 |
Correct |
1 ms |
4696 KB |
Output is correct |
| 12 |
Correct |
3 ms |
4956 KB |
Output is correct |
| 13 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 14 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 15 |
Correct |
1 ms |
4444 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4440 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 |
4444 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 |
4444 KB |
Output is correct |
| 9 |
Correct |
2 ms |
4696 KB |
Output is correct |
| 10 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 11 |
Correct |
1 ms |
4696 KB |
Output is correct |
| 12 |
Correct |
3 ms |
4956 KB |
Output is correct |
| 13 |
Correct |
2 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 |
248 ms |
66076 KB |
Output is correct |
| 17 |
Correct |
47 ms |
16212 KB |
Output is correct |
| 18 |
Correct |
60 ms |
18260 KB |
Output is correct |
| 19 |
Correct |
342 ms |
75456 KB |
Output is correct |
| 20 |
Correct |
170 ms |
53164 KB |
Output is correct |
| 21 |
Correct |
22 ms |
9820 KB |
Output is correct |
| 22 |
Incorrect |
192 ms |
50000 KB |
Output isn't correct |
| 23 |
Halted |
0 ms |
0 KB |
- |
