#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
vector < pair < int, int > > gr[111111];
long long cnt[111111],min1[111111], min2[111111], Vmin1[111111], Vmin2[111111];
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
for(int i = 0; i < M; i ++ ){
gr[R[i][0]].push_back({L[i], R[i][1]});
gr[R[i][1]].push_back({L[i], R[i][0]});
}
for( int i = 0; i < N; i ++ ){
min1[i] = min2[i] = 1e9;
}
queue < pair < int, int > > q;
for( int i = 0; i < K; i ++ ){
min1[P[i]] = min2[P[i]] = 0;
q.push({0, P[i]});
}
while(!q.empty()){
pair < int, int > pp = q.front(); q.pop();
int c = pp.first, v = pp.second;
if( cnt[v] != c ) continue;
for( auto edge: gr[v] ){
int cost = edge.first, to = edge.second;
if( min1[to] > min2[v]+cost ){
if( Vmin1[to] == v ){
min1[to] = min1[v]+cost;
}else{
min2[to] = min1[to];
Vmin2[to] = Vmin1[to];
min1[to] = min1[v]+cost;
Vmin1[to] = v;
cnt[to]++;
q.push({cnt[to], to});
}
}
else if( min2[to] > min2[v]+cost ){
min2[to] = min2[v] + cost;
Vmin2[to] = v;
cnt[to]++;
q.push({cnt[to], to});
}
}
}
/*
for( int i = 0; i < N; i ++ ){
cout << "min1[" << i <<"]=" << min1[i] << "; min2[" << i << "]="<<min2[i]<<endl;
}
*/
return min2[0];
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
2944 KB |
Output is correct |
| 2 |
Correct |
6 ms |
2944 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
3072 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
2944 KB |
Output is correct |
| 2 |
Correct |
6 ms |
2944 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
3072 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
2944 KB |
Output is correct |
| 2 |
Correct |
6 ms |
2944 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
3072 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
