Submission

PPPPPPPPPP

Score: 100

User: Ongsa123

Problemset: Fast Delivery

Language: cpp

Time: 0.005 second

Submitted On: 2025-03-15 21:42:11

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define twod array<ll,2>
const ll inf = 1e18;

vector<twod> path[100000];
vector<ll> sh(100000,inf);
vector<bool> vis(100000,0);
vector<int> from(100000,-1);
priority_queue<twod,vector<twod>,greater<twod>> pq;

int main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int n,m; cin >> n >> m;
	for(int i=0,u,v,w;i<m;i++){
		cin >> u >> v >> w;
		path[u].pb({w,v});
	}
	int st; cin >> st;
	pq.push({0,st});
	sh[st] = 0;
	//vis[st] = 1;
	while(!pq.empty()){
		twod cur = pq.top();
		pq.pop();
		if(vis[cur[1]]) continue;
		vis[cur[1]] = 1;
		for(auto nx : path[cur[1]]){
			if(!vis[nx[1]] && sh[nx[1]] > cur[0] + nx[0]){
				sh[nx[1]] = cur[0] + nx[0];
				from[nx[1]] = cur[1];
				pq.push({sh[nx[1]],nx[1]});
			}
		}
	}
	for(int i=0;i<n;i++){
		if(i == st){
			continue;
		}
		cout << st << " -> " << i << " (";
		if(sh[i] == inf) cout << "inf)";
		else{
			cout << sh[i] << ") ";
			vector<int> walk;
			int e =i;
			while(e != -1){
				walk.pb(e);
				e = from[e];
			}
			reverse(walk.begin(),walk.end());
			for(auto x : walk) cout << x << ' ';
		}
		cout << "\n";
	}
	return 0;
}