hopingsteam

Tutoriale-Pe.NET - Algoritmul lui Dijkstra

Nov 13th, 2017
124
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /* Tutoriale-Pe.NET - Algoritmul lui Dijkstra
  2.  * Link: http://tutoriale-pe.net/algoritmul-lui-dijkstra-c/
  3.  * Rezolvare infoarena: http://www.infoarena.ro/problema/dijkstra
  4.  */
  5. #include    <iostream>
  6. #include    <fstream>
  7. #include    <queue>
  8. #include    <vector>
  9.  
  10. using namespace std;
  11.  
  12. ifstream fin("dijkstra.in");
  13. ofstream fout("dijkstra.out");
  14.  
  15. const int NMax = 50005;
  16. const int oo = (1 << 30);
  17.  
  18. int N, M;
  19. int D[NMax];
  20. bool InCoada[NMax];
  21.  
  22. vector < pair <int,int> > G[NMax];
  23.  
  24. struct compara
  25. {
  26.     bool operator()(int x, int y)
  27.     {
  28.         return D[x] > D[y];
  29.     }
  30. };
  31.  
  32. priority_queue<int, vector<int>, compara> Coada;
  33.  
  34. void Citeste()
  35. {
  36.     fin >> N >> M;
  37.     for(int i = 1; i <= M; i++)
  38.     {
  39.         int x, y, c;
  40.         fin >> x >> y >> c;
  41.         G[x].push_back(make_pair(y,c));
  42.     }
  43. }
  44.  
  45. void Dijkstra(int nodStart)
  46. {
  47.     for(int i = 1; i <= N; i++)
  48.         D[i] = oo;
  49.  
  50.     D[nodStart]=0;
  51.  
  52.     Coada.push(nodStart);
  53.     InCoada[nodStart] = true;
  54.  
  55.     while(!Coada.empty())
  56.     {
  57.         int nodCurent = Coada.top();
  58.         Coada.pop();
  59.  
  60.         InCoada[nodCurent] = false;
  61.         for(size_t i = 0; i < G[nodCurent].size(); i++)
  62.         {
  63.             int Vecin = G[nodCurent][i].first;
  64.             int Cost = G[nodCurent][i].second;
  65.             if(D[nodCurent] + Cost < D[Vecin])
  66.             {
  67.                 D[Vecin] = D[nodCurent] + Cost;
  68.                 if(InCoada[Vecin] == false)
  69.                 {
  70.                     Coada.push(Vecin);
  71.                     InCoada[Vecin] = true;
  72.                 }
  73.             }
  74.         }
  75.     }
  76. }
  77.  
  78. void Afiseaza()
  79. {
  80.     for(int i = 2; i <= N; i++)
  81.     {
  82.         if(D[i] != oo)
  83.             fout << D[i] << " ";
  84.         else
  85.             fout << "0 ";
  86.     }
  87. }
  88.  
  89. int main()
  90. {
  91.     Citeste();
  92.     Dijkstra(1);
  93.     Afiseaza();
  94. }
RAW Paste Data