Cod sursa(job #2467574)

Utilizator geniucosOncescu Costin geniucos Data 4 octombrie 2019 17:16:51
Problema Algoritmul lui Dijkstra Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.59 kb
#include<bits/stdc++.h>

using namespace std;

template < class T >
class WeightedGraph {
public:
    vector < vector < pair < int, T > > > v;
    void readGraph (int N, int M, bool isDigraph = 0) {
        v.resize (N);
        while (M --) {
            int x, y;
            T z;
            scanf ("%d %d", &x, &y);
            cin >> z;
            x --, y --;
            v[x].push_back ({y, z});
            if (!isDigraph)
                v[y].push_back ({x, z});
        }
    }
    int size () {
        return v.size ();
    }
};

template < class T, class T0 >
vector < T > dijkstra (WeightedGraph < T0 > &g, int source) {
    priority_queue < pair < T, int > > PQ;
    vector < T > ans (g.size (), -1);
    ans[source] = 0;
    PQ.push ({0, source});
    while (!PQ.empty ()) {
        auto curr = PQ.top ();
        int node = curr.second;
        T currD = -curr.first;
        PQ.pop ();
        if (currD > ans[node])
            continue;
        for (auto it : g.v[node])
            if (ans[it.first] < 0 || ans[it.first] > ans[node] + it.second)
                ans[it.first] = ans[node] + it.second,
                PQ.push ({-ans[it.first], it.first});
    }
    return ans;
}

int main () {
    freopen ("dijkstra.in", "r", stdin);
    freopen ("dijkstra.out", "w", stdout);

    int N, M, S = 0;
    scanf ("%d %d", &N, &M);
    WeightedGraph < int > g;
    g.readGraph (N, M, 1);
    auto ans = dijkstra < long long, int > (g, S);
    for (auto it : ans)
        if (it != 0)
            printf ("%lld ", (it < 0 ? 0 : it));
    printf ("\n");
}