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];
  16. bool InCoada[NMax];
  17.  
  18. vector < pair < int, int > > G[NMax];
  19.  
  20. struct ComparaDistante
  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;
  56.     Coada.push(nodStart);
  57.     InCoada[nodStart] = true;
  58.     while(!Coada.empty())
  59.     {
  60.         int nodCurent = Coada.top();
  61.         Coada.pop();
  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.                 {
  73.             Coada.push(Vecin);
  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. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top