/**
* Essentially a variant of Dijkstra's algorithm. The proof can be left as an exercise.
*
* Time Complexity: O(n + m * log(m)) (Dijkstra)
* Implementation 1 (Full solution)
*/
#include <bits/stdc++.h>
#include "crocodile.h"
typedef long long ll;
typedef std::vector<int> vec;
const ll INF = 0x3f3f3f3f3f3f3f;
struct edge_t {
int node, w;
};
typedef std::vector<edge_t> adj_list_t;
struct dist_info_t {
int node;
ll dist;
};
inline bool operator<(const dist_info_t& d1, const dist_info_t& d2) {
return d1.dist > d2.dist;
}
int travel_plan(int n, int m, int edges[][2], int w[], int K, int P[]) {
std::vector<adj_list_t> graph(n);
for (int k = 0; k < m; k++) {
graph[edges[k][0]].push_back(edge_t{edges[k][1], w[k]});
graph[edges[k][1]].push_back(edge_t{edges[k][0], w[k]});
}
std::vector<ll> time(n, INF);
std::priority_queue<dist_info_t> pq;
vec wait(n, 2);
for (int i = 0; i < K; i++) {
time[P[i]] = 0, wait[P[i]] = 1;
pq.push(dist_info_t{P[i], 0});
}
while (!pq.empty() && wait[0] > 0) {
dist_info_t t = pq.top();
pq.pop();
if (wait[t.node] == 0)
continue;
time[t.node] = t.dist, wait[t.node]--;
if (wait[t.node] == 0) {
for (const edge_t& e : graph[t.node]) {
if (wait[e.node] > 0)
pq.push(dist_info_t{e.node, time[t.node] + e.w});
}
}
}
assert(time[0] < INF);
return time[0];
}
