Submission

Score: 100

User: PIP3_PP

Problemset: Fast Delivery

Language: cpp

Time: 0.003 second

Submitted On: 2026-03-13 16:50:19

#include<bits/stdc++.h>
using namespace std;

int main(){
	int m,n;
	cin >> m >> n;
	unordered_map<int,vector<pair<int,int>>> G;
	for(int i = 0 ; i < n ; i++){
		int x, y, w;
		cin >> x >> y >> w;
		G[x].push_back({w,y});
	}
	int st;
	cin >> st;
	priority_queue<pair<int,int> , vector<pair<int,int>> , greater<pair<int,int>>> pq;
	vector<pair<int,vector<int>>> dist(m,{INT_MAX,{}});
	
	pq.push({0,st});
	dist[st] = {0,{st}};
	
	while(!pq.empty()){
		auto t = pq.top();
		int w = t.first , u = t.second;
		pq.pop();
		
		if(w > dist[u].first) continue;
		
		for(auto x : G[u]){
			int e = x.first , v = x.second;
			if(dist[v].first > dist[u].first + e){
				dist[v].first = dist[u].first + e;
				vector<int> temp = dist[u].second;
				temp.push_back(u);
				dist[v].second = temp ;
				pq.push({dist[v].first,v});
			}
		}
	}
	
	for(int i = 0 ; i < m ; i++){
		if(dist[i].first == 0) continue;
		cout << st << " -> " << i << " (";
		if(dist[i].first != INT_MAX) cout << dist[i].first << ") ";
		else {cout << "inf) \n"; continue;}
		for(int j = 1 ; j < dist[i].second.size() ; j++){
			cout << dist[i].second[j] << " ";
		}
		cout << i <<"\n";
	}
}
//1
//-> 0 (3) 1 0
//1
//-> 2 (4) 1 0 2
//1
//-> 3 (6) 1 0 2 3
//1
//-> 4 (8) 1 0 2 4
//1
//-> 5 (9) 1 0 2 4 5