fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // for convenience
  5. using pii = pair<int, int>;
  6. using pipii = pair<int, pii>;
  7. const int inf = 1e9;
  8.  
  9. /**
  10.  * n = จำนวน node ในกราฟ (0..n-1)
  11.  * m = จำนวน edge ในกราฟ
  12.  * G[u] = list ของ node ที่ติดอยู่กับ u (ตัวแรกคือหมายเลข node, ตัวที่สองคือ weight)
  13.  */
  14. int shortest_path(int n, int m, vector<pii> G[], int k, int s, int t)
  15. {
  16.     vector<vector<int>> dist(n, vector<int>(k+1, inf));
  17.     vector<vector<bool>> visited(n, vector<bool>(k+1, false));
  18.  
  19.     // push สถานะเริ่มต้นใส่ priority queue ของ dijkstra
  20.     dist[s][k] = 0;
  21.     priority_queue<pipii, vector<pipii>, greater<pipii>> Q; // min heap (dist[u][f], (u, f))
  22.     Q.push({dist[s][k], {s, k}});
  23.  
  24.     while (!Q.empty()) {
  25.         int u = Q.top().second.first, f = Q.top().second.second;
  26.         Q.pop();
  27.         if (visited[u][f])
  28.             continue;
  29.         visited[u][f] = true;
  30.         if (u == t) // end
  31.             return dist[u][f];
  32.  
  33.         // เพิ่มการเปลี่ยนสถานะจาก (u, f) ไปสถานะอื่น ๆ ใส่ priority_queue
  34.         for (auto vw : G[u]) {
  35.             int v = vw.first, w = vw.second;
  36.             if (!visited[v][f] && dist[u][f]+w < dist[v][f]) { // เดินตามปกติ
  37.                 dist[v][f] = dist[u][f]+w;
  38.                 Q.push({dist[v][f], {v, f}});
  39.             }
  40.             if (f >= 1 && !visited[v][f-1] && dist[u][f] < dist[v][f-1]) { // ใช้สิทธิ์ผ่านฟรี 1 ครั้ง
  41.                 dist[v][f-1] = dist[u][f];
  42.                 Q.push({dist[v][f-1], {v, f-1}});
  43.             }
  44.         }
  45.     }
  46.  
  47.     return -1; // ไม่มีเส้นทางจากจุดเริ่มต้นไปจุดจบ
  48. }
  49.  
  50. vector<pii> G[100010];
  51. int main()
  52. {
  53.     int n, m, k, s, t;
  54.     scanf("%d%d%d%d%d", &n, &m, &k, &s, &t);
  55.     assert(s >= 0 && s < n);
  56.     assert(t >= 0 && t < n);
  57.     while (m--) {
  58.         int u, v, w;
  59.         scanf("%d%d%d", &u, &v, &w);
  60.         assert(u >= 0 && u < n);
  61.         assert(v >= 0 && v < n);
  62.         G[u].push_back({v, w});
  63.     }
  64.     printf("%d\n", shortest_path(n, m, G, k, s, t));
  65.  
  66.     return 0;
  67. }
Success #stdin #stdout 0s 17584KB
comments (?)
stdin
copy 
5 5 1
0 3
0 1 4
1 2 5
2 3 4
0 4 8
4 3 7
stdout
copy 
7
https://ideone.com/3hipRU
language:
C++14 (gcc 8.3)
created:
4 years 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!