Submission

Score: 70

User: AugusEiEi

Problemset: Fast Delivery

Language: cpp

Time: 0.123 second

Submitted On: 2026-03-24 10:05:09

#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);
  ll n,m;cin>>n>>m;
  vector<ll>dist(n,inf);
  vector<bool>visited(n,false);
  vector<pll>edges[n];
  vector<ll>prev(n,-1);
  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);
  }
  ll 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);
      }
    }
  }
  vector<ll>ans[n];
  for(int i=0;i<n;i++){
    int x=i;
    ans[i].push_back(i);
    while(prev[x]!=s){
      ans[i].push_back(prev[x]);
      x=prev[x];
    }
    ans[i].push_back(s);
  }
  for(int i=0;i<n;i++){
    if(i==s) continue;
    if(dist[i]==inf) cout<<s<<" -> "<<i<<" "<<"(inf)";
    else cout<<s<<" -> "<<i<<" "<<'('<<dist[i]<<") ";
    if(dist[i]!=inf){
      for(int j=ans[i].size()-1;j>=0;j--){
        cout<<ans[i][j]<<" ";
      }
    }
    cout<<endl;
  }
}