fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define endl "\n"
  5. typedef long long ll;
  6. const int MOD = 1e9+7;
  7. const ll INF = LLONG_MAX / 2;
  8.  
  9. int main() {
  10. ios_base::sync_with_stdio(false);
  11. cin.tie(NULL);
  12.  
  13. int t;
  14. cin >> t;
  15.  
  16. while (t--) {
  17. int n, m, h;
  18. cin >> n >> m >> h;
  19.  
  20. unordered_set<int> hvertex;
  21. for (int i = 0; i < h; ++i) {
  22. int x;
  23. cin >> x;
  24. hvertex.insert(x);
  25. }
  26.  
  27. vector<vector<pair<int, int>>> adj(n + 1);
  28. for (int i = 0; i < m; ++i) {
  29. int u, v, w;
  30. cin >> u >> v >> w;
  31. adj[u].emplace_back(v, w);
  32. adj[v].emplace_back(u, w);
  33. }
  34.  
  35. auto dijkstra = [&](int start) {
  36. vector<vector<ll>> dist(n + 1, vector<ll>(2, INF));
  37. using T = tuple<ll, int, int>; // (distance, node, state)
  38. priority_queue<T, vector<T>, greater<T>> pq;
  39.  
  40. // Initialize starting node
  41. dist[start][0] = 0;
  42. pq.emplace(0, start, 0);
  43.  
  44. // If start is H-vertex, initialize state 1
  45. if (hvertex.count(start)) {
  46. dist[start][1] = 0;
  47. pq.emplace(0, start, 1);
  48. }
  49.  
  50. while (!pq.empty()) {
  51. auto [d, u, s] = pq.top();
  52. pq.pop();
  53.  
  54. if (d > dist[u][s]) continue;
  55.  
  56. for (auto [v, w] : adj[u]) {
  57. if (s == 1) {
  58. // Halve the edge weight, transition to state 0
  59. ll new_d = d + w / 2;
  60. if (new_d < dist[v][0]) {
  61. dist[v][0] = new_d;
  62. pq.emplace(new_d, v, 0);
  63. }
  64. } else {
  65. // State 0: pay full weight
  66. ll new_d = d + w;
  67. if (new_d < dist[v][0]) {
  68. dist[v][0] = new_d;
  69. pq.emplace(new_d, v, 0);
  70. }
  71.  
  72. // If current node (u) is H-vertex, allow halving next edge
  73. if (hvertex.count(u)) {
  74. if (d < dist[v][1]) { // Pay 0 to activate state 1
  75. dist[v][1] = d;
  76. pq.emplace(d, v, 1);
  77. }
  78. }
  79. }
  80. }
  81. }
  82. return dist;
  83. };
  84.  
  85. auto from_1 = dijkstra(1);
  86. auto from_n = dijkstra(n);
  87.  
  88. ll ans = INF;
  89. for (int i = 1; i <= n; ++i) {
  90. // Case 1: Current node is H-vertex
  91. if (hvertex.count(i)) {
  92. ll option1 = min(from_1[i][0], from_1[i][1]) +
  93. min(from_n[i][0], from_n[i][1]);
  94. ans = min(ans, option1);
  95. }
  96. // Case 2: Regular node
  97. else {
  98. ll option2 = from_1[i][0] + from_n[i][0];
  99. ans = min(ans, option2);
  100. }
  101. }
  102.  
  103. if (ans == INF) cout << -1 << endl;
  104. else cout << ans % MOD << endl;
  105. }
  106.  
  107. return 0;
  108. }
Success #stdin #stdout 0.01s 5280KB
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
5
-1
9
18
12
22