Submission

Score: 90

User: achinhchin

Problemset: Fast Delivery

Language: cpp

Time: 0.003 second

Submitted On: 2026-02-26 04:31:10

#include<iostream>
#include<algorithm>
#include<utility>
#include<vector>
#include<map>
#include<stack>
#include<queue>
#define f first
#define s second
#define fr front()
#define bg begin()
#define en end()
using namespace std;
typedef long long l;
typedef pair<l,l> pl;
typedef pair<l,pair<l,l>> ppl;
typedef vector<l> vl;
typedef vector<vector<l>> vvl;
typedef vector<vector<pair<l,l>>> vvp;
typedef vector<pair<l,l>> vpl;
typedef map<l,l> ml;

const l LLM=1e18;
priority_queue<array<l,3>,vector<array<l,3>>,greater<array<l,3>>>Q;
array<l,3>T;
l n,m,i,j,k,a,b,c,t;

int main(){
  cin.tie(nullptr)->sync_with_stdio(0);
  cin>>n>>m;vvp G(n);
  
  // FIX 1: Initialize distances to LLM and parents to -1
  vpl A(n, {LLM, -1}); 
  
  while(m--)cin>>i>>j>>k,G[i].emplace_back(k,j);
  cin>>a;Q.push({0,a,a});
  
  while(!Q.empty()){
    T=Q.top(),Q.pop();
    
    // FIX 2: Check if distance is no longer infinity
    if(A[T[1]].f != LLM) continue; 
    
    A[T[1]].f=T[0],A[T[1]].s=T[2];
    for(auto i:G[T[1]])
      // FIX 3: Only push to queue if the neighbor hasn't been finalized
      if(A[i.s].f == LLM && i.s != a)
        Q.push({T[0]+i.f,i.s,T[1]});
  }
  
  for(i=0;i<n;i++) if(i!=a) {
    cout<<a<<" -> "<<i<<" (";
    
    // FIX 4: Check against LLM to see if node is actually unreachable
    if(A[i].f == LLM){cout<<"inf)\n";continue;}
    
    cout<<A[i].f<<") "<<a;
    vl B;
    for(t=i;t!=a;t=A[t].s) B.push_back(t);
    for(j=B.size()-1;j>=0;j--) cout<<' '<<B[j];
    cout<<'\n';
  }
}