Submission

PPPPPPPPPP

Score: 100

User: Nightingale

Problemset: Fast Delivery

Language: cpp

Time: 0.002 second

Submitted On: 2025-03-31 15:29:56

#include <bits/stdc++.h>
#define int long long
using namespace std;

int a, b;
map<int, vector<int>> path;
map<int, int> preve;
void star(vector<vector<int>> &dp,int here,vector<int> &meta){
  queue<int> st;
  st.push(here);
  meta[here] = 0;
  
  while(!st.empty()){
    int ex = st.front();
    st.pop();
    for(int i=0;i<path[ex].size();i++){
      if(dp[ex][path[ex][i]]!=LLONG_MAX&&meta[ex]!=LLONG_MAX&&meta[ex]+dp[ex][path[ex][i]]<meta[path[ex][i]]){
        meta[path[ex][i]] = meta[ex]+dp[ex][path[ex][i]];
        preve[path[ex][i]] = ex;
        st.push(path[ex][i]);
      }
    }
  }
}
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;

    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 (meat != want) {
                    meat = preve[meat];
                    walker.push_back(meat);
                }

                for (int i = walker.size() - 1; i >= 0; i--) {
                    cout << walker[i] << ' ';
                }
            }
            cout << '\n';
        }
    }
}