fork download
copy 
  1. #include <bits/stdc++.h> 
  2. using namespace std;
  3.  
  4. #define endl "\n" 
  5. typedef long long int ll;
  6. typedef vector<int> vi;
  7. const int MOD = 1e9+7;
  8.  
  9. int main(){
  10.     int t;
  11.     cin >> t;
  12.  
  13.     while (t--) {
  14.         int n, m, h;
  15.         cin >> n >> m >> h;
  16.  
  17.         // Store horse nodes
  18.         vector<bool> hasHorse(n+1, false);
  19.         for (int i = 0; i < h; i++) {
  20.             int x;
  21.             cin >> x;
  22.             hasHorse[x] = true;
  23.         }
  24.  
  25.         // Adjacency List
  26.         vector<vector<pair<int, int>>> adj(n+1);
  27.         for (int i = 0; i < m; i++) {
  28.             int u, v, w;
  29.             cin >> u >> v >> w;
  30.             adj[u].push_back({v, w});
  31.             adj[v].push_back({u, w});
  32.         }
  33.  
  34.         // Distance Arrays
  35.         vector<vector<int>> dp(n+1, vector<int>(2, INT_MAX));
  36.         vector<vector<int>> dp2(n+1, vector<int>(2, INT_MAX));
  37.  
  38.         // Visited Arrays
  39.         vector<vector<bool>> vis(n+1, vector<bool>(2, false));
  40.  
  41.         // ---------------------- First Dijkstra (From 1)
  42.         priority_queue<array<int, 3>, vector<array<int, 3>>, greater<array<int, 3>>> pq;
  43.  
  44.         // Start with node 1
  45.         dp[1][0] = 0;
  46.         pq.push({0, 1, 0});  // {distance, node, horse_not_used}
  47.  
  48.         if (hasHorse[1]) {
  49.             dp[1][1] = 0;
  50.             pq.push({0, 1, 1});
  51.         }
  52.  
  53.         while (!pq.empty()) {
  54.             auto [currDist, node, state] = pq.top();
  55.             pq.pop();
  56.  
  57.             if (vis[node][state]) continue;
  58.             vis[node][state] = true;
  59.  
  60.             for (auto [nextNode, weight] : adj[node]) {
  61.                 int newDist = currDist + (state ? weight / 2 : weight);
  62.  
  63.                 // Transition without horse
  64.                 if (dp[nextNode][state] > newDist) {
  65.                     dp[nextNode][state] = newDist;
  66.                     pq.push({newDist, nextNode, state});
  67.                 }
  68.             }
  69.         }
  70.  
  71.         // ---------------------- Second Dijkstra (From n)
  72.         vis.assign(n+1, vector<bool>(2, false));
  73.         pq.push({0, n, 0});
  74.         dp2[n][0] = 0;
  75.  
  76.         if (hasHorse[n]) {
  77.             dp2[n][1] = 0;
  78.             pq.push({0, n, 1});
  79.         }
  80.  
  81.         while (!pq.empty()) {
  82.             auto [currDist, node, state] = pq.top();
  83.             pq.pop();
  84.  
  85.             if (vis[node][state]) continue;
  86.             vis[node][state] = true;
  87.  
  88.             for (auto [nextNode, weight] : adj[node]) {
  89.                 int newDist = currDist + (state ? weight / 2 : weight);
  90.  
  91.                 // Transition without horse
  92.                 if (dp2[nextNode][state] > newDist) {
  93.                     dp2[nextNode][state] = newDist;
  94.                     pq.push({newDist, nextNode, state});
  95.                 }
  96.             }
  97.         }
  98.  
  99.         // ---------------------- Calculate the Result
  100.         int res = INT_MAX;
  101.         for (int i = 1; i <= n; i++) {
  102.             res = min(res, max(min(dp[i][0], dp[i][1]), min(dp2[i][0], dp2[i][1])));
  103.         }
  104.  
  105.         if (res == INT_MAX) cout << -1 << endl;
  106.         else cout << res << endl;
  107.     }
  108.  
  109.     return 0;
  110. }
  111.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
6
2 1 1
1
1 2 10
3 1 2
2 3
1 2 10
3 3 1
2
1 2 4
1 3 10
2 3 6
4 3 2
2 3
1 2 10
2 3 18
3 4 16
3 2 1
2
1 2 4
1 3 16
7 7 1
3
1 5 2
2 6 12
1 2 12
6 4 8
7 3 4
6 3 4
7 6 4
stdout
copy 
5
-1
6
28
16
16
https://ideone.com/5KZbpM
language:
C++14 (clang 8.0)
created:
39 days ago
visibility:
public

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!