c++ Dijkstra堆優化(Set)

因為蒟蒻太弱了，是以搞個普及組最短路卡了兩天，寫個随筆聊以紀念。

Dijkstra，圖論最短路算法基礎算法之一，也是從時間複雜度上來說較優的算法（不卡負權的情況下）。

正常樸素算法O(N^2)，起碼比隔壁Floyed強。。。

本着精益求精的精神，神犇們創造出了一種名為堆優化的東東。

有人可能問，SPFA不香嗎？

關于SPFA，它死了。。。

1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cmath>
 5 #include<set>
 6 #include<cstring>
 7 using namespace std;
 8 const int MAXN=1e5+5,MAXM=2e5+5;
 9 int n,m,s,cnt;
10 int head[MAXM],dis[MAXN];
11 bool vis[MAXN];
12 struct edge{
13     int to,dist,next; //to:指向的後續節點  dist:邊權    next:類指針操作
14     //不會的可以康康鍊式前向星講解 
15 }e[MAXM];
16 void addedge(int u,int v,int w){
17     e[cnt].to=v;
18     e[cnt].dist=w;
19     e[cnt].next=head[u];
20     head[u]=cnt++; //存圖 
21 }
22 typedef pair<int,int> PII; //偷懶。。。
23 //pair中，first=dis（邊權），second=pos （後續節點下标）
24 set<PII> heap; //建立一個set容器,其内部預設以first升序排列 
25 void Dijkstra(){
26     heap.insert(make_pair(0,s)); //存入初始節點 
27     dis[s]=0;
28     while(!heap.empty()){ //若容器為空，則說明無點可周遊 
29         PII tmp=*heap.begin(); //取最小邊進行更新 
30         heap.erase(heap.begin()); //删掉已經用過的最小邊 
31         int x=tmp.second; //下标 
32         vis[x]=1; //标記用過 
33         for(int i=head[x]; i!=-1; i=e[i].next){
34             int y=e[i].to; //以x為起點，挨個周遊連結清單中的後續節點 
35             if(!vis[y] && dis[x]+e[i].dist<dis[y]){ //沒走過，且可以更新 
36                 heap.erase(make_pair(dis[y],y)); //删掉原先不是最優的點 
37                 dis[y]=dis[x]+e[i].dist;
38                 heap.insert(make_pair(dis[y],y)); //加入已更優的點 
39                 // 先将對應的 pair 從堆中删除，再将更新後的 pair 插入堆
40             }
41         }
42     }
43 }
44 int main(){
45     ios::sync_with_stdio(false);
46     memset(head,-1,sizeof(head)); //初始化 
47     memset(dis,0x7f,sizeof(dis));
48     cin>>n>>m>>s;
49     for(int i=1; i<=m; i++){
50         int u,v,w;
51         cin>>u>>v>>w;
52         addedge(u,v,w);
53     }
54     Dijkstra();
55     for(int i=1; i<=n; i++) cout<<dis[i]<<" ";
56     return 0;
57 }