#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, ban, vis; vector<int> dp(n, INF); int dijkstra() { vector<vector<int>> dist(n, vector<int>(2, INF)); // min, and second min to a finish vector<bool> vis; 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][1] = 0; } } while (!pq.empty()) { auto [d, node] = pq.top(); pq.pop(); if (dist[node][1] < d) continue; for (auto [next, v, id] : edge[node]) { if (dist[next][0] > d + v) { dist[next][1] = dist[next][0]; dist[next][0] = d + v; 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 dfs(int node, int prev) { // if (vis[node]) return dp[node]; // vis[node] = 1; // if (fin[node]) return dp[node] = 0; // // vector<Node> banned, allow; // int a = INF, b = INF; // for (auto [next, v, id] : edge[node]) { // if (next == prev) continue; // int t = dfs(next, node) + v; // if (t < a) { // b = a; // a = t; // } // else if (t < b) { // b = t; // } // } // return dp[node] = b; // } int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){ n = N; m = M; edge.assign(n, {}); ban.assign(m, 0); vis.assign(n, 0); 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; }