Submission

PPPPPPPPPP

Score: 100

User: hmmm

Problemset: Fast Delivery

Language: cpp

Time: 0.006 second

Submitted On: 2025-03-13 11:34:56

#include<bits/stdc++.h>
using namespace std;
using pii=array<int,2>;
const int N=1e5+5;
vector<pii> g[N];
int dis[N],pa[N];
bool vis[N];
priority_queue<pii,vector<pii>,greater<pii>> q;

int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	int n,m;
	cin >> n >> m;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin >> u >> v >> w;
		g[u].push_back({v,w});
//		g[v].push_back({u,w});
	}
	memset(pa,-1,sizeof pa);
	int t;
	cin >> t;
	memset(dis,0x3f,sizeof dis);
	q.push({dis[t]=0,t});
	while(!q.empty()){
		auto l=q.top()[0];
		auto x=q.top()[1];
		q.pop();
		if(vis[x]) continue;
		vis[x]=true;
		for(auto e:g[x]){
			auto xx=e[0];
			auto ll=e[1];
			if(vis[xx]==false && dis[xx]>dis[x]+ll){
				dis[xx]=dis[x]+ll;
				q.push({dis[xx],xx});
				pa[xx]=x;
			}
		}
	}
	for(int i=0;i<n;i++){
		if(i==t) continue;
//		cout << dis[i] << ' ';
		if(dis[i]==1061109567){
			cout << t << " -> " << i << " (inf)\n";
		}
		else{
			cout << t << " -> " << i << " (" <<dis[i] << ") ";
				int to=i;
				vector<int> p;
				while(to!=-1){
					p.push_back(to);
//					cout << to << ' ';
					to=pa[to];
				}
				reverse(p.begin(),p.end());
				for(auto e:p) cout << e << ' ';
			cout << "\n";
		}
	}
}