Submission

PPPPPPPPPP

Score: 100

User: FotoFatTurtle

Problemset: Fast Delivery

Language: cpp

Time: 0.003 second

Submitted On: 2025-03-20 19:35:23

#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int node,edge,te,mp,temp,st;
    cin>>node>>edge;
    vector<vector<pair<int,int>>> adj(node);
    for(int i=0;i<edge;i++)
    {
        cin>>te>>mp>>temp;
        adj[te].push_back({temp,mp});
    }
    cin>>st;
    priority_queue<pair<pair<int,int>,vector<int>>,vector<pair<pair<int,int>,vector<int>>>,greater<pair<pair<int,int>,vector<int>>>> q;
    int dist[node];
    for(int i=0;i<node;i++)
        dist[i]=2e9;
    vector<vector<int>> rou(node);
    dist[st]=0;
    rou[st].push_back(st);
    q.push({{0,st},rou[st]});
    vector<int> tempo;
    while(!q.empty())
    {
        te=q.top().f.f;
        mp=q.top().f.s;
        tempo=q.top().s;
        q.pop();
        if(dist[mp]>te)
            continue;
        for(int i=0;i<adj[mp].size();i++)
        {
            if(dist[adj[mp][i].s]>te+adj[mp][i].f)
            {
                dist[adj[mp][i].s]=te+adj[mp][i].f;
                tempo.push_back(adj[mp][i].s);
                rou[adj[mp][i].s]=tempo;
                q.push({{te+adj[mp][i].f,adj[mp][i].s},tempo});
                tempo.pop_back();
            }
        }
    }
    /*for(int i=0;i<node;i++)
        cout<<dist[i]<<" ";*/
    for(int i=0;i<node;i++)
    {
        if(i==st)
            continue;
        if(dist[i]==2e9)
        {
            cout<<st<<" -> "<<i<<" (inf)";
        }
        else
        {
            cout<<st<<" -> "<<i<<" ("<<dist[i]<<") ";
            for(int j=0;j<rou[i].size();j++)
                cout<<rou[i][j]<<" ";
        }       
        cout<<"\n";
    }
    /*for(int i=0;i<rou[4].size();i++)
        cout<<rou[4][i]<<" ";*/
}