#include "crocodile.h" #include <bits/stdc++.h> using namespace std; const long long MAXN = 1e5 + 5; set<long long> exits; vector<pair<long long, long long> > g[MAXN]; long long values[MAXN][2]; bool vis[MAXN]; int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) { for(long long i = 0; i < MAXN; i++) { values[i][0] = 1e15; values[i][1] = 1e15; } for(long long i = 0; i < K; i++) { exits.insert(P[i]); } for(long long i = 0; i < M; i++) { g[R[i][0]].push_back({R[i][1], L[i]}); g[R[i][1]].push_back({R[i][0], L[i]}); } for(long long i = 0; i < N; i++) { if(exits.count(i)) { for(long long j = 0; j < g[i].size(); j++) { int hi = g[i][j].first; if(!exits.count(hi)) { if(values[hi][1] < g[i][j].second) { continue; } else if(values[hi][0] < g[i][j].second) { values[hi][1] = g[i][j].second; } else { values[hi][1] = values[hi][0]; values[hi][0] = g[i][j].second; } } } } } priority_queue<pair<long long, long long>, vector<pair<long long, long long> >, greater<pair<long long, long long> > > pq; for(long long i = 0; i < N; i++) { if(values[i][1] != 1e15) { pq.push({values[i][1], i}); } } while(!pq.empty()) { pair<long long, long long> cur = pq.top(); pq.pop(); long long cur_dist = cur.first, node = cur.second; if(vis[node]) { continue; } if(node == 0) { break; } vis[node] = true; for(long long i = 0; i < g[node].size(); i++) { if(exits.count(g[node][i].first) || vis[g[node][i].first]) { continue; } long long new_dist = g[node][i].second + cur_dist; long long next = g[node][i].first; //cout << "node = " << node << ", next = " << next << ", cur_dist = " << cur_dist << ", new_dist = " << new_dist << endl; if(values[next][1] < new_dist) { continue; } else if(values[next][0] < new_dist) { //assert(!vis[g[node][i].first]); values[next][1] = new_dist; pq.push({values[next][1], next}); } else { //assert(!vis[g[node][i].first]); values[next][1] = values[next][0]; values[next][0] = new_dist; pq.push({values[next][1], next}); } } } while(!pq.empty()) { pq.pop(); } /*for(int i = 0; i < N; i++) { cout << values[i][0] << " " << values[i][1] << endl; }*/ assert(values[0][1] != 1e15); return values[0][1]; }

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:25:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |       for(long long j = 0; j < g[i].size(); j++) {
      |                            ~~^~~~~~~~~~~~~
crocodile.cpp:59:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for(long long i = 0; i < g[node].size(); i++) {
      |                          ~~^~~~~~~~~~~~~~~~