#include "crocodile.h" #include <bits/stdc++.h> using namespace std; const int N = 1000005; vector<pair<int, int>> graph[N]; int n, m; int dijkstra(int exits[], int sz) { const int INF = 1e9; vector<int> dist(n, INF); vector<int> vis(n, 0); priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q; for (int i = 0; i < sz; i++) { dist[exits[i]] = 0; vis[exits[i]] = 1; q.push({0, exits[i]}); } while (q.size()) { int d = q.top().first; int u = q.top().second; vis[u]++; if (vis[u] == 1) // remove first choice, can't take that shit { continue; } q.pop(); if (d > dist[u]) continue; for (auto i : graph[u]) { int w = i.first; int v = i.second; if (dist[v] > dist[u] + w) { dist[v] = dist[u] + w; if (v == 0) { return dist[v]; } q.push({dist[v], v}); } } } int ans = dist[0]; return ans; } int travel_plan(int nn, int mm, int R[][2], int L[], int K, int P[]) { n = nn, m = mm; for (int i = 0; i < m; i++) { graph[R[i][0]].push_back({L[i], R[i][1]}); graph[R[i][1]].push_back({L[i], R[i][0]}); } return dijkstra(P, K); }