Submission

PPPPPPPPPP

Score: 100

User: pxsit

Problemset: Fast Delivery

Language: cpp

Time: 0.003 second

Submitted On: 2025-03-13 11:22:59

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
#define ld long double
#define ull unsigned ll
#define cint const int
#define cf const float

cint mxA = 1e6+5, MOD = 1e9+7, INF = 0x3f3f3f3f;
cint d4x[4] = {0, 1, 0, -1}, d4y[4] = {1, 0, -1, 0};
cint d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1}, d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1};

vector<vector<pair<int,int>>> adj;
vector<vector<int>> way;
int n, m, q, dis[10005];
bool vis[10005];
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;

void solve(){
    memset(dis,INF,sizeof(dis));
    cin >> n >> m;
    adj.resize(n);
    way.resize(n);
    for(int i = 1, u, v, w; i <= m; i++){
        cin >> u >> v >> w;
        adj[u].push_back({v,w});
    }cin >> q;
    pq.push({0,q});
    dis[q] = 0;
    while(!pq.empty()){
        int d = pq.top().first, u = pq.top().second; pq.pop();
        // cout << d << ' ' << u << endl;
        if(vis[u]) continue;
        vis[u] = true;
        for(pair<int,int> p: adj[u]){
            if(p.second+dis[u]<dis[p.first]){
                dis[p.first] = dis[u]+p.second;
                if(!way[p.first].empty()) way[p.first].clear();
                if(!way[u].empty()) for(int i: way[u]) way[p.first].push_back(i);
                way[p.first].push_back(u);
                pq.push({dis[p.first],p.first});
            }
        }
    }
    for(int i = 0; i < n; i++){
        if(i!=q){
            if(dis[i]==INF) cout << q << " -> " << i << " (inf)";
            else{
                cout << q << " -> " << i << " (" << dis[i] << ") ";
                for(int j: way[i]) cout << j << ' '; cout << i;
            }cout << endl;
        }
    }
    return;
}

int main(){
    cin.tie(nullptr)->sync_with_stdio(0);cout.tie(0);
    // freopen("", "r", stdin);
    // freopen("", "w", stdout);
    int t = 1;
    // cin >> t;
    while(t--) solve();
    return 0;
}