Submission

Score: 100

User: AugusEiEi

Problemset: Fast Delivery

Language: cpp

Time: 0.002 second

Submitted On: 2026-03-24 10:18:19

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

typedef long long ll;
typedef pair<ll,ll> pll;
ll inf=1e18;

int main(){
  ios_base::sync_with_stdio(0); cin.tie(0);
  int n,m;cin>>n>>m;
  vector<ll>dist(n,inf),prev(n,-1);
  vector<bool>visited(n,false);
  vector<pll>edges[n];
  for(int i=0;i<m;i++){
    int u,v,w;cin>>u>>v>>w;
    edges[u].emplace_back(v,w);
    //edges[v].emplace_back(u,w);
  }
  int s;cin>>s;
  priority_queue<pll,vector<pll>,greater<pll>>pq;
  dist[s]=0;
  pq.emplace(dist[s],s);
  while(!pq.empty()){
    auto [d,x]=pq.top();
    pq.pop();
    if(visited[x]){
      continue;
    }
    visited[x]=true;
    for(auto [tox,w]:edges[x]){
      if(dist[tox]>d+w){
        dist[tox]=d+w;
        prev[tox]=x;
        pq.emplace(dist[tox],tox);
      }
    }
  }
  for(int i=0;i<n;i++){
    if(i==s) continue;
    cout<<s<<" -> "<<i<<" (";
    if(dist[i]==inf){
      cout<<"inf)"<<endl;
      continue;
    }else{
      cout<<dist[i]<<") ";
    }
    vector<int>path;
    for(int j=i;j!=-1;j=prev[j]){
      path.push_back(j);
    }
    reverse(path.begin(),path.end());
    for(int x:path) cout<<x<<" ";
    cout<<endl;
  }
}