#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
typedef vector<ii> vii;
const int MAXN = 111111;
int dist[MAXN], block[MAXN], dist2[MAXN];
vector<vii> linkd;
priority_queue<ii> pq;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
vector<vii>(N).swap( linkd );
memset( dist, -1, sizeof dist );
memset( dist2, -1, sizeof dist2 );
memset( block, -1, sizeof block );
for(int i=0; i<M; i++){
linkd[R[i][0]].push_back( { R[i][1], L[i] } );
linkd[R[i][1]].push_back( { R[i][0], L[i] } );
}
for(int i=0; i<K; i++) pq.push( {0, P[i]} ), dist[P[i]]=0;
while(!pq.empty()){
int here = pq.top().second, d = -pq.top().first; pq.pop();
if( dist[here] < d ) continue;
for( auto it : linkd[here] ){
int there = it.first, co = it.second;
if( dist[there] == -1 || dist[there] > d + co ){
dist[there] = d + co;
block[there] = here;
pq.push( { -d-co, there } );
}
}
}
// for(int i=0; i<N; i++) printf("%d ",block[i]);
for(int i=0; i<K; i++) pq.push( {0, P[i]} ), dist2[P[i]]=0;
while(!pq.empty()){
int here = pq.top().second, d = -pq.top().first; pq.pop();
if( dist2[here] < d ) continue;
for( auto it : linkd[here] ){
int there = it.first, co = it.second;
if( block[there] == here ) continue;
if( dist2[there] == -1 || dist2[there] > d + co ){
dist2[there] = d + co;
pq.push( { -d-co, there } );
}
}
}
return dist2[0];
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
120408 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
120540 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
120408 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
558 ms |
147940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
