#include "crocodile.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
#include <utility>
using namespace std;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
vector<vector<pair<int, long long> > > adjacent (N, vector<pair<int, long long> >());
for (int i = 0; i < M; i++){
int s = R[i][0];
int e = R[i][1];
long long d = L[i];
adjacent[s].push_back(make_pair(e, d));
adjacent[e].push_back(make_pair(s, d));
}
vector<long long> max_escape (N, 1000000001);
for (int i = 0; i < K; i++){
max_escape[P[i]] = 0;
}
vector<long long> current_best_escape (N, 1000000001);
vector<long long> current_second_best_escape (N, 1000000001);
priority_queue<pair<int, long long> > to_visit;
for (int i = 0; i < K; i++){
int c_vertex = P[i];
for (int j = 0; j < adjacent[c_vertex].size(); j++){
int new_vertex = adjacent[c_vertex][j].first;
long long escape_length = adjacent[c_vertex][j].second;
if (escape_length <= current_best_escape[new_vertex]){
current_second_best_escape[new_vertex] = current_best_escape[new_vertex];
current_best_escape[new_vertex] = escape_length;
to_visit.push(make_pair(-current_second_best_escape[new_vertex], new_vertex));
} else{
if (escape_length <= current_second_best_escape[new_vertex]){
current_second_best_escape[new_vertex] = escape_length;
}
to_visit.push(make_pair(-current_second_best_escape[new_vertex], new_vertex));
}
}
}
while (max_escape[0] == 1000000001){
pair<long long, int> current_vertex_pair = to_visit.top();
to_visit.pop();
int c_vertex = current_vertex_pair.second;
long long d = -current_vertex_pair.first;
max_escape[c_vertex] = d;
//cout << c_vertex << ' ' << d << endl;
if (max_escape[c_vertex] != 1000000001){
for (int j = 0; j < adjacent[c_vertex].size(); j++){
int new_vertex = adjacent[c_vertex][j].first;
long long escape_length = adjacent[c_vertex][j].second + d;
if (escape_length <= current_best_escape[new_vertex]){
current_second_best_escape[new_vertex] = current_best_escape[new_vertex];
current_best_escape[new_vertex] = escape_length;
to_visit.push(make_pair(-current_second_best_escape[new_vertex], new_vertex));
} else{
if (escape_length <= current_second_best_escape[new_vertex]){
current_second_best_escape[new_vertex] = escape_length;
to_visit.push(make_pair(-current_second_best_escape[new_vertex], new_vertex));
}
}
}
}
}
return max_escape[0];
}
Compilation message
crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:43:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < adjacent[c_vertex].size(); j++){
~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
crocodile.cpp:75:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < adjacent[c_vertex].size(); j++){
~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
