#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
#define pb push_back
#define ins insert
#define f first
#define s second
const int MX = 1e5;
const ll INF = 1e18;
vector<pii> adj[MX];
ll dist[MX], fin[MX];
int main() {
cin.tie(0) -> sync_with_stdio(0);
int n, m, k; cin >> n >> m >> k;
for (int i = 0; i < m; i++) {
int x, y, w;
cin >> x >> y >> w;
adj[x].pb({y, w});
adj[y].pb({x, w});
}
for (int i = 0; i < n; i++) {
dist[i] = INF, fin[i] = INF;
}
vector<int> st(k);
priority_queue<pll> pq;
for (int i = 0; i < k; i++) {
int x; cin >> x;
pq.push({0, x});
st[i] = x;
dist[x] = 0;
}
while (!pq.empty()) {
auto N = pq.top(); pq.pop();
ll t = -N.f, u = N.s;
if (dist[u] != t) continue;
for (auto [v, w] : adj[u]) {
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.push({-dist[v], v});
}
}
}
fin[0] = 0;
pq.push({0, 0});
while (!pq.empty()) {
auto N = pq.top(); pq.pop();
ll t = -N.f, u = N.s;
if (fin[u] != t) continue;
vector<vector<ll>> pos;
for (auto [v, w] : adj[u]) {
pos.pb({w + dist[v], v, w});
}
sort(all(pos), [&](auto& x, auto& y) {
return x[0] < y[0];
});
for (int i = 1; i < sz(pos); i++) {
ll v = pos[i][1], w = pos[i][2];
if (t + w < fin[v]) {
fin[v] = t + w;
pq.push({-fin[v], v});
}
}
}
ll res = 2e9;
for (int i : st) {
smin(res, fin[i]);
}
cout << res << '\n';
auto test = [&]() {
for (int i = 0; i < n; i++) {
cout << i << ": " << fin[i] << '\n';
}
};
// test();
}
/**
* Problem: IOI, Crocodile.
* Observations:
* 1. You will never try to go
* backwards, because there's no
* point to doing that.
* 2. Because of observation 1,
* each possible decision must have
* an alternative that doesn't
* go backwards.
*
* Algorithm:
* First, calculate shortest paths.
* You can never pick the #1 option,
* so always pick the #2 option in terms
* of the distance.
*
* Note: IDK if multi-source Dijkstra
* works, but it should work. IDK.
*/
Compilation message
crocodile.cpp: In function 'int main()':
crocodile.cpp:76:10: warning: variable 'test' set but not used [-Wunused-but-set-variable]
76 | auto test = [&]() {
| ^~~~
/usr/bin/ld: /tmp/cc1Xu25S.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccEJrA4V.o:crocodile.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cc1Xu25S.o: in function `main':
grader.cpp:(.text.startup+0x36): undefined reference to `travel_plan(int, int, int (*) [2], int*, int, int*)'
collect2: error: ld returned 1 exit status
