Advertisement
Guest User

Untitled

a guest
Dec 20th, 2014
147
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.56 KB | None | 0 0
  1. void init()
  2. {
  3.     dis[1] = 0;
  4.     FOR(i,2,n)
  5.         dis[i] = INF;
  6. }
  7.  
  8. auto cmp = [&](int a, int b)->bool
  9. {
  10.     if(dis[a] == dis[b]) return a < b;
  11.     return dis[a] < dis[b];
  12. };
  13.  
  14. set<int, decltype(cmp)> Q(cmp);
  15.  
  16. void dijkstra()
  17. {
  18.     int u; //aktualny wierzcholek
  19.     while(!Q.empty())
  20.     {
  21.         u = *(Q.begin());
  22.         Q.erase(u);
  23.         for(Tunnel t : from[u])
  24.         {
  25.             if(dis[u] + t.cost < dis[t.to])
  26.             {
  27.                 dis[t.to] = dis[u] + t.cost;
  28.                 Q.insert(t.to);
  29.             }
  30.         }
  31.     }
  32. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement