Submission

PPPPPPPPPP

Score: 100

User: osensunny

Problemset: Fast Delivery

Language: cpp

Time: 0.002 second

Submitted On: 2025-03-22 21:46:35

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

#define vi vector<int>
#define vvi vector<vi>
#define ii pair<int, int>
#define fi first
#define se second
#define vii vector<ii>
#define vvii vector<vii>
#define vb vector<bool>

int V, E, src, a, b, c;
vvii adj(1005);
vi dist(1005, 1e9), par(1005, -1);
vb vis(1005, false);

void solve(){
	dist[src] = 0;
	priority_queue<ii, vii, greater<ii>> pq;
	pq.push({dist[src], src});
	
	while(!pq.empty()){
		ii fr = pq.top();
		pq.pop();
		
		int u = fr.se;
		if(vis[u]) continue;
		vis[u] = true;
		
		for(ii edge: adj[u]){
			int w = edge.fi, v = edge.se;
			if(dist[u] + w < dist[v]){
				dist[v] = dist[u] + w;
				par[v] = u;
				pq.push({dist[v], v});
			}
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	
	cin >> V >> E;
	for(int i=0; i<E; i++){
		cin >> a >> b >> c;
		adj[a].push_back({c, b});
	}
	cin >> src;

	solve();
	
	for(int i=0; i<V; i++){
		if(i != src){
			if(dist[i] == 1e9){
				cout << src << " -> " << i << " (inf)";
			}
			else{
				cout << src << " -> " << i << " (" << dist[i] << ") ";
				stack<int> st;
				int x = i;
				while(x != -1){
					st.push(x);
					x = par[x];
				}
				while(!st.empty()){
					cout << st.top() << ' ';
					st.pop();
				}
			}
			cout << '\n';
		}
	}
	
	return 0;
}
/*
6 8
0 2 1
1 0 3
1 2 5
2 3 2
2 4 4
3 0 5
3 5 5
4 5 1
1
*/