Submission

--PPP-P---

Score: 40

User: Nightingale

Problemset: Fast Delivery

Language: cpp

Time: 0.002 second

Submitted On: 2025-03-31 10:31:52

#include <bits/stdc++.h>
#define int long long
using namespace std;
map<int,vector<int>> path;
vector<int> visited;
int best = LLONG_MAX;
vector<int> reala;
int a;
int b;
int deli(vector<vector<int>> &dis,int her,int targ,int walk,vector<int> &jou){
  if(her==targ&&walk<=best){
    best = walk;
    if(jou.size()<reala.size()||reala.empty()&&targ!=a-1) reala = jou;
    else if(targ==a-1) reala = jou;
    return 0;
  }
  if(count(visited.begin(),visited.end(),her)!=0) return 0;
  visited.push_back(her);
  for(int i=0;i<path[her].size();i++){
    vector<int> jou2 = jou;
    jou2.push_back(path[her][i]);
    if(dis[her][path[her][i]]==LLONG_MAX) continue;
    int walk2 = walk+dis[her][path[her][i]];
    deli(dis,path[her][i],targ,walk2,jou2);
  }
  return 0;
}
int32_t main() 
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> a >> b;
  vector<vector<int>> dis(a,vector<int>(a,LLONG_MAX));
  vector<int> jou;
  for(int i=0;i<b;i++){
    int c,d,e;
    cin >> c >> d >> e;
    path[c].push_back(d);
    dis[c][d] = e;
  }
  int want;
  cin >> want;
  for(auto it=path.begin();it!=path.end();it++){
    best = LLONG_MAX;
    visited.clear();
    reala.clear();
    if(it->first!=want){
      deli(dis,want,it->first,0,reala);
      cout << want << " -> " << it->first << ' ' << "(";
      if(best!=LLONG_MAX) cout << best << ") " << want << ' ';
      else cout << "inf" << ")";
      for(int i=0;i<reala.size();i++){
        cout << reala[i] << ' ';
      }
      cout << '\n';
    }
  }
}