fork download 
  1. #include <bits/stdc++.h>
  2. #define FOR(i,a,b) for (int i = a; i <= b; i++)
  3.  
  4. using namespace std;
  5.  
  6. const int MAXN = 1005;
  7. const long long INF = 1e18;
  8.  
  9. vector<pair<int,int>> adj[MAXN];
  10. long long d[MAXN];
  11. long long dist[MAXN][MAXN];
  12. int store[MAXN];
  13. int n,k,m;
  14.  
  15. void sub1() {
  16.     FOR(i,1,n)
  17.         FOR(j,1,n)
  18.             if (i != j) dist[i][j] = INF;
  19.     FOR(u,1,n)
  20.         for (auto [v,w] : adj[u])
  21.             dist[u][v] = min(dist[u][v], 1LL*w);
  22.  
  23.     FOR(t,1,n)
  24.         FOR(i,1,n)
  25.             FOR(j,1,n)
  26.                 dist[i][j] = min(dist[i][j], dist[i][t] + dist[t][j]);
  27.  
  28.     long long res = INF;
  29.     FOR(i,1,n) {
  30.         long long temp = 0;
  31.         FOR(j,1,k) temp = max(temp, dist[i][store[j]]);
  32.         res = min(res, temp);
  33.     }
  34.     cout << res;
  35. }
  36.  
  37. long long dijkstra(int s) {
  38.     memset(d, 0x3f, sizeof(d));
  39.     d[s] = 0;
  40.  
  41.     priority_queue<pair<long long,int>> pq;
  42.     pq.push({0,s});
  43.  
  44.     while(!pq.empty()) {
  45.  
  46.         long long val = -pq.top().first;
  47.         int u = pq.top().second;
  48.         pq.pop();
  49.  
  50.         if (val > d[u]) continue;
  51.  
  52.         for (auto [v,w] : adj[u]) {
  53.             if (d[v] > d[u] + w) {
  54.                 d[v] = d[u] + w;
  55.                 pq.push({-d[v], v});
  56.             }
  57.         }
  58.     }
  59. 	long long temp = 0;
  60.     FOR(i,1,k)
  61.         temp = max(temp, d[store[i]]);
  62.     return temp;
  63. }
  64.  
  65. void sub2() {
  66.     long long res = INF;
  67.     FOR(i,1,n) res = min(res, dijkstra(i));
  68.     cout << res;
  69. }
  70.  
  71. int main() {
  72.     cin >> n >> k >> m;
  73.     FOR(i,1,k) cin >> store[i];
  74.  
  75.     FOR(i,1,m) {
  76.         int u,v,c;
  77.         cin >> u >> v >> c;
  78.         adj[u].push_back({v,c});
  79.         adj[v].push_back({u,c});
  80.     }
  81.  
  82.     if (n <= 100) sub1();
  83. 	else sub2();
  84.  
  85. 	return 0;
  86. }
  87.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin 
Standard input is empty
stdout 
1000000000000000000
https://ideone.com/IfmVcU
language:
C++14 (clang 8.0)
created:
121 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!