Cerința

Dijkstra este un cetățean model al comunității în care trăiește. El își ajută fiecare vecin aflat în necaz. Astăzi, Vlad îi cere ajutorul și îl roagă să livreze câte un pachet fiecărui vecin de-al lor. Știind că sunt n case în aceasta comunitate, iar distanțele dintre ele variază, Dijkstra vă roagă să realizați un program care să afișeze costul drumului minim dintre casa p, casa lui Vlad, și casele vecinilor. În cazul în care nu există drum până la unul dintre vecini, se va afișa -1.

Date de intrare

Programul citește din fișier numărul n, numărul de case din comunitate, m, numărul de drumuri dintre case, p, numărul casei lui Vlad, iar pe următoarele m linii se vor afla x, y și d cu semnificația că există drum între casele x și y de lungime d.

Date de ieșire

Programul va afișa n numere separate printr-un spațiu, al i-lea număr reprezentând distanța minimă de la casa lui Vlad la casa i.

Restricții și precizări

1 ≤ p ≤ n ≤ 100.000
1 ≤ m ≤ 250.000
cele m distanțe citite vor fi mai mici decât 20.000

Exemplu

dijkstra2.in

dijkstra2.out

2 0 2 7 3

Explicație

Drumurile minime de la casa lui Vlad la celelalte case sunt 2 0 2 7 3.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Dijkstra2:

#include <bits/stdc++.h>

using namespace std;
class cmp
{
    public:
    bool operator ()(pair <int, int> &a, pair<int, int> &b)
    {
        return a.second>b.second;
    }
};
priority_queue < pair <int, int>, vector <pair<int, int>>, cmp> pq;
int n, p, m;
vector <pair <int, int>> graf[100001];
int dist[100001];
void initializare(int p)
{
    int i;
    for (i = 1; i<=n; ++i)
        if (i!=p) dist[i] = 2000000000;
}
int main()
{
    ifstream fin ("dijkstra2.in");
    ofstream fout ("dijkstra2.out");
    fin >> n >> m >> p;
    initializare(p);
    int y, i, j, x, nod, cost, d;
    for (i = 0; i<m; ++i)
    {
        fin >> x >> y >> d;
        graf[x].push_back (make_pair(y, d));
        graf[y].push_back (make_pair(x, d));
    }
    pq.push(make_pair(p, dist[p]));
    while (pq.size())
    {
        nod = pq.top().first;
        cost = pq.top().second;
        pq.pop();
        if (dist[nod] != cost)
            continue;
        for (auto x : graf[nod])
        {
            if (cost + x.second < dist[x.first])
            {
                dist[x.first] = cost+x.second;
                pq.push(make_pair(x.first, dist[x.first]));
            }
        }
    }
    for (i = 1; i<=n; ++i)
        {if (dist[i] != 2000000000)
            fout << dist[i] << " ";
        else fout << "-1 ";}
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #1887 Dijkstra2

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1887 Dijkstra2 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #1887 Dijkstra2