Submission

PPPPPPPPPP

Score: 100

User: Ongsa123

Problemset: Fast Delivery

Language: cpp

Time: 0.005 second

Submitted On: 2025-03-14 00:19:30

#include <bits/stdc++.h>
using namespace std;
using ll=long long int;
#define twod array<ll,2>
const ll inf=1e18;
priority_queue<twod,vector<twod>,greater<twod>> q;
vector<twod> node[100000];
vector<ll> dp(100000,inf);
bool ans[100000];
bool vis[100000];
int pa[100000];
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n,nn;cin >> n >> nn;
	for(int i=1;i<=nn;i++){
		int u,v,w;cin >> u >> v >> w;
		node[u].push_back({v,w});
//		node[v].push_back({u,w});
	}
	int st;cin >> st;
	dp[st]=0;
	pa[st]=-1;
	q.push({0,st});
	while(!q.empty()){
		auto x=q.top();q.pop();
		auto u=x[1],w=x[0];
		if(vis[u]!=0) continue;
		vis[u]=1;
		for(auto e:node[u]){
			auto v=e[0],l=e[1];
			if(vis[v]==0 && dp[v]>dp[u]+l){
				dp[v]=dp[u]+l;
				pa[v]=u;
				q.push({dp[v],v});
			}
		}
	}
	for(int i=0;i<n;i++){
		if(i!=st)cout << st << " -> " << i << " ";
		else continue;
		if(dp[i]==inf) cout << "(inf)\n";
		else{
			cout << '(' << dp[i] << ')' << " ";
			int u=i;
			vector<int> path;
			while(u!=-1){
				path.push_back(u);
				u=pa[u];
			}
			reverse(path.begin(),path.end());
			for(auto e:path) cout << e << " ";
			cout << "\n";
		} 
	}
	return 0;
}