#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
struct elem{
int x;
int dist1, dist2;
bool operator<(const elem &ot) const{
if(dist2!=ot.dist2) return dist2>ot.dist2;
return dist1>ot.dist1;
}
};
int travel_plan(int n, int m, int r[][2], int l[], int k, int p[])
{
vector<vector<pair<int, int>>> g(n+1);
vector<bool> used(n+1, 0);
vector<int> dist1(n+1, 1e9), dist2(n+1, 1e9);
priority_queue<elem> pq;
for(int i=0;i<m;++i){
g[r[i][0]+1].push_back({r[i][1]+1, l[i]});
g[r[i][1]+1].push_back({r[i][0]+1, l[i]});
}
for(int i=0;i<k;++i){
dist1[p[i]+1]=dist2[p[i]+1]=0;
pq.push({p[i]+1, dist1[p[i]+1], dist2[p[i]+1]});
}
while(!pq.empty()){
elem x=pq.top();
pq.pop();
if(used[x.x]) continue;
used[x.x]=1;
for(auto it:g[x.x]){
elem nx;
nx.x=it.first;
nx.dist1=dist1[it.first];
nx.dist2=dist2[it.first];
int ndist=x.dist2+it.second;
if(ndist<=nx.dist1){
nx.dist2=nx.dist1;
nx.dist1=ndist;
pq.push(nx);
}
else if(ndist<nx.dist2){
nx.dist2=ndist;
pq.push(nx);
}
dist1[nx.x]=nx.dist1;
dist2[nx.x]=nx.dist2;
}
}
return dist2[1];
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Correct |
1 ms |
312 KB |
Output is correct |
| 8 |
Correct |
1 ms |
312 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Correct |
1 ms |
312 KB |
Output is correct |
| 8 |
Correct |
1 ms |
312 KB |
Output is correct |
| 9 |
Correct |
2 ms |
588 KB |
Output is correct |
| 10 |
Correct |
1 ms |
332 KB |
Output is correct |
| 11 |
Correct |
2 ms |
332 KB |
Output is correct |
| 12 |
Correct |
4 ms |
716 KB |
Output is correct |
| 13 |
Correct |
4 ms |
844 KB |
Output is correct |
| 14 |
Correct |
1 ms |
332 KB |
Output is correct |
| 15 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Correct |
1 ms |
312 KB |
Output is correct |
| 8 |
Correct |
1 ms |
312 KB |
Output is correct |
| 9 |
Correct |
2 ms |
588 KB |
Output is correct |
| 10 |
Correct |
1 ms |
332 KB |
Output is correct |
| 11 |
Correct |
2 ms |
332 KB |
Output is correct |
| 12 |
Correct |
4 ms |
716 KB |
Output is correct |
| 13 |
Correct |
4 ms |
844 KB |
Output is correct |
| 14 |
Correct |
1 ms |
332 KB |
Output is correct |
| 15 |
Correct |
1 ms |
332 KB |
Output is correct |
| 16 |
Correct |
512 ms |
55976 KB |
Output is correct |
| 17 |
Correct |
103 ms |
15360 KB |
Output is correct |
| 18 |
Correct |
138 ms |
17024 KB |
Output is correct |
| 19 |
Correct |
643 ms |
63288 KB |
Output is correct |
| 20 |
Correct |
339 ms |
46384 KB |
Output is correct |
| 21 |
Correct |
49 ms |
6536 KB |
Output is correct |
| 22 |
Correct |
348 ms |
42848 KB |
Output is correct |
