Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- typedef long long int64;
- const int MAXE = 1000010, MAXV = 200001;
- const int64 INF=0x3f3f3f3f3f3f3f3f;
- struct edge
- {
- int to;
- int64 wi;
- int last;
- edge(int to, int64 wi, int last):to(to), wi(wi), last(last){}
- edge(){}
- };
- struct Heap
- {
- int64 wi;
- int node;
- Heap(int64 wi,int node):wi(wi),node(node){}
- Heap(){}
- bool operator <(const Heap &rhs) const
- {
- return wi>rhs.wi;
- }
- };
- struct __Dijkstra
- {
- __Dijkstra(){}
- edge e[MAXE];
- int head[MAXE], head_point = 0;
- int64 dis[MAXV];
- int V;
- inline void addedge(int from, int to, int64 wi)
- {
- e[head_point] = edge(to, wi, head[from]);
- head[from] = head_point++;
- }
- inline void init()
- {
- memset(head, -1, sizeof(head));
- head_point = 0;
- }
- inline void shortest_path(int s)
- {
- memset(dis, 0x3f, sizeof(dis));
- priority_queue<Heap> pq;
- while(!pq.empty()) pq.pop();
- dis[s] = 0;
- pq.emplace(Heap(0, s));
- Heap now;
- while(!pq.empty())
- {
- now = pq.top(); pq.pop();
- if(dis[now.node] < now.wi) continue;
- for(int i = head[now.node]; i != -1; i = e[i].last)
- {
- int to = e[i].to;
- if(dis[to] > dis[now.node] + e[i].wi)
- {
- dis[to] = dis[now.node] + e[i].wi;
- pq.emplace(Heap(dis[to], to));
- }
- }
- }
- }
- inline void shortest_path(int s, int t)
- {
- memset(dis, 0x3f, sizeof(dis));
- priority_queue<Heap> pq;
- dis[s] = 0;
- pq.emplace(Heap(dis[s], s));
- Heap now;
- while(!pq.empty())
- {
- now = pq.top(); pq.pop();
- if(dis[now.node] < now.wi) continue;
- if(now.node == t) return;
- for(int i = head[now.node]; i != -1; i = e[i].last)
- {
- int to = e[i].to;
- if(dis[to] > dis[now.node] + e[i].wi)
- {
- dis[to] = dis[now.node] + e[i].wi;
- pq.emplace(Heap(dis[to], to));
- }
- }
- }
- }
- inline void show_all_dis()
- {
- puts("show_all_dis()");
- puts("############DEBUG###############");
- for(int i=1;i<=V;i++)
- printf("%d ",dis[i]);
- puts("\n############DEBUG###############\n");
- }
- inline void show_single_dis(int i)
- {
- printf("show_single_dis(int %d)",i);
- puts("############DEBUG###############");
- printf("%d",dis[i]);
- puts("\n############DEBUG###############\n");
- }
- };
- /**
- __Dijkstra dij;
- dij.init(); //you need to call this function first
- dij.V = v; //set the amount of the vertex
- for(...)
- dij.addedge(ui,vi,ci); //make Graph
- dij.shortest_path(s); //call this function to get the shortest paths
- //#from s
- dij.show_all_dis(); //DEBUG
- dij.shortest_path(s,t); //call this function to get the shortest paths
- //#from s to t
- dij.show_all_dis(ti); //DEBUG
- for(...)
- print dij.dis[i];
- */
Advertisement
Add Comment
Please, Sign In to add comment