Submission

PPPPPPPPPP

Score: 100

User: lufychop

Problemset: Fast Delivery

Language: cpp

Time: 0.003 second

Submitted On: 2025-03-14 15:25:22

#include <bits/stdc++.h>

using namespace std;

int main(void)
{
	long long n,m,s,u,v,w,t;
	cin>>n>>m;
	vector<long long> dis(n+1,1e18);
	vector<long long> prev(n+1,INT_MAX);
	vector<vector<pair<long long,long long>>> adj(n+1);
	priority_queue<pair<long long,long long>,vector<pair<long long,long long>>,greater<pair<long long,long long>>> pq;
	for(int i=0;i<m;i++)
	{
		cin>>u>>v>>w;
		adj[u].push_back({w,v});
	}
	cin>>s;
	dis[s]=0;
	prev[s]=-1;
	pq.push({0,s});
	while(!pq.empty())
	{
		u=pq.top().second;
		w=pq.top().first;
		pq.pop();
		if(w>dis[u])
		{
			continue;
		}
		for(int i=0;i<adj[u].size();i++)
		{
			t=adj[u][i].first;
			v=adj[u][i].second;
			if(dis[v]>w+t)
			{
				dis[v]=w+t;
				prev[v]=u;
				pq.push({w+t,v});
			}
		}
	}
	for(int i=0;i<n;i++)
	{
		if(i==s)
		{
			continue;
		}
		cout<<s<<" -> "<<i<<" ";
		if(dis[i]==1e18)
		{
			cout<<"(inf)\n";
			continue;
		}
		cout<<"("<<dis[i]<<") ";
		stack<long long> st;
		v=i;
		while(v!=s)
		{
			st.push(v);
			v=prev[v];
		}
		cout<<s;
		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

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 0
*/