#include "crocodile.h"
#include<bits/stdc++.h>
using namespace std;
#define f(i,a,b) for(int i = a;i < b;i++)
#define ll int
#define pb push_back
#define F first
#define S second
#define ii pair<ll,ll>
vector<vector<ii> >adj;
bool v[100005] = {0};
ll val[100005] = {0};
vector<ll>ex[100005];
int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]){
adj.assign(n+5,vector<ii>());
priority_queue<ii>ek;
f(i,0,n){
ex[i].pb(1e9);
ex[i].pb(1e9);
val[i] = 1e9;
ek.push(ii(-val[i],i));
}
f(i,0,m){
adj[r[i][0]].pb(ii(r[i][1],l[i]));
adj[r[i][1]].pb(ii(r[i][0],l[i]));
}
f(i,0,k){
ll z = p[i];
v[z] = 1;
val[z] = 0;
for(auto x:adj[z]){
if(!v[x.F]){
ex[x.F].pb(val[z] + x.S);
sort(ex[x.F].begin(),ex[x.F].end());
ex[x.F].pop_back();
val[x.F] = ex[x.F][1];
ek.push(ii(-val[x.F],x.F));
}
}
}
while(!ek.empty()){
ii f = ek.top();
ek.pop();
if(v[f.S] || -f.F > val[f.S]){
continue;
}
ll z = f.S;
v[z] = 1;
for(auto x:adj[z]){
if(!v[x.F]){
ex[x.F].pb(val[z] + x.S);
sort(ex[x.F].begin(),ex[x.F].end());
ex[x.F].pop_back();
val[x.F] = ex[x.F][1];
ek.push(ii(-val[x.F],x.F));
}
}
}
return val[0];
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2800 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2772 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2772 KB |
Output is correct |
| 7 |
Correct |
2 ms |
2772 KB |
Output is correct |
| 8 |
Correct |
2 ms |
2772 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2800 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2772 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2772 KB |
Output is correct |
| 7 |
Correct |
2 ms |
2772 KB |
Output is correct |
| 8 |
Correct |
2 ms |
2772 KB |
Output is correct |
| 9 |
Correct |
3 ms |
3028 KB |
Output is correct |
| 10 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 11 |
Correct |
3 ms |
2804 KB |
Output is correct |
| 12 |
Correct |
5 ms |
3284 KB |
Output is correct |
| 13 |
Correct |
4 ms |
3324 KB |
Output is correct |
| 14 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 15 |
Correct |
2 ms |
2772 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2800 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2772 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2772 KB |
Output is correct |
| 7 |
Correct |
2 ms |
2772 KB |
Output is correct |
| 8 |
Correct |
2 ms |
2772 KB |
Output is correct |
| 9 |
Correct |
3 ms |
3028 KB |
Output is correct |
| 10 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 11 |
Correct |
3 ms |
2804 KB |
Output is correct |
| 12 |
Correct |
5 ms |
3284 KB |
Output is correct |
| 13 |
Correct |
4 ms |
3324 KB |
Output is correct |
| 14 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 15 |
Correct |
2 ms |
2772 KB |
Output is correct |
| 16 |
Correct |
481 ms |
66408 KB |
Output is correct |
| 17 |
Correct |
96 ms |
20872 KB |
Output is correct |
| 18 |
Correct |
114 ms |
22456 KB |
Output is correct |
| 19 |
Correct |
621 ms |
72348 KB |
Output is correct |
| 20 |
Correct |
342 ms |
53948 KB |
Output is correct |
| 21 |
Correct |
41 ms |
9688 KB |
Output is correct |
| 22 |
Correct |
348 ms |
48484 KB |
Output is correct |
