#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
vector<vector<pair<long long,long long>>>adj(N);
for (long long 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]});
}
const long long maxn = 1e9;
vector<vector<long long>>dist(N,vector<long long>(2,maxn));
priority_queue<pair<long long,long long>>q;
for (long long i = 0;i<K;++i){
q.push({0,P[i]});
dist[P[i]][0] = 0;
dist[P[i]][1] = 0;
}
while(!q.empty()){
auto u = q.top();
q.pop();
if (dist[u.second][1] < -u.first)continue;
for (auto x:adj[u.second]){
if (dist[x.first][0] > -u.first + x.second){
if (dist[x.first][1] > dist[x.first][0]){
dist[x.first][1] = dist[x.first][0];
q.push({-dist[x.first][1],x.first});
}
dist[x.first][0] = -u.first + x.second;
}
else if (dist[x.first][1] > -u.first + x.second){
dist[x.first][1] = -u.first + x.second;
q.push({-dist[x.first][1],x.first});
}
}
}
return dist[0][1];
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
468 KB |
Output is correct |
| 5 |
Correct |
1 ms |
468 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
468 KB |
Output is correct |
| 8 |
Correct |
2 ms |
468 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
468 KB |
Output is correct |
| 5 |
Correct |
1 ms |
468 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
468 KB |
Output is correct |
| 8 |
Correct |
2 ms |
468 KB |
Output is correct |
| 9 |
Correct |
2 ms |
596 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
2 ms |
468 KB |
Output is correct |
| 12 |
Correct |
4 ms |
960 KB |
Output is correct |
| 13 |
Correct |
3 ms |
1072 KB |
Output is correct |
| 14 |
Correct |
1 ms |
340 KB |
Output is correct |
| 15 |
Correct |
1 ms |
468 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
468 KB |
Output is correct |
| 5 |
Correct |
1 ms |
468 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
468 KB |
Output is correct |
| 8 |
Correct |
2 ms |
468 KB |
Output is correct |
| 9 |
Correct |
2 ms |
596 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
2 ms |
468 KB |
Output is correct |
| 12 |
Correct |
4 ms |
960 KB |
Output is correct |
| 13 |
Correct |
3 ms |
1072 KB |
Output is correct |
| 14 |
Correct |
1 ms |
340 KB |
Output is correct |
| 15 |
Correct |
1 ms |
468 KB |
Output is correct |
| 16 |
Correct |
464 ms |
81924 KB |
Output is correct |
| 17 |
Correct |
84 ms |
21556 KB |
Output is correct |
| 18 |
Correct |
105 ms |
23156 KB |
Output is correct |
| 19 |
Correct |
551 ms |
90132 KB |
Output is correct |
| 20 |
Correct |
279 ms |
65688 KB |
Output is correct |
| 21 |
Correct |
37 ms |
9276 KB |
Output is correct |
| 22 |
Correct |
290 ms |
63520 KB |
Output is correct |
