#include "crocodile.h" #include <bits/stdc++.h> using namespace std; using ll = long long; using pr = pair<int, int>; #define pb push_back const int INF = 1e9+7; int n, m; struct Node{ int next, v, id; }; vector<vector<Node>> edge; vector<bool> fin; int dijkstra() { vector<vector<int>> dist(n, vector<int>(2, INF)); // min, and second min to a finish vector<bool> vis(n, 0); vector<pr> prev(n, {-1, -1}); priority_queue<pr, vector<pr>, greater<pr>> pq; // val, node for (int i = 0; i < n; i++) { if (fin[i]) { pq.push({0, i}); dist[i][0] = 0; dist[i][1] = 0; } } while (!pq.empty()) { auto [d, node] = pq.top(); pq.pop(); if (vis[node]) continue; vis[node] = 1; for (auto [next, v, id] : edge[node]) { if (dist[next][0] > d + v) { dist[next][1] = dist[next][0]; dist[next][0] = d + v; if (dist[next][1] != INF) pq.push({dist[next][1], next}); } else if (dist[next][1] > d + v) { dist[next][1] = d + v; pq.push({d + v, next}); } } } return dist[0][1]; } int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){ n = N; m = M; edge.assign(n, {}); fin.assign(n, 0); for (int i = 0; i < m; i++) { edge[R[i][0]].pb({R[i][1], L[i], i}); edge[R[i][1]].pb({R[i][0], L[i], i}); } for (int i = 0; i < K; i++) fin[P[i]] = 1; int res = dijkstra(); if (res == INF) return -1; else return res; return N; }