• API
• FAQ
• Tools
• Archive
SHARE
TWEET Dijkstra a guest Sep 22nd, 2019 99 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include    <iostream>
2. #include    <fstream>
3. #include    <queue>
4. #include    <vector>
5.
6. using namespace std;
7.
8. ifstream fin("dijkstra.in");
9. ofstream fout("dijkstra.out");
10.
11. const int NMax = 50005;
12. const int oo = (1 << 30);
13.
14. int N, M;
15. int D[NMax];
17.
18. vector < pair < int, int > > G[NMax];
19.
21. {
22.     bool operator()(int x,int y)
23.     {
24.         return D[x] > D[y];
25.     }
26. };
27.
28. priority_queue < int, vector < int >,ComparaDistante > Coada;
29.
30. void Citire()
31. {
32.     fin >> N >> M;
33.     for(int i = 1; i <= M; i++)
34.     {
35.         int x, y, c;
36.         fin >> x >> y >> c;
37.         G[x].push_back(make_pair(y, c));
38.     }
39. }
40.
41. void Afiseaza()
42. {
43.     for(int i = 2; i <= N; i++)
44.         if(D[i] != oo)
45.         fout << D[i] << " ";
46.     else
47.         fout << "0 ";
48. }
49.
50. void Dijkstra(int nodStart)
51. {
52.     for(int i = 1; i <= N; i++)
53.         D[i] = oo;
54.
55.     D[nodStart]=0;
57.     InCoada[nodStart] = true;
59.     {
60.         int nodCurent = Coada.top();
62.         InCoada[nodCurent] = false;
63.
64.         for(size_t i = 0; i < G[nodCurent].size(); i++)
65.        {
66.             int Vecin = G[nodCurent][i].first;
67.             int Cost = G[nodCurent][i].second;
68.             if(D[nodCurent] + Cost < D[Vecin])
69.            {
70.                D[Vecin] = D[nodCurent] + Cost;
71.                if(InCoada[Vecin] == false)
72.                 {
74.             InCoada[Vecin] = true;
75.                 }
76.            }
77.         }
78.     }
79. }
80.
81. int main()
82. {
83.     Citire();
84.     Dijkstra(1);
85.     Afiseaza();
86.     return 0;
87. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!

Top