Submission

PPPPPPPPPP

Score: 100

User: Dormon

Problemset: Fast Delivery

Language: cpp

Time: 0.002 second

Submitted On: 2025-03-13 14:11:21

#include <iostream>
#include <cstdint>
#include <cstring>
#include <vector>
#include <algorithm>
#include <functional>
#include <queue>
#include <numeric>
#include <array>
#include <iomanip> // cout << fixed << setprecision(n);

using namespace std;
const bool TEST_CASE = 0;

template<typename T>
typename std::enable_if<std::is_integral<T>::value>::type
Debug(const char* name, T value) {
    std::cout << name << " : " << value << '\n';
}

template<typename T, typename... Args>
typename std::enable_if<std::is_integral<T>::value>::type
Debug(const char* names, T value, Args... args){
    const char* comma = strchr(names, ',');
    std::cout.write(names, comma - names) << " : " << value << " | ";
    Debug(comma + 1, args...);
}
template<typename T> 
ostream& operator<<(ostream& out, vector<T> &a){
    for (auto &x : a) out << x << ' '; 
    return out;
};

#ifdef DORMON
    #define debug(...) Debug(#__VA_ARGS__, __VA_ARGS__)
#else
    #define debug(...) 
#endif

#define int long long

void solve(){
    int n, m;
    cin >> n >> m;
    
    vector<vector<array<int, 2>>> adj(n);

    for (int i = 0;i < m;i++){
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        // adj[v].push_back({u, w});
    }

    int st;
    cin >> st;

    vector<int> dist(n, 1e18), pa(n, 0ll);
    iota(pa.begin(), pa.end(), 0ll);

    struct heap{
        int pre, u, w;
        bool operator < (const heap &o) const {
            return w > o.w;
        }
    };

    priority_queue<heap> pq;
    pq.push({st, st, dist[st] = 0ll});
    while (!pq.empty()){
        auto [pre, u, W] = pq.top(); pq.pop();
        if (dist[u] < W) continue;
        for (auto [v, w]:adj[u]){
            if (dist[u] + w < dist[v]){
                pq.push({u, v, dist[u] + w});
                dist[v] = dist[u] + w;
                pa[v] = u;
            }
        }
    }

    vector<vector<int>> path(n);
    
    for (int i = 0;i < n;i++){
        if (i == st) continue;
        if (dist[i] == 1e18){
            path[i].push_back(-1 + 0ll);
            continue;
        }
        int u = i;
        while (u != st){
            path[i].push_back(u);
            u = pa[u];
        }
        path[i].push_back(st);
        reverse(path[i].begin(), path[i].end());
    }
    for (int i = 0;i < n;i++){
        if (i == st) continue;
        cout << st << " -> " << i;
        if (dist[i] != 1e18)
            cout << " (" << dist[i] << ") ";
        else{
            cout << " (inf)\n";
            continue;
        } 
        cout << path[i] << '\n';
    }
}


int32_t main()
{
    #ifndef DORMON
        ios_base::sync_with_stdio(false); 
    #endif
    cin.tie(0);
    int q = 1; 
    if (TEST_CASE) cin >> q;
    while (q--){
        solve();
    }
}