Emiliatan

__Dijkstra

Jan 24th, 2019
169
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.24 KB | None | 0 0
  1. typedef long long int64;
  2. const int MAXE = 1000010, MAXV = 200001;
  3. const int64 INF=0x3f3f3f3f3f3f3f3f;
  4.  
  5. struct edge
  6. {
  7.     int to;
  8.     int64 wi;
  9.     int last;
  10.     edge(int to, int64 wi, int last):to(to), wi(wi), last(last){}
  11.     edge(){}
  12. };
  13. struct Heap
  14. {
  15.     int64 wi;
  16.     int node;
  17.     Heap(int64 wi,int node):wi(wi),node(node){}
  18.     Heap(){}
  19.     bool operator <(const Heap &rhs) const
  20.     {
  21.         return wi>rhs.wi;
  22.     }
  23. };
  24. struct __Dijkstra
  25. {
  26.     __Dijkstra(){}
  27.     edge e[MAXE];
  28.     int head[MAXE], head_point = 0;
  29.  
  30.     int64 dis[MAXV];
  31.     int V;
  32.     inline void addedge(int from, int to, int64 wi)
  33.     {
  34.         e[head_point] = edge(to, wi, head[from]);
  35.         head[from] = head_point++;
  36.     }
  37.  
  38.     inline void init()
  39.     {
  40.         memset(head, -1, sizeof(head));
  41.         head_point = 0;
  42.     }
  43.  
  44.     inline void shortest_path(int s)
  45.     {
  46.         memset(dis, 0x3f, sizeof(dis));
  47.         priority_queue<Heap> pq;
  48.         while(!pq.empty()) pq.pop();
  49.         dis[s] = 0;
  50.         pq.emplace(Heap(0, s));
  51.         Heap now;
  52.         while(!pq.empty())
  53.         {
  54.             now = pq.top(); pq.pop();
  55.  
  56.             if(dis[now.node] < now.wi) continue;
  57.             for(int i = head[now.node]; i != -1; i = e[i].last)
  58.             {
  59.                 int to = e[i].to;
  60.                 if(dis[to] > dis[now.node] + e[i].wi)
  61.                 {
  62.                     dis[to] = dis[now.node] + e[i].wi;
  63.                     pq.emplace(Heap(dis[to], to));
  64.                 }
  65.             }
  66.         }
  67.     }
  68.     inline void shortest_path(int s, int t)
  69.     {
  70.         memset(dis, 0x3f, sizeof(dis));
  71.         priority_queue<Heap> pq;
  72.         dis[s] = 0;
  73.         pq.emplace(Heap(dis[s], s));
  74.         Heap now;
  75.         while(!pq.empty())
  76.         {
  77.             now = pq.top(); pq.pop();
  78.             if(dis[now.node] < now.wi) continue;
  79.             if(now.node == t) return;
  80.             for(int i = head[now.node]; i != -1; i = e[i].last)
  81.             {
  82.                 int to = e[i].to;
  83.                 if(dis[to] > dis[now.node] + e[i].wi)
  84.                 {
  85.                     dis[to] = dis[now.node] + e[i].wi;
  86.                     pq.emplace(Heap(dis[to], to));
  87.                 }
  88.             }
  89.         }
  90.     }
  91.     inline void show_all_dis()
  92.     {
  93.         puts("show_all_dis()");
  94.         puts("############DEBUG###############");
  95.         for(int i=1;i<=V;i++)
  96.             printf("%d ",dis[i]);
  97.         puts("\n############DEBUG###############\n");
  98.     }
  99.     inline void show_single_dis(int i)
  100.     {
  101.         printf("show_single_dis(int %d)",i);
  102.         puts("############DEBUG###############");
  103.         printf("%d",dis[i]);
  104.         puts("\n############DEBUG###############\n");
  105.     }
  106. };
  107.  
  108. /**
  109. __Dijkstra dij;
  110.  
  111. dij.init();                 //you need to call this function first
  112. dij.V = v;                  //set the amount of the vertex
  113. for(...)
  114.     dij.addedge(ui,vi,ci);  //make Graph
  115.  
  116. dij.shortest_path(s);       //call this function to get the shortest paths
  117.                             //#from s
  118. dij.show_all_dis();         //DEBUG
  119.  
  120. dij.shortest_path(s,t);     //call this function to get the shortest paths
  121.                             //#from s to t
  122. dij.show_all_dis(ti);       //DEBUG
  123.  
  124. for(...)
  125.     print dij.dis[i];
  126. */
Advertisement
Add Comment
Please, Sign In to add comment