Cerința

Se dă un graf orientat ponderat cu n noduri – în care fiecare arc are asociat un cost, număr natural strict pozitiv, și un nod p. Să se determine, folosind algoritmul lui Dijkstra, costul minim al drumului de la p la fiecare nod al grafului.

Date de intrare

Fișierul de intrare dijkstra.in conține pe prima linie numerele n p, iar următoarele linii câte un triplet i j c, cu semnificația: există arcul (i j) și are costul c.

Date de ieșire

Fișierul de ieșire dijkstra.out va conține pe prima linie n numere, separate prin exact un spațiu, al i-lea număr reprezentând costul drumului minim de la p la i. Dacă nu există drum de la p la un anumit vârf, costul afișat va fi -1.

Restricții și precizări

• 1 ≤ n ≤ 100
• costul unui arc va fi mai mic decât 1000
• costul unui drum este egal cu suma costurilor arcelor care îl compun

Exemplu

dijkstra.in

5 4
1 3 1
2 1 2
4 2 1
4 3 8
5 3 5
5 4 2

dijkstra.out

3 1 4 0 -1

#include <bits/stdc++.h>


using namespace std;
#define Inf 0x3f3f3f3f

ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");

using PI = pair<int , int>;
int n , m , x , y , p , D[100001] , w;
vector <PI> G[100001];

void dijkstra(int nod)
{
    priority_queue < PI , vector<PI> , greater<PI> > Q;
    D[nod] = 0;
    Q.push({0 , nod});
    while(!Q.empty())
    {
       x = Q.top().first;
       y = Q.top().second;
       Q.pop();
       if(x > D[y]) continue;
       for(auto& q:G[y])
       {
           int nodnou = q.first;
           int costnou = q.second;
           if(D[nodnou] > D[y] + costnou)
           {
               D[nodnou] = D[y] + costnou;
               Q.push({D[nodnou] , nodnou});
           }
       }
    }
}

int main()
{
    cin >> n >> p;
    while(cin >> x >> y >> w)
        G[x].push_back({y , w});

    for(int i = 1 ; i <= n ; i++)
        D[i] = Inf;
    dijkstra(p);
    for(int i = 1 ; i <= n ; i++)
        if(D[i] == Inf) cout << "-1 ";
        else cout << D[i] << " ";
}