Submission

Score: 40

User: kavin8888

Problemset: Fast Delivery

Language: cpp

Time: 0.002 second

Submitted On: 2026-03-10 10:12:44

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,start;
vector<vector<pair<int,int>>> adj;
vector<int> dist,p;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
signed main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>n>>m;
	adj.resize(n); dist.assign(n,1e9); p.assign(n,-1);
	for(int i=0;i<m;++i) {
		int u,v,d; cin>>u>>v>>d;
		adj[u].push_back({v,d});
		adj[v].push_back({u,d});
	}
	cin>>start;
	dist[start]=0;
	pq.push({0,start});
	while(!pq.empty()) {
		auto [c,u] =pq.top(); pq.pop();
		if(c>dist[u]) continue;
		for(auto [v,d] : adj[u]) {
			if(c+d<dist[v]) {
				dist[v]=c+d; p[v]=u;
				pq.push({c+d,v});
			}
		}
	}
	for(int i=0;i<n;++i) {
		if(i==start) continue;
		cout<<start<<" -> "<<i<<" ";
		if(dist[i]==1e9) { cout<<"(inf)\n"; continue; }
		cout<<"("<<dist[i]<<") ";
		vector<int> path; int curr=i;
		while(curr!=-1) { path.push_back(curr); curr=p[curr]; }
		reverse(path.begin(),path.end());
		for(int j:path) cout<<j<<" ";
		cout<<'\n';
	}
	return 0;
}