SMMR-230: Hyperloop

#include <bits/stdc++.h>

using namespace std;

const int INF = 2e9;
using pi = pair <int, int>;
using pii = pair <int, pi>;

int parent[1001], dis[1001];
bool visited[1001];

vector <pi> G[1001];
vector <int> path;

int main(){

    int n, m, z;
    scanf("%d%d%d", &n, &m, &z);

    for(int i=0;i<=n;i++) {
        parent[i] = i;
        dis[i] = INF;
    }

    int s, t;
    scanf("%d%d", &s, &t);

    for(int i=1;i<=m;i++){
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        if(z < w) {
            G[u].push_back({v, w});
            G[v].push_back({u, w});
        }
    }

    int q;
    scanf("%d", &q);

    priority_queue <pi, vector <pi>, greater <pi>> pq;

    dis[s] = 0;
    pq.push({dis[s], s});

    while(pq.size() > 0){

        int u, d;
        u = pq.top().second;
        d = pq.top().first;
        pq.pop();

        if(visited[u])
            continue;
        visited[u] = true;

        if(u == t) {
            break;
        }

        for(auto vw: G[u]){
            int v, w;
            v = vw.first;
            w = vw.second;
            if(!visited[v] and d + w < dis[v]){
                dis[v] = d + w;
                pq.push({dis[v], v});
                parent[v] = u; // ไม่สามารถใช้ if(parent[u] == u) parent[u] = v ได้
                /*
                ex: 1 -> 2 -> ... (ทางที่ผิด)
                    1 -> 3 -> ... (ทางที่ถูก)
                    1 ไป 2, 3 ไม่รู้ว่าเส้นทางที่ถูกต้องคือทางใด
                    เส้นทาง 2 ซึ่ง ทำก่อน 3 อาจไม่ใช่เส้นทางที่ถูกต้อง แล้วตอนปริ้นทางเดินออกมาจะไปผิดทาง เพราะ parent[1] = 2
                    ดังนั้น จึงเก็บ parent[v] = u แทน : ให้ปลายทางมาต้นทาง
                */
            }
        }
    }

    if(!visited[t]){
        printf("-1");
        return 0;
    }

    if(q == 1) printf("%d", dis[t]);
    else {
        printf("%d\n", dis[t]);
        int u = t;
        while(u != s){
            path.push_back(u);
            u = parent[u];
        }
        path.push_back(s);
        printf("%d\n", path.size());
        for(int i = path.size()-1; i >= 0; i--) printf("%d ", path[i]);
    }

    return 0;
}