fork download
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define endl "\n"
  6. typedef long long int ll;
  7. typedef vector<int> vi;
  8. const int MOD = 1e9+7;
  9.  
  10. int main(){
  11. int t;
  12. cin>>t;
  13.  
  14. for(int testcase=0; testcase<t; testcase++){
  15. int n,m,h;cin>>n>>m>>h;
  16.  
  17. unordered_map<int, int> hvertex;
  18. vector<int> vis;
  19.  
  20. for (int i = 0; i < h; i++) {
  21. int ttt;
  22. cin>>ttt;
  23. hvertex[ttt] = 1;
  24. }
  25.  
  26. vector<vector<pair<int, int>>> adj(n+1);
  27.  
  28. for (int i = 0; i < m; i++) {
  29. int u, v, w;cin>>u>>v>>w;
  30. adj[u].push_back({v,w});
  31. adj[v].push_back({u,w});
  32. }
  33.  
  34. vi dp(n+1, INT_MAX);
  35. vi dp2(n+1, INT_MAX);
  36.  
  37. priority_queue<array<int, 3>, vector<array<int, 3>>, greater<array<int, 3>>> pq;
  38. pq.push({0, 1, 0}); // {distance, node, horse_status}
  39.  
  40. while(!pq.empty()){
  41. auto [dist, node, has_horse] = pq.top();
  42. pq.pop();
  43.  
  44. if(dist >= dp[node]) continue;
  45. dp[node] = dist;
  46.  
  47. for(auto [next, weight] : adj[node]){
  48. int new_dist = dist + (has_horse ? weight / 2 : weight);
  49. if(dp[next] > new_dist) {
  50. pq.push({new_dist, next, has_horse || hvertex[node]});
  51. }
  52. }
  53. }
  54.  
  55. pq.push({0, n, 0});
  56.  
  57. while(!pq.empty()){
  58. auto [dist, node, has_horse] = pq.top();
  59. pq.pop();
  60.  
  61. if(dist >= dp2[node]) continue;
  62. dp2[node] = dist;
  63.  
  64. for(auto [next, weight] : adj[node]){
  65. int new_dist = dist + (has_horse ? weight / 2 : weight);
  66. if(dp2[next] > new_dist) {
  67. pq.push({new_dist, next, has_horse || hvertex[node]});
  68. }
  69. }
  70. }
  71.  
  72. int res = INT_MAX;
  73. for (int i = 1; i <= n; i++) {
  74. if(dp[i] == INT_MAX || dp2[i] == INT_MAX) continue;
  75. res = min(res, dp[i] + dp2[i]);
  76. }
  77.  
  78. cout << (res == INT_MAX ? -1 : res) << endl;
  79. }
  80. return 0;
  81. }
  82.  
Success #stdin #stdout 0.01s 5284KB
stdin
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
10
-1
10
36
16
28