Submission

Score: 100

User: cyblox_boi

Problemset: Fast Delivery

Language: cpp

Time: 0.002 second

Submitted On: 2026-03-14 19:06:33

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

struct Edge
{
    int v, w;
};

typedef map<int, vector<Edge>> AdjList;

vector<int> getPath(int v, map<int, int> &parent)
{
    vector<int> path;

    while (v != -1)
    {
        path.push_back(v);

        v = parent[v];
    }

    reverse(path.begin(), path.end());

    return path;
}

void dijkstra(AdjList &adj, int n, int start)
{
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    map<int, int> dist;
    map<int, int> parents;

    for (int i = 0; i < n; i++)
    {
        dist[i] = INT_MAX;
        parents[i] = -1;
    }

    dist[start] = 0;

    pq.push({0, start});

    while (!pq.empty())
    {
        auto [d, u] = pq.top();

        pq.pop();

        if (d > dist[u])
        {
            continue;
        }

        for (const auto &edge : adj[u])
        {
            int newCost = dist[u] + edge.w;

            if (newCost < dist[edge.v])
            {
                dist[edge.v] = newCost;
                parents[edge.v] = u;

                pq.push({newCost, edge.v});
            }
        }
    }

    for (const auto &p : parents)
    {
        if (p.first == start)
        {
            continue;
        }

        cout << start << " -> " << p.first << " (";

        if (dist[p.first] == INT_MAX)
        {
            cout << "inf";
        }
        else
        {
            cout << dist[p.first];
        }

        cout << ") ";

        if (dist[p.first] != INT_MAX)
        {
            vector<int> path = getPath(p.first, parents);

            for (const int &i : path)
            {
                cout << i << ' ';
            }
        }

        cout << '\n';
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    AdjList adj;

    for (int i = 0; i < m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;

        adj[u].push_back({v, w});
    }

    int start;
    cin >> start;

    dijkstra(adj, n, start);

    return 0;
}