Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <fstream>
- #include <queue>
- #include <vector>
- using namespace std;
- ifstream fin("dijkstra.in");
- ofstream fout("dijkstra.out");
- const int NMax = 50005;
- const int oo = (1 << 30); // constanta infinit
- int N, M;
- int D[NMax]; // vector de distanta
- bool InCoada[NMax]; //stocheaza cand un nod intra in coada
- vector < pair < int, int > > G[NMax]; //vector de perechi
- struct ComparaDistante // functie care ordoneaza min si max
- {
- bool operator()(int x,int y) // x si y -nodurile pe care coada le compara
- {
- return D[x] > D[y];
- }
- };
- priority_queue < int, vector < int >,ComparaDistante > Coada;
- void Citire()
- {
- fin >> N >> M;
- for(int i = 1; i <= M; i++)
- {
- int x, y, c;
- fin >> x >> y >> c;
- G[x].push_back(make_pair(y, c)); // punem in G[x] toti vecinii y care au costul c
- }
- }
- void Afiseaza()
- {
- for(int i = 2; i <= N; i++) // i = 2 pt ca nodul de start e 1 ( "Dijkstra(1)" )
- if(D[i] != oo)
- fout << D[i] << " ";
- else
- fout << "0 ";
- }
- void Dijkstra(int nodStart)
- {
- for(int i = 1; i <= N; i++)
- D[i] = oo; // incepem cu toate distantele fiind oo
- D[nodStart]=0; // distanta la nodul de start = 0
- Coada.push(nodStart); // punem nodul de start in coada
- InCoada[nodStart] = true; // marcam nodul ca fiind in coada
- while(!Coada.empty()) // cat timp coada nu e goala
- {
- int nodCurent = Coada.top(); // extragem nodul curent
- Coada.pop(); // il eliminam
- InCoada[nodCurent] = false; //nodul curent nu mai face parte din coada
- for(size_t i = 0; i < G[nodCurent].size(); i++)
- {
- int Vecin = G[nodCurent][i].first;
- int Cost = G[nodCurent][i].second;
- if(D[nodCurent] + Cost < D[Vecin])
- {
- D[Vecin] = D[nodCurent] + Cost;
- if(InCoada[Vecin] == false) // daca vecinul nu se afla in coada
- {
- Coada.push(Vecin); // adaugam vecinul in coada
- InCoada[Vecin] = true; //marcam vecinul ca fiind in coada
- }
- }
- }
- }
- }
- int main()
- {
- Citire();
- Dijkstra(1);
- Afiseaza();
- return 0;
- }
Add Comment
Please, Sign In to add comment