#include <bits/stdc++.h> #include "crocodile.h" using namespace std; int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) { int dp[N][2]; for (int i = 0; i < N; i++) { dp[i][0] = dp[i][1] = INT_MAX; } vector <vector <pair<int,int>>> v(N); for (int i = 0; i < M; i++) { int u = R[i][0]; int u1 = R[i][1]; v[u].emplace_back(u1,L[i]); v[u1].emplace_back(u,L[i]); } priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q; for (int i = 0; i < N; i++) { if (v[i].size() == 1) { dp[i][0] = dp[i][1] = 0; q.push({0,i}); } } while (!q.empty()) { auto [w1,f] = q.top(); q.pop(); if (w1 != dp[f][1]) continue; for (auto [to,w]:v[f]) { if (dp[to][0] > dp[f][1] + w) { if (dp[to][1] > dp[to][0]) { dp[to][0] = dp[to][1]; q.push({dp[to][1],to}); } dp[to][0] = dp[f][1] + w; } else if (dp[to][1] > dp[f][1] + w) { dp[to][1] = dp[f][1] + w; q.push({dp[to][1],to}); } } } return dp[0][1]; }