#include <bits/stdc++.h> #define ll long long #define task "RELAYMARATHON" using namespace std; const int N = 1e5 + 16; const ll INF = 1e18; int n, m, K, u, v, a[N]; ll w, result; vector < pair <int, ll> > adj[N]; /* 6 6 4 1 2 5 2 4 7 4 6 50 6 5 3 1 5 15 3 5 6 1 5 4 6 */ /* 11 15 5 1 2 3 1 2 2 1 5 12 2 4 5 5 4 10 6 5 12 6 7 14 7 5 7 7 9 9 9 4 6 4 8 5 8 10 9 10 9 16 7 11 21 9 11 20 1 11 10 6 7 */ namespace sub1 { ll d[516][516]; priority_queue < pair <ll, int>, vector < pair <ll, int> >, greater < pair <ll, int> > > pq; void dijkstra(int k, int t) { for (int i = 1; i <= n; i++) { d[t][i] = INF; } d[t][k] = 0; pq.push({d[t][k], k}); while (!pq.empty()) { pair <ll, int> top = pq.top(); pq.pop(); ll dist = top.first; int u = top.second; if (dist > d[t][u]) { continue; } for (auto v : adj[u]) { int vertex = v.first; ll value = v.second; if (d[t][vertex] > dist + value) { d[t][vertex] = dist + value; pq.push({d[t][vertex], vertex}); } } } } ll result = INF; void solve() { for (int i = 1; i <= K; i++) { dijkstra(a[i], i); } for (int i = 1; i <= K; i++) { for (int j = i + 1; j <= K; j++) { for (int k = 1; k <= K; k++) { for (int s = k + 1; s <= K; s++) { if (a[i] != a[k] && a[i] != a[s] && a[j] != a[k] && a[j] != a[s]) { result = min(result, d[i][a[j]] + d[k][a[s]]); } } } } } cout << result; } } namespace sub2 { ll d[516][516]; priority_queue < pair <ll, int>, vector < pair <ll, int> >, greater < pair <ll, int> > > pq; void dijkstra(int k, int t) { for (int i = 1; i <= n; i++) { d[t][i] = INF; } d[t][k] = 0; pq.push({d[t][k], k}); while (!pq.empty()) { pair <ll, int> top = pq.top(); pq.pop(); ll dist = top.first; int u = top.second; if (dist > d[t][u]) { continue; } for (auto v : adj[u]) { int vertex = v.first; ll value = v.second; if (d[t][vertex] > dist + value) { d[t][vertex] = dist + value; pq.push({d[t][vertex], vertex}); } } } } ll result = INF; void solve() { for (int i = 1; i <= K; i++) { dijkstra(a[i], i); } for (int i = 1; i <= K; i++) { for (int j = 1; j <= K; j++) { if (i == j) { continue; } int e1 = -1, e2 = -1; for (int k = 1; k <= K; k++) { if (k == i || k == j) { continue; } if (e1 == -1 || d[i][e1] > d[i][a[k]]) { e1 = a[k]; } } for (int k = 1; k <= K; k++) { if (k == i || k == j || a[k] == e1) { continue; } if (e2 == -1 || d[j][e2] > d[j][a[k]]) { e2 = a[k]; } } result = min(result, d[i][e1] + d[j][e2]); } } cout << result; } } int main() { ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0); if (fopen(task".inp", "r")) { freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); } cin >> n >> m >> K; for (int i = 1; i <= m; i++) { cin >> u >> v >> w; adj[u].push_back({v, w}); adj[v].push_back({u, w}); } for (int i = 1; i <= K; i++) { cin >> a[i]; } if (n <= 50) { sub1 :: solve(); } else { sub2 :: solve(); } return 0; }

RelayMarathon.cpp: In function 'int main()':
RelayMarathon.cpp:165:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  165 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
RelayMarathon.cpp:166:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  166 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~