最短路学习（复习）笔记

# Part 1 ### 前言 哇啊啊啊，已经$n$年没做最短路的题了，板子都不熟练了，所以要复习一下 # Part 2 板子 ### $Dijkstra$+堆优化 ``` void dijkstra(int s) { int i,x,y; memset(dis,0X3f,sizeof(dis)); memset(v,0,sizeof(v)); dis[s]=0; q.push(make_pair(0,s)); while (q.size()) { y=q.top().second; q.pop(); if (v[y]) continue; v[y]=true; for (i=las[y];i;i=nxt[i]) if (dis[y]+b[i]<dis[a[i]]) { dis[a[i]]=dis[y]+b[i]; q.push(make_pair(-dis[a[i]],a[i])); } } } ``` ### ~~死了的~~$SPFA$ ```pascal procedure spfa(s:longint); var l,r,x,i:longint; begin fillchar(dis,sizeof(dis),100); dis[s]:=0; l:=1; r:=1; q[1]:=s; while l<=r do begin x:=q[l]; i:=las[x]; while (i<>0) do begin if (dis[x]+b[i]<dis[a[i]]) then begin dis[a[i]]:=dis[x]+b[i]; inc(r); q[r]:=a[i]; end; i:=nxt[i]; end; inc(l); end; end; ``` # Part 3 ### SPFA的各种作用 #### 求负（正）环 ##### bfs ```cpp bool spfa() { int i,l,r,x; l=1; r=1; q[1]=1; dis[1]=0; while (l<=r) { //if (r>2*(n+m)) return true; 卡界 慎用 x=q[l]; for (i=las[x];i;i=nxt[i]) if (dis[x]+b[i]<dis[a[i]]) { dis[a[i]]=dis[x]+b[i]; ru[a[i]]++; if (ru[a[i]]>=n) { return true; } r++; q[r]=a[i]; } l++; } return false; } ``` ##### dfs ```cpp bool spfa(int u) { vis[u] = 1; for (i=las[x];i;i=nxt[i]) { int v = e[i].v; if (dis[v] > dis[u] + e[i].w) { if (vis[v]) return 1; dis[v] = dis[u] + e[i].w; if (dfs(v)) return 1; } } vis[u] = 0; return 0; } ``` # Part 4 ### 例题