Submission

PP-PPPP-PP

Score: 80

User: Nightingale

Problemset: Fast Delivery

Language: cpp

Time: 0.003 second

Submitted On: 2025-03-31 12:04:38

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a;
int b;
map<int,vector<int>> path;
map<int,int> preve;
void star(vector<vector<int>> &dp,int here,vector<int> &meta){
  for(auto it=path[here].begin();it!=path[here].end();it++){
    if(dp[here][*it]!=LLONG_MAX&&meta[here]+dp[here][*it]<meta[*it]){
      meta[*it] = meta[here]+dp[here][*it];
      preve[*it] = here;
      star(dp,*it,meta);
    }
  }
  return;
}
int32_t main() 
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> a >> b;
  vector<vector<int>> dp(a,vector<int>(a,LLONG_MAX));
  vector<int> meta(a,LLONG_MAX);
  for(int i=0;i<b;i++){
    int c,d,e;
    cin >> c >> d >> e;
    dp[c][d] = e;
    path[c].push_back(d);
  }
  int want;
  cin >> want;
  meta[want] = 0;
  star(dp,want,meta);
  for(auto it=path.begin();it!=path.end();it++){
    if(it->first!=want){
      if(meta[it->first]==LLONG_MAX){
        cout << want << " -> " << it->first << " (" << "inf" << ") ";
      }
      else{
        cout << want << " -> " << it->first << " (" <<  meta[it->first] << ") ";
        int meat = it->first;
        vector<int> walker;
        walker.push_back(meat);
        while(1){
          meat = preve[meat];
          walker.push_back(meat);
          if(meat==want) break;
        }
        for(int i=walker.size()-1;i>=0;i--){
          cout << walker[i] << ' ';
        }
      }
      cout << '\n';
    }
  }
}