Submission

Score: 40

User: patty

Problemset: Fast Delivery

Language: cpp

Time: 0.003 second

Submitted On: 2026-03-06 20:13:49

#include <bits/stdc++.h>
using namespace std;
int findroot(vector<int> &parent, int a) {
	if(a==parent[a]) return a;
	return parent[a] = findroot(parent,parent[a]);
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n,m,u,v,w,home,k;
	cin >> n >> m;
	vector<vector<pair<int,int>>> city(n);
	for(int i=0;i<m;i++) {
		cin >> u >> v >> w;
		city[u].push_back({v,w});
		city[v].push_back({u,w});
	}
	cin >> home;
	vector<int> parent(n,-1);
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
	vector<int> dis(n,INT_MAX);
	q.push({0,home});
	dis[home] = 0;
	while(!q.empty()) {
		int weight = q.top().first;
		int tobe = q.top().second;
		q.pop();
		if(weight>dis[tobe]) continue;
		for(auto &i : city[tobe]) {
			if(weight+i.second<dis[i.first]) {
				dis[i.first] = weight + i.second;
				q.push({weight+i.second,i.first});
				parent[i.first] = tobe;
			}
		}
	}
	for(int j=0;j<n;j++) {
		if(j!=home) {
			cout << home << " -> " << j << ' ';
			if(parent[j]==-1) cout << "(inf)\n";
			else {
				cout << "(" << dis[j] << ")";
				vector<int> path;
				k = j;
				while(parent[k]!=-1) {
					path.push_back(k);
					k = parent[k];
				}
				reverse(path.begin(),path.end());
				cout << ' ' << home;
				for(auto &st : path) cout << ' ' << st;
				cout << '\n';
			}
		}
	}
}