#include <bits/stdc++.h>
#include "crocodile.h"
using namespace std;
struct Chamber{
int cost, id, from;
Chamber(int from, int id, int cost){
this -> from = from;
this -> id = id;
this -> cost = cost;
}
bool operator<(const Chamber& rhs) const {
return cost > rhs.cost;
}
};
struct Path{
int to, cost;
Path(int to, int cost){
this -> to = to;
this -> cost = cost;
}
};
priority_queue<Chamber> pq;
vector<Path> p[100001];
int block[100001];
int ans[100001];
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
for(int i = 0; i < M ; i++){
p[R[i][0]].push_back(Path(R[i][1], L[i]));
p[R[i][1]].push_back(Path(R[i][0], L[i]));
}
memset(ans, -1, sizeof(ans));
for(int i = 0; i < K; i++){
pq.push(Chamber(-1, P[i], 0));
}
int v;
while(!pq.empty()){
v = pq.top().id;
if(ans[v] != -1){
pq.pop();
continue;
}
ans[v] = pq.top().cost;
block[v] = pq.top().from;
for(auto x : p[v]){
if(ans[x.to] != -1) continue;
pq.push(Chamber(v, x.to, ans[v] + x.cost));
}
}
memset(ans, -1, sizeof(ans));
pq.push(Chamber(0, 0, 0));
while(!pq.empty()){
v = pq.top().id;
if(ans[v] != -1){
pq.pop();
continue;
}
ans[v] = pq.top().cost;
if(block[v] == -1){
return ans[v];
}
for(auto x : p[v]){
if(x.to == block[v]) continue;
if(ans[x.to] != -1) continue;
pq.push(Chamber(0, x.to, ans[v] + x.cost));
}
}
}
/*
#define MAX_N 50000
#define MAX_M 10000000
static int N, M;
static int R[MAX_M][2];
static int L[MAX_M];
static int K;
static int P[MAX_N];
static int solution;
inline
void my_assert(int e) {if (!e) abort();}
void read_input()
{
int i;
my_assert(3==scanf("%d %d %d",&N,&M,&K));
for(i=0; i<M; i++)
my_assert(3==scanf("%d %d %d",&R[i][0],&R[i][1],&L[i]));
for(i=0; i<K; i++)
my_assert(1==scanf("%d",&P[i]));
my_assert(1==scanf("%d",&solution));
}
int main()
{
int ans;
read_input();
ans = travel_plan(N,M,R,L,K,P);
if(ans==solution)
printf("Correct.\n");
else
printf("Incorrect. Returned %d, Expected %d.\n",ans,solution);
return 0;
}*/
Compilation message
crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:74:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
3068 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
3068 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
3068 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
