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

dijkstra.out

3 1 4 0 -1

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 Dijkstra:

#include <iostream>

#include <fstream>

#define INFINIT 1000000000

using namespace std;



ifstream fin("dijkstra.in");

ofstream fout("dijkstra.out");



int n , a[105][105], v[105], d[105], t[105];



int main()

{

    int i , j , c , p;

    fin >> n >> p;

    

    for(i =1 ; i <= n ; ++i)

        for(j = 1 ; j <= n ; ++j)

            a[i][j] = INFINIT;

    

    while( fin >> i >> j >> c )

        a[i][j] = c;

    

    for(i =1 ; i <= n ; i ++ )

    {

        v[i] = 0;

        d[i] = a[p][i];

        t[i] = p;

    }

    v[p] = 1, t[p] = 0, d[p] = 0;

    d[0] = INFINIT;

    for(int k = 1 ; k < n ; ++k)

    {

        int pmax = 0;

        for(i = 1 ; i <= n ; ++i)

            if(v[i] == 0 && d[i] < d[pmax])

                pmax = i;

        if(pmax > -1)

        {

            v[pmax] = 1;

            for(i = 1; i <= n ; ++i)

                if(v[i] == 0 && d[i] > d[pmax] + a[pmax][i])

                    d[i] = d[pmax] + a[pmax][i], t[i] = pmax;

        }

    }

    

    for(i = 1 ;i <= n ; ++i)

        fout << (d[i] != INFINIT ? d[i] : -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 #588 Dijkstra

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #588 Dijkstra 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 #588 Dijkstra