#include <bits/stdc++.h>
#include "crocodile.h"
using namespace std;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
vector<int> c(N);
for(int i = 0; i < M; i++){
c[R[i][0]]++;
c[R[i][1]]++;
}
//cout << "???" << endl;
for(int i = 0; i < K; i ++){
c[P[i]] += 1e9;
}
//cout << "??" << endl;
vector<pair<int, int>> tree[N];
for(int i = 0; i < M; i ++){
if((c[R[i][0]] == 2 || c[R[i][1]] == 2) && R[i][1] && R[i][0]) continue;
tree[R[i][0]].push_back({R[i][1], L[i]});
tree[R[i][1]].push_back({R[i][0], L[i]});
}
// cout << "???" << endl;
priority_queue<pair<int, int>> que;
for(int i = 0; i < K; i++){
que.push({0, P[i]});
}
vector<int> dist(N, 1e9);
while(!que.empty()){
int a = -que.top().first, b = que.top().second;
//cout << b << endl;
que.pop();
if(dist[b] < a)continue;
dist[b] = a;
for(auto [l, r] : tree[b]){
que.push({-r-a, l});
}
}
for(int i = 0; i < N; i++){
sort(tree[i].begin(), tree[i].end(), [&](auto a, auto b){return dist[a.first] < dist[b.first];});
}
que.push({0, 0});
vector<int> vis(N, false);
while(!que.empty()){
int a = -que.top().first, b = que.top().second;
que.pop();
if(vis[b])continue;
vis[b] = true;
if(!dist[b])return a;
bool block = false;
for(auto [i, j] : tree[b]){
if(block && !vis[i]){
que.push({-j-a, i});
}
if(!vis[i]){
block = true;
}
}
}
}
Compilation message
crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:5:20: warning: control reaches end of non-void function [-Wreturn-type]
5 | vector<int> c(N);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
