Submission

Score: 30

User: achinhchin

Problemset: Fast Delivery

Language: cpp

Time: 0.003 second

Submitted On: 2026-02-26 04:20:19

#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);vpl A(n);
  while(m--)cin>>i>>j>>k,G[i].emplace_back(k,j),G[j].emplace_back(k,i);
  cin>>a;Q.push({0,a,a});
  while(!Q.empty()){
    T=Q.top(),Q.pop();if(A[T[1]].f)continue;
    A[T[1]].f=T[0],A[T[1]].s=T[2];
    for(auto i:G[T[1]])if(!A[i.s].f&&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<<" (";
    if(!A[i].f){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';
  }
}