#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll INF = 1e18;
vector<vector<pair<ll,ll> > > adjlist;
vector<ll> safe;
vector<ll> shortest;
vector<ll> secshortest;
ll n;
void dijkstra(){
priority_queue<pair<ll,ll>,vector<pair<ll,ll> >,greater<pair<ll,ll> > > pq;
for (ll i : safe){
pq.push(make_pair(0,i));
}
while (pq.size()>0){
auto f = pq.top();
pq.pop();
if (f.first>secshortest[f.second]){
continue;
}
//cout<<"process "<<f.second<<endl;
for (auto i : adjlist[f.second]){
if (secshortest[i.second]>secshortest[f.second]+i.first){
if (secshortest[f.second]+i.first<=shortest[i.second]){
secshortest[i.second]=shortest[i.second];
shortest[i.second]=secshortest[f.second]+i.first;
} else {
secshortest[i.second]=secshortest[f.second]+i.first;
}
pq.push(make_pair(secshortest[i.second],i.second));
}
}
/*for (ll i : shortest){
cout<<(i==INF?-1:i)<<" ";
}cout<<endl;
for (ll i : secshortest){
cout<<(i==INF?-1:i)<<" ";
}cout<<endl;
cout<<"==="<<endl;*/
}
for (ll i : shortest){
assert(i>=0);
}
for (ll i : secshortest){
assert(i>=0);
}
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
n=N;
adjlist.resize(n);
safe.resize(K);
shortest.resize(n,INF);
secshortest.resize(n,INF);
for (int i = 0; i<M; i++){
adjlist[R[i][0]].push_back(make_pair(L[i],R[i][1]));
adjlist[R[i][1]].push_back(make_pair(L[i],R[i][0]));
}
for (int i = 0; i<K; i++){
safe[i]=P[i];
shortest[P[i]]=0;
secshortest[P[i]]=0;
}
dijkstra();
return secshortest[0];
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
3 ms |
504 KB |
Output is correct |
| 5 |
Correct |
3 ms |
504 KB |
Output is correct |
| 6 |
Correct |
3 ms |
504 KB |
Output is correct |
| 7 |
Correct |
3 ms |
504 KB |
Output is correct |
| 8 |
Correct |
3 ms |
504 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
3 ms |
504 KB |
Output is correct |
| 5 |
Correct |
3 ms |
504 KB |
Output is correct |
| 6 |
Correct |
3 ms |
504 KB |
Output is correct |
| 7 |
Correct |
3 ms |
504 KB |
Output is correct |
| 8 |
Correct |
3 ms |
504 KB |
Output is correct |
| 9 |
Correct |
4 ms |
632 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| 11 |
Correct |
3 ms |
504 KB |
Output is correct |
| 12 |
Correct |
6 ms |
1016 KB |
Output is correct |
| 13 |
Correct |
6 ms |
1080 KB |
Output is correct |
| 14 |
Correct |
2 ms |
376 KB |
Output is correct |
| 15 |
Correct |
3 ms |
504 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
3 ms |
504 KB |
Output is correct |
| 5 |
Correct |
3 ms |
504 KB |
Output is correct |
| 6 |
Correct |
3 ms |
504 KB |
Output is correct |
| 7 |
Correct |
3 ms |
504 KB |
Output is correct |
| 8 |
Correct |
3 ms |
504 KB |
Output is correct |
| 9 |
Correct |
4 ms |
632 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| 11 |
Correct |
3 ms |
504 KB |
Output is correct |
| 12 |
Correct |
6 ms |
1016 KB |
Output is correct |
| 13 |
Correct |
6 ms |
1080 KB |
Output is correct |
| 14 |
Correct |
2 ms |
376 KB |
Output is correct |
| 15 |
Correct |
3 ms |
504 KB |
Output is correct |
| 16 |
Correct |
713 ms |
67184 KB |
Output is correct |
| 17 |
Correct |
129 ms |
16620 KB |
Output is correct |
| 18 |
Correct |
169 ms |
18932 KB |
Output is correct |
| 19 |
Correct |
843 ms |
77216 KB |
Output is correct |
| 20 |
Correct |
384 ms |
52600 KB |
Output is correct |
| 21 |
Correct |
58 ms |
7416 KB |
Output is correct |
| 22 |
Incorrect |
423 ms |
48968 KB |
Output isn't correct |
