Advertisement
YEZAELP

SMMR-230: Hyperloop

Dec 25th, 2020
117
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.44 KB | None
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int INF = 2e9;
  6. using pi = pair <int, int>;
  7. using pii = pair <int, pi>;
  8.  
  9. int parent[1001], dis[1001];
  10. bool visited[1001];
  11.  
  12. vector <pi> G[1001];
  13. vector <int> path;
  14.  
  15. int main(){
  16.  
  17.     int n, m, z;
  18.     scanf("%d%d%d", &n, &m, &z);
  19.  
  20.     for(int i=0;i<=n;i++) {
  21.         parent[i] = i;
  22.         dis[i] = INF;
  23.     }
  24.  
  25.     int s, t;
  26.     scanf("%d%d", &s, &t);
  27.  
  28.     for(int i=1;i<=m;i++){
  29.         int u, v, w;
  30.         scanf("%d%d%d", &u, &v, &w);
  31.         if(z < w) {
  32.             G[u].push_back({v, w});
  33.             G[v].push_back({u, w});
  34.         }
  35.     }
  36.  
  37.     int q;
  38.     scanf("%d", &q);
  39.  
  40.     priority_queue <pi, vector <pi>, greater <pi>> pq;
  41.  
  42.     dis[s] = 0;
  43.     pq.push({dis[s], s});
  44.  
  45.     while(pq.size() > 0){
  46.  
  47.         int u, d;
  48.         u = pq.top().second;
  49.         d = pq.top().first;
  50.         pq.pop();
  51.  
  52.         if(visited[u])
  53.             continue;
  54.         visited[u] = true;
  55.  
  56.         if(u == t) {
  57.             break;
  58.         }
  59.  
  60.         for(auto vw: G[u]){
  61.             int v, w;
  62.             v = vw.first;
  63.             w = vw.second;
  64.             if(!visited[v] and d + w < dis[v]){
  65.                 dis[v] = d + w;
  66.                 pq.push({dis[v], v});
  67.                 parent[v] = u; // ไม่สามารถใช้ if(parent[u] == u) parent[u] = v ได้
  68.                 /*
  69.                 ex: 1 -> 2 -> ... (ทางที่ผิด)
  70.                     1 -> 3 -> ... (ทางที่ถูก)
  71.                     1 ไป 2, 3 ไม่รู้ว่าเส้นทางที่ถูกต้องคือทางใด
  72.                     เส้นทาง 2 ซึ่ง ทำก่อน 3 อาจไม่ใช่เส้นทางที่ถูกต้อง แล้วตอนปริ้นทางเดินออกมาจะไปผิดทาง เพราะ parent[1] = 2
  73.                     ดังนั้น จึงเก็บ parent[v] = u แทน : ให้ปลายทางมาต้นทาง
  74.                 */
  75.             }
  76.         }
  77.     }
  78.  
  79.     if(!visited[t]){
  80.         printf("-1");
  81.         return 0;
  82.     }
  83.  
  84.     if(q == 1) printf("%d", dis[t]);
  85.     else {
  86.         printf("%d\n", dis[t]);
  87.         int u = t;
  88.         while(u != s){
  89.             path.push_back(u);
  90.             u = parent[u];
  91.         }
  92.         path.push_back(s);
  93.         printf("%d\n", path.size());
  94.         for(int i = path.size()-1; i >= 0; i--) printf("%d ", path[i]);
  95.     }
  96.  
  97.     return 0;
  98. }
Advertisement
RAW Paste Data Copied
Advertisement