一、模板

1. Floyd

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e2+8;
const int INF=0x3f3f3f3f;
int n,m,dis[MAXN][MAXN];
int main(){cin>>n>>m;memset(dis,INF,sizeof(dis));for(int u=1;u<=n;u++)dis[u][u]=0;for(int i=1,u,v,w;i<=m;i++)cin>>u>>v>>w,dis[u][v]=min(dis[u][v],w);for(int k=1;k<=n;k++)for(int u=1;u<=n;u++)for(int v=1;v<=n;v++)dis[u][v]=min(dis[u][v],dis[u][k]+dis[k][v]);for(int u=1;u<=n;u++)for(int v=1;v<=n;v++)cout<<(dis[u][v]==INF?-1:dis[u][v])<<" \n"[v==n];return 0;
}

2. 01BFS

原題：求 $K$ 的所有非 $0$ 倍數中十進制表示下數碼和的最小值

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+8;
const int INF=0x3f3f3f3f;
int k,dis[MAXN];//除以k余數為x的數中最小的數碼和
int bfs(){deque<int>dque;dis[1]=1,dque.push_back(1);while(!dque.empty()){int x=dque.front(),nx;dque.pop_front();if(x==0)return dis[x];//代價為0的操作，放在隊首nx=x*10%k;//x后面直接加0，十進制數碼和不變，放在隊首if(dis[nx]>dis[x])dis[nx]=dis[x],dque.push_front(nx);//代價為1的操作，放在隊尾nx=(x+1)%k;//x+1和x的數碼和差1，放在隊尾if(dis[nx]>dis[x]+1)dis[nx]=dis[x]+1,dque.push_back(nx);}
}
int main(){cin>>k;memset(dis,INF,sizeof(dis));cout<<bfs();return 0;
}

3. SPFA

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+8;
const int INF=0x3f3f3f3f;
struct Edge{int v,w;};
int n,m,s,dis[MAXN];
bool in_que[MAXN];
vector<Edge>adj[MAXN];
void spfa(int s){queue<int>que;dis[s]=0,in_que[s]=true,que.push(s);while(!que.empty()){int u=que.front();in_que[u]=false,que.pop();for(auto[v,w]:adj[u])if(dis[v]>dis[u]+w){dis[v]=dis[u]+w;if(!in_que[v])in_que[v]=true,que.push(v);}}
}
int main(){cin>>n>>m>>s;for(int i=1,u,v,w;i<=m;i++)cin>>u>>v>>w,adj[u].push_back({v,w});memset(dis,INF,sizeof(dis));spfa(s);for(int i=1;i<=n;i++)cout<<(dis[i]==INF?INT32_MAX:dis[i])<<" ";return 0;
}

4. Dijkstra（弱化版）

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+8;
const int INF=0x3f3f3f3f;
struct Edge{int v,w;};
bool vis[MAXN];
int n,m,s,t,dis[MAXN];
vector<Edge>adj[MAXN];
void dijkstra(int s){dis[s]=0;for(int i=1;i<=n;i++){int u=0;for(int j=1;j<=n;j++)if(!vis[j]&&dis[j]<dis[u])u=j;if(!u)return;vis[u]=true;for(auto[v,w]:adj[u])if(!vis[v]&&dis[v]>dis[u]+w)dis[v]=dis[u]+w;}
}
int main(){cin>>n>>m>>s>>t;for(int i=1,u,v,w;i<=m;i++)cin>>u>>v>>w,adj[u].push_back({v,w}),adj[v].push_back({u,w});memset(dis,INF,sizeof(dis));dijkstra(s);cout<<dis[t];return 0;
}

5. Dijkstra（優化版）

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+8;
const int INF=0x3f3f3f3f;
struct Edge{int v,w;};
bool vis[MAXN];
int n,m,s,t,dis[MAXN];
vector<Edge>adj[MAXN];
void dijkstra(int s){//兩種方法均可，推薦沒有注釋的代碼priority_queue<pair<int,int> >pq;//{-dis[u],u}dis[s]=0,pq.push({0,s});while(!pq.empty()){auto u=pq.top().second;pq.pop();if(vis[u])continue;vis[u]=true;for(auto[v,w]:adj[u])if(dis[v]>dis[u]+w)dis[v]=dis[u]+w,pq.push({-dis[v],v});}// priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >pq;// dis[s]=0,pq.push({0,s});// while(!pq.empty()){//     auto[d,u]=pq.top();//     pq.pop();//     if(d>dis[u])continue;//     for(auto[v,w]:adj[u])//         if(dis[v]>dis[u]+w) {//             dis[v]=dis[u]+w;//             pq.push({dis[v],v});//         }// }
}
int main(){cin>>n>>m>>s;for(int i=1,u,v,w;i<=m;i++)cin>>u>>v>>w,adj[u].push_back({v,w});memset(dis,INF,sizeof(dis));dijkstra(s);for(int i=1;i<=n;i++)cout<<(dis[i]==INF?INT32_MAX:dis[i])<<" ";return 0;
}

二、例題

1. Floyd

1.1 傳送門

香蕉大學里有 $n$ 棟教學樓，有 $m$ 條雙向通行道路連接這些教學樓，不存在重邊和自環。每條道路都有一定的長度，而且所有教學樓之間都可以直接或者間接的通過道路到達。我們可以很容易的求出這些教學樓之間的最短路。
為了使交通更為順暢，校方決定在兩個教學樓里增設一對傳送門。傳送門可以將這對教學樓的距離直接縮短為 $0$。利用傳送門，某些教學樓之間的最短路的距離就變短了。
由于預算有限，學校里只能安裝一對傳送門。但是校長希望盡可能方便學生，使任意兩點之間的最短路長度的總和最小。當然啦，從 $x$ 教學樓到 $y$ 教學樓的長度和從 $y$ 教學樓到 $x$ 教學樓的長度只需要統計一次就可以了。

---

標準的一道暴力枚舉題。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e2+8;
const int INF=0x3f3f3f3f;
int n,m,dis[MAXN][MAXN];
int main(){cin>>n>>m;memset(dis,INF,sizeof(dis));for(int u=1;u<=n;u++)dis[u][u]=0;for(int i=1,u,v,w;i<=m;i++)cin>>u>>v>>w,dis[u][v]=dis[v][u]=min(dis[u][v],w);for(int k=1;k<=n;k++)for(int u=1;u<=n;u++)for(int v=1;v<=n;v++)dis[u][v]=min(dis[u][v],dis[u][k]+dis[k][v]);int ans=INF;for(int i=1;i<=n;i++)//枚舉傳送門端點Afor(int j=i+1;j<=n;j++){//枚舉傳送門端點Bint sum=0;//存儲安裝傳送門后所有點對的最短路總和for(int u=1;u<=n;u++)//枚舉所有起點計算最短路總和for(int v=u+1;v<=n;v++)//枚舉所有終點計算最短路總和   sum+=min({//因為i和j間有傳送門，視其距離為0dis[u][v],dis[u][i]+dis[j][v],dis[u][j]+dis[i][v]});ans=min(ans,sum);//每次更新答案到最小值}cout<<ans;return 0;
}

1.2 無向圖最小環

給定一個 $n$ 個點 $m$ 條帶正權邊且無重邊的無向圖，請輸出圖中簡單環的最小權值和。特別地，如果圖中沒有簡單環則輸出 "No Simple Cycle"。本題中的簡單環是指，不重復經過同一個點，且不重復經過同一條邊的環。

---

比較經典的一道松弛類型的題目。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e2+8;
const int INF=0x3f3f3f3f;
int t,dis[MAXN][MAXN],tmp[MAXN][MAXN];
int main(){cin>>t;while(t--){int n,m;cin>>n>>m;memset(dis,INF,sizeof(dis));memset(tmp,INF,sizeof(tmp));for(int u=1;u<=n;u++)dis[u][u]=tmp[u][u]=0;for(int j=1,u,v,w;j<=m;j++){cin>>u>>v>>w;dis[u][v]=dis[v][u]=min(dis[u][v],w);tmp[u][v]=tmp[v][u]=min(tmp[u][v],w);}int ans=INF;//最小環的權值和for(int k=1;k<=n;k++){//尋找所有i<k和j<k的通過k的形如i-j-k-i的環for(int i=1;i<k;i++)for(int j=i+1;j<k;j++)if(dis[i][j]!=INF&&tmp[j][k]!=INF&&tmp[k][i]!=INF)ans=min(ans,dis[i][j]+tmp[j][k]+tmp[k][i]);//使用tmp而非dis，防止重復頂點的出現for(int i=1;i<=n;i++)//用Floyd松弛for(int j=1;j<=n;j++)dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);}if(ans==INF)cout<<"No Simple Cycle\n";else cout<<ans<<"\n";}return 0;
}

1.3 災后重建

題目傳送門

---

由于題目保證每次輸入都是不下降的，考慮尋找已經重建好的村莊 $k$ 作為中轉站，以尋找兩村莊之間的最短路進行更新和輸出。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e2+8;
const int INF=0x3f3f3f3f;
int n,m,q,tms[MAXN],dis[MAXN][MAXN];
int main(){cin>>n>>m;memset(dis,INF,sizeof(dis));for(int u=0;u<n;u++)dis[u][u]=0;for(int i=0;i<n;i++)cin>>tms[i];for(int i=1,u,v,w;i<=m;i++)cin>>u>>v>>w,dis[u][v]=dis[v][u]=min(dis[u][v],w);cin>>q;for(int i=1,x,y,t,k=0;i<=q;i++){cin>>x>>y>>t;while(k<n&&tms[k]<=t){for(int u=0;u<n;u++)for(int v=0;v<n;v++)dis[u][v]=min(dis[u][v],dis[u][k]+dis[k][v]);k++;}if(tms[x]<=t&&tms[y]<=t&&dis[x][y]<INF)cout<<dis[x][y]<<"\n";else cout<<"-1\n";}return 0;
}

1.4 飛豬

給定一個 $n$ 個點 $m$ 條邊的邊帶權簡單連通無向圖，在 $0$ 時刻你在點 $1$ 上。
假設當前是 $t$ 時刻，你在點 $v$ 上，你可以選擇兩種操作：

• 仍停留在點 $v$ 上，操作后到 $t+1$ 時刻。
• 選擇一條邊 $(a,b,w)$ 滿足 $a=v$ 或 $b=v$，則你到這條邊連接的另一個點上，操作后到 $t+w$ 時刻。

有 $k$ 條信息，每一條信息形如 $(t_i,v_i)$ 表示在 $t_i$ 時刻，點 $v_i$ 上會出現一只飛豬，其編號為 $i$，若該時刻你在 $v_i$ 上，則你捕獲到了 $i$ 號飛豬。
現在你需要求出你能捕獲到的飛豬數量的最大值。

---

看到中間分的兩種情況可以立刻想到動態規劃的做法，再結合要從 $a$ 到達 $b$ 想到最短路。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e2+8;
const int MAXK=5e3+8;
const int INF=0x3f3f3f3f;
int n,m,k,dis[MAXN][MAXN],dp[MAXK];//dp[i]表示捕獲第i只飛豬時的最大飛豬數量
struct Pig{int t,idx;bool operator<(const Pig&rhs)const{return t<rhs.t;}
}pigs[MAXK];
int main(){cin>>n>>m>>k;memset(dis,INF,sizeof(dis));for(int u=1;u<=n;u++)dis[u][u]=0;for(int i=1,u,v,w;i<=m;i++)cin>>u>>v>>w,dis[u][v]=dis[v][u]=min(dis[u][v],w);for(int k=1;k<=n;k++)//Floydfor(int u=1;u<=n;u++)for(int v=1;v<=n;v++)dis[u][v]=min(dis[u][v],dis[u][k]+dis[k][v]);for(int i=1;i<=k;i++)cin>>pigs[i].t>>pigs[i].idx;sort(pigs+1,pigs+k+1);memset(dp,-INF,sizeof(dp));pigs[0].idx=1,dp[0]=0;//0時刻在節點1（初始位置）捕獲0只飛豬for(int i=1;i<=k;i++)//遍歷每只飛豬ifor(int j=0;j<i;j++)//嘗試從之前的飛豬j轉移過來if(pigs[j].t+dis[pigs[j].idx][pigs[i].idx]<=pigs[i].t)//從j的時間和位置，能否在i出現前到達i的位置dp[i]=max(dp[i],dp[j]+1);//若可達，則更新dp[i]為捕獲j后再捕獲i的數量int ans=0;for(int i=1;i<=k;i++)ans=max(ans,dp[i]);cout<<ans;return 0;
}

2. 01BFS

2.1 Kathiresan

Kathiresan 被關在一個高度戒備的矩形監獄中的單元格 $(0,0)$。他必須到達 $(R?1,C?1)$ 處的大門才能逃出監獄。Kathiresan 可以從任何單元格移動到其四個相鄰單元格之一，如果 Kathiresan 當前位于 $(x_1,y_1)$，那么他可以移動到 $(x_2,y_2)$ 當且僅當它們的曼哈距離為 $1$ 且 $0\le x_2<R$ 且 $0\le y2<C$。Kathiresan 設法獲得了監獄的地圖。如果 ${\text{map}}_{x_1,y_1}={\text{map}}_{x_2,y_2}$，則 Kathiresan 可以從 $(x_1,y_1)$ 移動到 $(x_2,y_2)$ 而不打暈任何守衛。如果 ${\text{map}}_{x_1,y_1}\ne {\text{map}}_{x_2,y_2}$，則 Kathiresan 可以通過打暈一名守衛從 $(x_1,y_1)$ 移動到 $(x_2,y_2)$。給定監獄的地圖，找出為了逃出監獄，Kathiresan必須打暈的最少守衛數量。

---

顯然，代價為 $0$ 的操作是直接移動，代價為 $1$ 的操作是打倒一名守衛然后移動。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e3+8;
const int INF=0x3f3f3f3f;
const int dx[]={1,0,-1,0};
const int dy[]={0,1,0,-1};
int t,n,m,dis[MAXN][MAXN],grid[MAXN][MAXN];//dis:到每個單元格的最小代價
int bfs(int sx,int sy){deque<pair<int,int> >dque;dis[sx][sy]=0,dque.push_back({sx,sy});while(!dque.empty()){auto[x,y]=dque.front();dque.pop_front();if(x==n&&y==m)return dis[n][m];for(int i=0;i<4;i++){int nx=x+dx[i],ny=y+dy[i],w=grid[nx][ny]!=grid[x][y];if(grid[nx][ny]==-1||dis[nx][ny]<=dis[x][y]+w)continue;//如果超出地圖或者該格有當前最優解dis[nx][ny]=dis[x][y]+w;//保證隊列始終按距離排序，先處理距離近的單元格w?dque.push_back({nx,ny}):dque.push_front({nx,ny});}}
}
int main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>t;while(t--){memset(dis,INF,sizeof(dis));memset(grid,-1,sizeof(grid));cin>>n>>m;char ch;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>ch,grid[i][j]=ch;cout<<bfs(1,1)<<"\n";}return 0;
}

2.2 障礙路線

考慮一個 $N\times N$（$1\le N\le 100$）的由一個個方格組成的正方形牧場。有些方格是奶牛們不能踏上的，它們被標記為了 'x'。例如下圖：

. . B x .
. x x A .
. . . x .
. x . . .
. . x . .

貝茜發現自己恰好在點 $A$ 處，她想去 $B$ 處的舔鹽塊。但是奶牛是一種緩慢而且笨拙的動物，十分討厭轉彎。盡管如此，必要的時候她們還是會轉彎的。對于一個給定的牧場，請你計算從 $A$ 到 $B$ 最少的轉彎次數。開始的時候，貝茜可以面對任意一個方向，并且貝茜知道她一定可以到達 $B$ 處。

---

遇到轉彎類題目一定要把 dis 數組多開一個方向維度。可以發現，代價為 $0$ 的操作是不轉彎，代價為 $1$ 的操作是轉彎。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e2+8;
const int INF=0x3f3f3f3f;
const int dx[]={-1,0,1,0};
const int dy[]={0,1,0,-1};
int n,sx,sy,ex,ey,grid[MAXN][MAXN],dis[MAXN][MAXN][5];
int bfs(int sx,int sy){deque<tuple<int,int,int> >dque;for(int i=0;i<4;i++)dis[sx][sy][i]=0,dque.push_back({sx,sy,i});while(!dque.empty()){auto[x,y,dir]=dque.front();dque.pop_front();if(x==ex&&y==ey)return dis[x][y][dir];for(int i=0;i<4;i++){int nx=x+dx[i],ny=y+dy[i],w=i!=dir;if(grid[nx][ny]<0||dis[nx][ny][i]<=dis[x][y][dir]+w)continue;dis[nx][ny][i]=dis[x][y][dir]+w;w?dque.push_back({nx,ny,i}):dque.push_front({nx,ny,i});}}
}
int main(){memset(dis,INF,sizeof(dis));memset(grid,-1,sizeof(grid));cin>>n;char ch;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){cin>>ch;if(ch=='.')grid[i][j]=0;if(ch=='A')sx=i,sy=j,grid[i][j]=0;if(ch=='B')ex=i,ey=j,grid[i][j]=0;}cout<<bfs(sx,sy);return 0;
}

2.3 奇妙的棋盤

小猴在玩一個神奇的游戲，游戲中給出了一個 $n\times m$ 的棋盤，棋盤中的格子有的黑，有的白。我們每次可以選擇任意一個格子進行操作，然后這個格子和所有與它顏色相同的相鄰的同色連通塊中的所有格子的顏色全部取反。小猴想知道至少需要多少次操作可以使所有格子變成白色。

---

代價為 $0$ 的操作顯然是相鄰格子顏色相同，而代價為 $1$ 則是相鄰格子顏色不同。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e2+8;
const int INF=0x3f3f3f3f;
const int dx[]={1,0,-1,0};
const int dy[]={0,1,0,-1};
int n,m,col[MAXN][MAXN],dis[MAXN][MAXN];
//col:存儲格子顏色 1黑0白
//dis:到達(x,y)所需的最少操作次數
int bfs(int sx,int sy){deque<pair<int,int> >dque;dis[sx][sy]=0,dque.push_back({sx,sy});int ret=0;//記錄最終需要的最少操作次數while(!dque.empty()){auto[x,y]=dque.front();dque.pop_front();//更新處理到該位置時累計需要的操作次數ret=max(ret,dis[x][y]+col[x][y]);//(x,y)是黑色說明要翻轉一次，否則不用翻轉for(int i=0;i<4;i++){int nx=x+dx[i],ny=y+dy[i],w=col[nx][ny]!=col[x][y];if(col[x][y]<0||dis[nx][ny]<=dis[x][y]+w)continue;dis[nx][ny]=dis[x][y]+w;//更新到達新位置的操作次數w?dque.push_back({nx,ny}):dque.push_front({nx,ny});}}return ret;
}
int main(){cin>>n>>m;memset(col,-1,sizeof(col));char ch;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>ch,col[i][j]=ch=='B';int ans=INF;for(int x=1;x<=n;x++)for(int y=1;y<=m;y++)if(col[x][y]!=col[x-1][y]&&col[x][y]!=col[x][y-1])memset(dis,INF,sizeof(dis)),ans=min(ans,bfs(x,y));cout<<ans;return 0;
}

3. SPFA

3.1 奶牛派對

寒假到了，$n$ 頭牛都要去參加一場在編號為 $x$ 的牛的農場舉行的派對，農場之間有 $m$ 條有向路，每條路都有一定的長度。每頭牛參加完派對后都必須回家，無論是去參加派對還是回家，每頭牛都會選擇最短路徑，求這 $n$ 頭牛的最短路徑（一個來回）中最長的一條路徑長度。

---

按照樸素寫法，我們可以先計算出 $n?1$ 個結點到 $x$ 的最短距離，然后再計算出 $x$ 到 $n?1$ 個結點的最短距離。時間復雜度 $O(nkm+km)$，顯然會超時。

考慮反向圖優化。由于一個結點 $a$ 到 $b$ 的反向圖搜索最短路就相當于 $b$ 到 $a$ 的正向圖搜索最短路。這樣在主函數中，可以只搜索兩次，都以派對作為起點進行搜索。時間復雜度 $O(2km)$，不會超時。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e3+8;
const int INF=0x3f3f3f3f;
struct Edge{int v,w;};
bool in_que[MAXN];
vector<Edge>adj[2][MAXN];
int n,m,x,dis[MAXN],ans[MAXN];
void spfa(int s,int rev){queue<int>que;dis[s]=0,in_que[s]=true,que.push(s);while(!que.empty()){int u=que.front();in_que[u]=false,que.pop();for(auto[v,w]:adj[rev][u])if(dis[v]>dis[u]+w){dis[v]=dis[u]+w;if(!in_que[v])in_que[v]=true,que.push(v);}}
}
int main(){cin>>n>>m>>x;for(int i=1,u,v,w;i<=m;i++)cin>>u>>v>>w,adj[0][u].push_back({v,w}),adj[1][v].push_back({u,w});memset(dis,INF,sizeof(dis));spfa(x,0);//第一次計算所有奶牛從派對回家的最短路for(int i=1;i<=n;i++)ans[i]=dis[i];memset(dis,INF,sizeof(dis));spfa(x,1);//第二次計算所有奶牛從家去派對的最短路int mx=0;for(int i=1;i<=n;i++)ans[i]+=dis[i],mx=max(mx,ans[i]);cout<<mx;return 0;
}

3.2 營救

媽媽下班回家，街坊鄰居說小明被一群陌生人強行押上了警車！媽媽豐富的經驗告訴她小明被帶到了 $t$ 區，而自己在 $s$ 區。該市有 $m$ 條大道連接 $n$ 個區，一條大道將兩個區相連接，每個大道有一個擁擠度。小明的媽媽雖然很著急，但是不愿意擁擠的人潮沖亂了她優雅的步伐。所以請你幫她規劃一條從 $s$ 至 $t$ 的路線，使得經過道路的擁擠度最大值最小。

---

SPFA 的變種，賊水。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e4+8;
const int INF=0x3f3f3f3f;
struct Edge{int v,w;};
int n,m,s,t,dis[MAXN];
bool in_que[MAXN];
vector<Edge>adj[MAXN];
void spfa(int s){queue<int>que;dis[s]=0,in_que[s]=true,que.push(s);while(!que.empty()){int u=que.front();in_que[u]=false,que.pop();for(auto[v,w]:adj[u])if(dis[v]>max(dis[u],w)){dis[v]=max(dis[u],w);if(!in_que[v])in_que[v]=true,que.push(v);}}
}
int main(){cin>>n>>m>>s>>t;for(int i=1,u,v,w;i<=m;i++)cin>>u>>v>>w,adj[u].push_back({v,w}),adj[v].push_back({u,w});memset(dis,INF,sizeof(dis));spfa(s);cout<<dis[t];return 0;
}

3.3 航空路線

Bessie 對她農場那寒冷的天氣感到厭煩，于是她準備坐飛機到一個更溫暖的地方度假。不幸的是，她發現只有一個航空公司：Air Bovinia，愿意賣票給牛……并且這些票的結構有些復雜。Air Bovinia 擁有 $N$（$1\le N\le 1000$）條航線，每條航線都經過兩個及以上的城市。舉個例子：某航線的一次航班可以從城市 $1$ 出發，然后飛往城市 $5$，再飛到城市 $2$，最后飛到城市 $8$。任何城市都不會在同一條航線上出現多次。如果 Bessie 選擇了一條航線，那么她可以從航線上的任意一個城市上飛機，然后在途中任意一個城市下飛機。她不必從航線的起點上飛機，再從航線的終點下飛機。每條航線都有一個確定的花費，只要它搭乘了這個航班，她就必須支付這個航班的全額花費，不論她途經了幾個城市。如果 Bessie 多次搭乘了某個航班，那么每次搭乘 Bessie 都必須支付航班的花費。Bessie 想要找到從她農場所在的城市（城市 $A$）到她目的地所在城市（城市 $B$）最便宜的路線。請你告訴她最少要花多少錢，并告訴她在此基礎上她最少經過多少個城市（坐飛機經過也算）。

---

抓住最后要求的重點：（1）要花多少錢；（2）要最少經過多少個城市。顯然這是多關鍵字排序的經典題目。多關鍵字排序，即先比較第一關鍵字（錢數），若第一關鍵字相同，則比較第二關鍵字（城市數）。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e4+8;
const int MAXL=1e2+8;
const long long INF=0x3f3f3f3f3f3f3f3f;
struct Edge{int v;long long w1,w2;//w1:花費 w2:經過城市個數
};
bool in_que[MAXN];
long long dis[MAXN];
vector<Edge>adj[MAXN];
int n,s,t,cty[MAXL],sum[MAXN];
/*** cty[]: 每次航班的花費* dis[]: 起點到每個城市的最小花費* sum[]: 起點到每個城市的最少經過城市數量
**/
void spfa(int s){queue<int>que;dis[s]=0,sum[s]=0,in_que[s]=true,que.push(s);while(!que.empty()){int u=que.front();in_que[u]=false,que.pop();for(auto[v,w1,w2]:adj[u])if(dis[v]>dis[u]+w1||(dis[v]==dis[u]+w1&&sum[v]>sum[u]+w2)){//按照關鍵字優先級更新dis[v]=dis[u]+w1,sum[v]=sum[u]+w2;if(!in_que[v])in_que[v]=true,que.push(v);}}
}
int main(){cin>>s>>t>>n;for(int i=1,c,m;i<=n;i++){cin>>c>>m;for(int j=1;j<=m;j++){cin>>cty[j];for(int k=1;k<j;k++)adj[cty[k]].push_back({cty[j],c,j-k});}}memset(dis,INF,sizeof(dis));spfa(s);if(dis[t]>=INF)cout<<"-1 -1";else cout<<dis[t]<<" "<<sum[t];return 0;
}

3.4 牛奶管道

農民約翰的農場有一套老舊的管網，管網由 $M$ 條管道（$1\le M\le 500$）構成，用于將牛奶從谷倉運到儲奶罐。他想在明年移除和更新大部分管道，但他想原封不動地保留一條完整的路徑，這樣他仍然可以把牛奶從谷倉輸送到儲罐。管網由 $N$ 個節點（$1\le N\le 500$）組成，每個點都可以作為一組管道的端點。結點 $1$ 是谷倉，結點 $N$ 是儲罐。$M$ 條雙向管道中的每一條都連接一對節點，并且都有一個延遲值（牛奶達到管的另一端的用時）和容量值（單位時間內可以穩定通過管道的牛奶量）。多條管道可以連接同一對節點。對于一條連接谷倉與儲罐的路徑，路徑的延遲等于沿途所有管道的延遲之和，路徑的容量等于沿途管道最小的容量(因為這是制約牛奶運送的“瓶頸”)。如果約翰通過一條延遲為 $L$、容量為 $C$ 的管道運送 $X$ 個單位的牛奶，需要的時間為 $L+\frac{X}{C}$。給出約翰的管網結構，請幫助他選擇一條路徑，使得他從谷倉到儲罐運送 $X$ 個單位牛奶的總時間最少。

---

SPFA 變形。原汁原味，十分經典。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+8;
const int INF=0x3f3f3f3f;
struct Edge{int v,l,c;};
bool in_que[MAXN];
vector<Edge>adj[MAXN];
int n,m,x,dis[MAXN],lmts[MAXN];
//dis[]:起點到各節點的最小延遲總和
//lmts[]:所有管道的容量
void spfa(int s,int lmt){queue<int>que;dis[s]=0,in_que[s]=true,que.push(s);while(!que.empty()){int u=que.front();in_que[u]=false,que.pop();for(auto[v,l,c]:adj[u])if(c>=lmt&&dis[v]>dis[u]+l){//可以通過且時間更短dis[v]=dis[u]+l;if(!in_que[v])in_que[v]=true,que.push(v);}}
}
int main(){cin>>n>>m>>x;for(int i=1,u,v,l,c;i<=m;i++){cin>>u>>v>>l>>c;adj[u].push_back({v,l,c});adj[v].push_back({u,l,c});lmts[i]=c;}int ans=INF;for(int i=1;i<=m;i++){memset(dis,INF,sizeof(dis));memset(in_que,false,sizeof(in_que));spfa(1,lmts[i]);ans=min(ans,dis[n]+x/lmts[i]);}cout<<ans;return 0;
}

4. Dijkstra

4.1 路徑統計

“RP餐廳”（？）的員工素質就是不一般，在齊刷刷的算出同一個電話號碼之后，就準備讓 HZH，TZY 去送快餐了，他們將自己居住的城市畫了一張地圖，已知在他們的地圖上，有 $N$ 個地方，而且他們目前處在標注為 $1$ 的小鎮上，而送餐的地點在標注為 $N$ 的小鎮。除此之外還知道這些道路都是單向的，從小鎮 $I$ 到 $J$ 需要花費 D[I,J] 的時間，為了更高效快捷的將快餐送到顧客手中，他們想走一條從小鎮 $1$ 到小鎮 $N$ 花費最少的一條路，但是他們臨出發前，撞到因為在路上堵車而生氣的 FYY，深受啟發，不能僅知道一條路線，萬一…于是，他們邀請 FYY 一起來研究起了下一個問題：這個最少花費的路徑有多少條？

---

顯然，我們需要新開一個數組 cnt[] 來存儲從起點到每個節點的最短路徑的數量（即輸出的第二個數據）。然后分兩種情況：

• 情況 1：發現一條更短的路徑到達節點 $v$（即 dis[v]>dis[u]+w）
  • 更新 dis[v] 為新的最短距離。
  • 重置 cnt[v]=cnt[u]（因為到達 $v$ 的最短路徑現在只能通過 $u$ 實現，路徑數量與到達 $u$ 的數量相同）。
• 情況 2：當發現一條與當前最短路徑等長的路徑（即 dis[v]=dis[u]+w）
  • 累加 cnt[v]+=cnt[u]（到達 $v$ 的最短路徑又多了 cnt[u] 條，這些路徑是通過 $u$ 到達 $v$ 的）。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+8;
const int INF=0x3f3f3f3f;
struct Edge{int v,w;};
bool vis[MAXN];
vector<Edge>adj[MAXN];
int n,m,dis[MAXN],cnt[MAXN];
void dijkstra(int s){priority_queue<pair<int,int> >pq;dis[s]=0,cnt[s]=1,pq.push({0,s});while(!pq.empty()){auto u=pq.top().second;pq.pop();if(vis[u])continue;vis[u]=true;for(auto[v,w]:adj[u])if(dis[v]>dis[u]+w)dis[v]=dis[u]+w,cnt[v]=cnt[u],pq.push({-dis[v],v});else if(dis[v]==dis[u]+w)cnt[v]+=cnt[u];}
}
int main(){cin>>n>>m;for(int i=1,u,v,w;i<=m;i++)cin>>u>>v>>w,adj[u].push_back({v,w});memset(dis,INF,sizeof(dis));dijkstra(1);if(dis[n]==INF)cout<<"No answer";else cout<<dis[n]<<" "<<cnt[n];return 0;
}

4.2 平面上的點

給定平面上的 $n$ 個點，定義 $(x_1,y_1)\to (x_2,y_2)$ 的費用為它們的最小距離分量，求從 $1$ 號點走到 $n$ 號點的最小費用。

---

很顯然，有一個 $O(n^2)$ 的建圖方法：

for(int u=1;u<=n;u++)for(int v=u+1;v<=n;v++){adj[u].push_back({v,min(abs(p[u].x-p[v].x),abs(p[u].y-p[v].y))});adj[v].push_back({u,min(abs(p[u].x-p[v].x),abs(p[u].y-p[v].y))});}

但可以考慮投影優化。

首先，將平面上的點 $(x,y)$ 投射到 $x$ 軸上，得到投影點 $(x,0)$，兩點的 $x$ 軸投影距離為 $|x_1?x_2|$（即橫向距離）；然后，將平面上的點 $(x,y)$ 投射到 $y$ 軸上，得到投影點 $(0,y)$，兩點的 $y$ 軸投影距離為 $|y_1?y_2|$（即縱向距離）。

接下來，利用投影的相鄰性質，即在同一投影軸上（如 $x$ 軸），任意兩個非相鄰投影點的距離，等于它們之間所有相鄰投影點的距離之和。

然后，再利用 Dijkstra 等其他最短路算法的性質，我們知道，每次在計算起點到當前節點的距離的時候，都會處理出真正的最短距離。因此我們只需要把 $|x_1?x_2|$ 和 $|y_1?y_2|$ 一起放入鄰接矩陣即可。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+8;
const int INF=0x3f3f3f3f;
struct Edge{int v,w;};
struct Point{int x,y,idx;}p[MAXN];
bool vis[MAXN];
int n,m,s,t,dis[MAXN];
vector<Edge>adj[MAXN];
bool cmpx(Point p1,Point p2){return p1.x<p2.x;}
bool cmpy(Point p1,Point p2){return p1.y<p2.y;}
void dijkstra(int s){priority_queue<pair<int,int> >pq;//{-dis[u],u}dis[s]=0,pq.push({0,s});while(!pq.empty()){auto u=pq.top().second;pq.pop();if(vis[u])continue;vis[u]=true;for(auto[v,w]:adj[u])if(dis[v]>dis[u]+w)dis[v]=dis[u]+w,pq.push({-dis[v],v});}
}
int main(){cin>>n;for(int i=1;i<=n;i++)cin>>p[i].x>>p[i].y,p[i].idx=i;sort(p+1,p+n+1,cmpx);for(int i=1;i<n;i++){adj[p[i].idx].push_back({p[i+1].idx,p[i+1].x-p[i].x});adj[p[i+1].idx].push_back({p[i].idx,p[i+1].x-p[i].x});}sort(p+1,p+n+1,cmpy);for(int i=1;i<n;i++){adj[p[i].idx].push_back({p[i+1].idx,p[i+1].y-p[i].y});adj[p[i+1].idx].push_back({p[i].idx,p[i+1].y-p[i].y});}memset(dis,INF,sizeof(dis));dijkstra(1);cout<<dis[n];return 0;
}

4.3 邀請函

在電視時代，沒有多少人觀看戲劇表演。 劇場老板意識到了這一事實，他想宣傳劇院，尤其是古典的喜劇片。
他已經打印了邀請函和所有必要的信息和計劃。許多學生被雇來分發這些邀請函。每個學生被指定了一個確切的公共汽車站，他或她將留在那里一整天，邀請人們觀看戲劇表演。
這里的公交系統是非常特殊的：共有 $n$ 個站點和 $m$ 個線路，所有的線路都是單向的，連接兩個站點。公共汽車離開起始點，到達目的地之后又空車返回起始點。
學生每天早上從總部所在的 $1$ 號站點出發，乘公交車到一個預定的站點邀請乘客。每個站點都被安排了一名學生。在一天結束的時候，所有的學生都回到總部。現在需要知道的是，學生所需的公交費用的總和最小是多少。

---

見 3.1 奶牛派對（就在本篇博客）。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+8;
const int INF=0x3f3f3f3f;
struct Edge{int v,w;};
bool vis[MAXN];
vector<Edge>adj[2][MAXN];
int n,m,dis[MAXN],ans[MAXN];
void dijkstra(int s,int rev){memset(dis,INF,sizeof(dis));memset(vis,false,sizeof(vis));priority_queue<pair<int,int> >pq;dis[s]=0,pq.push({0,s});while(!pq.empty()){auto u=pq.top().second;pq.pop();if(vis[u])continue;vis[u]=true;for(auto[v,w]:adj[rev][u])if(dis[v]>dis[u]+w)dis[v]=dis[u]+w,pq.push({-dis[v],v});}
}
int main(){cin>>n>>m;for(int i=1,u,v,w;i<=m;i++)cin>>u>>v>>w,adj[0][u].push_back({v,w}),adj[1][v].push_back({u,w});dijkstra(1,0);for(int i=1;i<=n;i++)ans[i]=dis[i];dijkstra(1,1);long long ret=0;for(int i=1;i<=n;i++)ans[i]+=dis[i],ret+=ans[i];cout<<ret;return 0;
}