#include <iostream>
#include <vector>
#include <queue>
#include "crocodile.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<pair<ll,ll>> d(N,{1e9,1e9});
vector<vector<pair<int,int>>> g(N,vector<pair<int,int>>());
for(int i=0;i<M;i++){
g[R[i][0]].push_back({R[i][1],L[i]});
g[R[i][1]].push_back({R[i][0],L[i]});
}
priority_queue<pair<ll,int>> pq;
for(int i=0;i<K;i++){
pq.push({0,P[i]});
d[P[i]].first=d[P[i]].second=0;
}
while(!pq.empty()){
ll dist=-pq.top().first,u=pq.top().second;
pq.pop();
//cout<<u<<' ';
if(dist>d[u].second)continue;
for(auto v:g[u]){
if(dist+v.second<d[v.first].first){
d[v.first].second=d[v.first].first;
d[v.first].first=dist+v.second;
pq.push({-d[v.first].second,v.first});
}
else if(dist+v.second<d[v.first].second){
d[v.first].second=dist+v.second;
pq.push({-d[v.first].second,v.first});
}
}
}
return d[0].second;
}
/*int main(){
int n,m,k;
cin>>n>>m>>k;
int R[m][2],l[m],e[k];
for(int i=0;i<m;i++)cin>>R[i][0]>>R[i][1]>>l[i];
for(int i=0;i<k;i++)cin>>e[i];
cout<<travel_plan(n,m,R,l,k,e);
}*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
3 ms |
596 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
468 KB |
Output is correct |
12 |
Correct |
4 ms |
832 KB |
Output is correct |
13 |
Correct |
3 ms |
852 KB |
Output is correct |
14 |
Correct |
1 ms |
312 KB |
Output is correct |
15 |
Correct |
1 ms |
328 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
3 ms |
596 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
468 KB |
Output is correct |
12 |
Correct |
4 ms |
832 KB |
Output is correct |
13 |
Correct |
3 ms |
852 KB |
Output is correct |
14 |
Correct |
1 ms |
312 KB |
Output is correct |
15 |
Correct |
1 ms |
328 KB |
Output is correct |
16 |
Correct |
428 ms |
59180 KB |
Output is correct |
17 |
Correct |
83 ms |
16708 KB |
Output is correct |
18 |
Correct |
110 ms |
18224 KB |
Output is correct |
19 |
Correct |
526 ms |
68084 KB |
Output is correct |
20 |
Correct |
291 ms |
47056 KB |
Output is correct |
21 |
Correct |
43 ms |
6872 KB |
Output is correct |
22 |
Incorrect |
277 ms |
45252 KB |
Output isn't correct |
23 |
Halted |
0 ms |
0 KB |
- |