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.                 // Transition with horse (if available)
  70.                 if (!state && hasHorse[nextNode]) {
  71.                     if (dp[nextNode][1] > newDist) {
  72.                         dp[nextNode][1] = newDist;
  73.                         pq.push({newDist, nextNode, 1});
  74.                     }
  75.                 }
  76.             }
  77.         }
  78.  
  79.         // ---------------------- Second Dijkstra (From n)
  80.         vis.assign(n+1, vector<bool>(2, false));
  81.         pq.push({0, n, 0});
  82.         dp2[n][0] = 0;
  83.  
  84.         if (hasHorse[n]) {
  85.             dp2[n][1] = 0;
  86.             pq.push({0, n, 1});
  87.         }
  88.  
  89.         while (!pq.empty()) {
  90.             auto [currDist, node, state] = pq.top();
  91.             pq.pop();
  92.  
  93.             if (vis[node][state]) continue;
  94.             vis[node][state] = true;
  95.  
  96.             for (auto [nextNode, weight] : adj[node]) {
  97.                 int newDist = currDist + (state ? weight / 2 : weight);
  98.  
  99.                 // Transition without horse
  100.                 if (dp2[nextNode][state] > newDist) {
  101.                     dp2[nextNode][state] = newDist;
  102.                     pq.push({newDist, nextNode, state});
  103.                 }
  104.             }
  105.         }
  106.  
  107.         // ---------------------- Calculate the Result
  108.         int res = INT_MAX;
  109.         for (int i = 1; i <= n; i++) {
  110.             res = min(res, max(min(dp[i][0], dp[i][1]), min(dp2[i][0], dp2[i][1])));
  111.         }
  112.  
  113.         if (res == INT_MAX) cout << -1 << endl;
  114.         else cout << res << endl;
  115.     }
  116.  
  117.     return 0;
  118. }
  119.  
Success #stdin #stdout 0s 5296KB
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
19
14
16
https://ideone.com/Amm3dq
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!