#include <bits/stdc++.h>
#include "crocodile.h"
#define vi vector<int>
#define vc vector
#define pi pair<int,int>
using namespace std;
vc<vc<pi>> edg; // Edges, aka the corridors coming out from each room
vc<pi> dis; // The two minimum distances found between 2 nodes. The fastest route will just be used to calculate the second fastest, which is the oke that will be used to obtain the other distances
int fpath = -1e9-7; // Fastest path
int u, c; // Amazing the amount of situations when a node and a cost can be useful
void dijkstra(int p[]){
priority_queue<pi> tv; // To Visit, not TeleVision or To Vandalize
for(int i = 0; i < (sizeof(p)/sizeof(int)); i++){
tv.push({0,p[i]});
dis[p[i]].first = 0;}
while(!tv.empty()){
u = tv.top().second; // The node being explored right now
c = tv.top().first; // The cost to get to u
tv.pop();
if(dis[u].second>c){continue;} // If this path is worse then why bother
if(u == 0){
fpath = max(fpath, c);
continue;}
for(pi p : edg[u]){ // p.first = cost, p.second = node the path leads to
if (p.first + c > dis[p.second].second){ // If this is path you've found is fastest than the second fastest one...
if (p.first + c > dis[p.second].first){ // And than the fastest one...
dis[p.second].second = dis[p.second].first; // Then the previously fastest one becomes the second fastest one...
dis[p.second].first = p.first + c;} // This new path becomes the fastest!
else{ // But if it's not fastest than the fastest one...
dis[p.second].second = p.first + c;}
tv.push({dis[p.second].second, p.second});
}
}
}
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
edg = vc<vc<pi>>(N);
for(int i = 0; i < M; i++){
edg[R[i][0]].push_back({-L[i],R[i][1]});
edg[R[i][1]].push_back({-L[i],R[i][0]});}
dis = vc<pi>(N,{-1e9-7,-1e9-7});
dijkstra(P);
return -fpath;}
Compilation message
crocodile.cpp: In function 'void dijkstra(int*)':
crocodile.cpp:15:32: warning: 'sizeof' on array function parameter 'p' will return size of 'int*' [-Wsizeof-array-argument]
15 | for(int i = 0; i < (sizeof(p)/sizeof(int)); i++){
| ~^~
crocodile.cpp:13:19: note: declared here
13 | void dijkstra(int p[]){
| ~~~~^~~
crocodile.cpp:15:22: warning: comparison of integer expressions of different signedness: 'int' and 'long unsigned int' [-Wsign-compare]
15 | for(int i = 0; i < (sizeof(p)/sizeof(int)); i++){
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
