原文地址
https://fmcraft.top/index.php/Programming/2025040402.html
主要算法
迪杰斯特拉Dijkstra
題目列表
P1：奶牛航線Cowroute
題目描述
題目描述
Bessie已經厭倦了農場冬天的寒冷氣候，她決定坐飛機去更溫暖的地方去度假。不幸的是，她發現只有Air Bovinia這一家航空公司愿意賣飛機票給牛，而且這家航空公司的飛機票的結構有些復雜。
Air Bovinia有N架飛機用來運營(1 <= N <= 1000)，每架飛機都只飛一條由兩個或者更多城市組成的特定航線。舉個例子，一架飛機的航線由1號城市開始，隨后飛去5號城市，接著飛去2號城市，最后到達8號城市。同一條航線中，同一座城市不會出現兩次。如果Bessie決定選擇乘坐一條航線，她可以在航線的任意城市登機，然后在這條航線后續的任意一個城市下飛機。每條航線都有一個確定的價格，Bessie如果乘坐了一條航線就必須支付全款，即使她只乘坐了這條航線的一小部分。如果Bessie乘坐了同一條航線多次，她每次都需要支付航線所需的費用。
Bessie想要找到從農夫John的農場(城市A)到她的目的地(城市B)的最便宜的飛行路線。請幫她計算出她最少需要多少錢，同時也請計算出她在花費最少的前提下，經過的城市的最少數量。
輸入
輸入的第一行包括三個用空格分離的整數A、B和N。表示出發和目的地城市的編號，和總的航班數。
接下來2N行描述航線信息。
每兩行第一行的兩個整數分別表示使用這條航線所需要的花費(范圍為區間1…1,000,000,000)。和航線所經過的城市數(范圍為區間1…100)。
第二行包含一個城市列表，依次表示航線沿途經過的城市(城市標號的范圍為1…1000)。
請注意，花費總和很容易就會超過32位整型。
輸出
輸出兩個以空格分離的整數，分別為從城市A到城市B所需要的最小花費，和在此前提下所需要經過城市的最少數量。m
如果無解，那么輸出"-1 -1“。(引號不用輸出)
樣例輸入 復制
3 4 3
3 5
1 2 3 4 5
2 3
3 5 4
1 2
1 5
樣例輸出 復制
2 2
提示
樣例說明
坐第2個航班，花費為2，經過5、4兩個城市
題解報告
本題存在錯誤，輸出樣例的第二個存在錯誤，所以標準程序中不輸出第二個答案
一、題目分析
Bessie 要從城市 A 前往城市 B 度假，Air Bovinia 航空公司有 N 條航線，每條航線由兩個或更多城市組成，同一航線中城市不會重復。Bessie 可以在航線的任意城市登機，在后續任意城市下機，且乘坐航線需支付全款，多次乘坐同航線需多次付費。我們的任務是幫 Bessie 找到從城市 A 到城市 B 的最便宜飛行路線，并計算在花費最少的前提下經過的最少城市數量，若無法到達則輸出 “-1 -1”。
二、算法思路
構建圖模型：
對于每條航線，將其拆分成多個邊。例如，若航線經過城市 a1, a2, …, an，則構建邊 (a1, a2), (a1, a3), …, (a1, an), (a2, a3), …, (a2, an), …, (an-1, an)，每條邊的權重為該航線的費用。這樣，我們就將航線信息轉化為了圖的鄰接關系。
使用 Dijkstra 算法求解：
Dijkstra 算法是一種用于計算圖中從一個源點到其他所有點的最短路徑的算法。在本題中，我們將源點設為城市 A，目標點為城市 B。
初始化距離數組 d，將所有城市的距離設為無窮大，將源點 A 的距離設為 0。
初始化標記數組 fl，用于標記城市是否已被訪問，初始時所有城市都未被訪問。
循環 n 次（n 為城市總數），每次找到距離最小且未被訪問的城市 fx。
遍歷 fx 的所有鄰接城市 sx，如果通過 fx 到達 sx 的距離比當前記錄的 sx 的距離更小，則更新 sx 的距離。
標記 fx 為已訪問。
處理輸出：
若最終 d[B] 仍為無窮大，說明無法從城市 A 到達城市 B，輸出 “-1 -1”；否則，輸出 d[B] 作為最小花費。
為了得到最少城市數量，我們可以在 Dijkstra 算法過程中記錄每個城市的前驅城市，最后從城市 B 回溯到城市 A 來計算經過的城市數量。但原代碼中未實現這部分功能，僅計算了最小花費。
標準程序
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1010;
int A,B,n,i,j,k,x,y,mi,sx,fx,sg,a[N],d[N],fl[N];
vector <int> f[N],g[N];
signed main(){cin>>A>>B>>n;for(i=1;i<=n;i++){cin>>x>>y;for(j=1;j<=y;j++) cin>>a[j];for(j=1;j<y;j++) for(k=j+1;k<=y;k++)f[a[j]].push_back(a[k]),g[a[j]].push_back(x);}for(n=1000,i=1;i<=n;i++) d[i]=1e18,fl[i]=1;d[A]=0;for(i=1;i<=n;i++){mi=1e18;for(j=1;j<=n;j++) if(d[j]<mi&&fl[j]) fx=j,mi=d[j];for(j=0;j<f[fx].size();j++){sx=f[fx][j];sg=g[fx][j];if(sg+d[fx]<d[sx]) d[sx]=d[fx]+sg;}fl[fx]=0;}cout<<(d[B]==1e18?-1:d[B]);
}
P2：架設電話線dd
題目描述
題目描述
在郊區有 N座通信基站，P條雙向電纜，第 i 條電纜連接基站 Ai和 Bi 。特別地，1 號基站是通信公司的總站，N 號基站位于一座農場中。現在，農場主希望對通信線路進行升級，其中升級第 i條電纜需要花費 Li 。
電話公司正在舉行優惠活動。農場主可以指定一條從 1號基站到 N 號基站的路徑，并指定路徑上不超過 K 條電纜，由電話公司免費提供升級服務。農場主只需要支付在該路徑上剩余的電纜中，升級價格最貴的那條電纜的花費即可。求至少用多少錢能完成升級。
一句話題意:在加權無向圖上求出一條從 1 號結點到 N號結點的路徑，使路徑上第 K+1 大的邊權盡量小。
輸入
第一行三個整數 N,P,K;
接下來 PP 行，每行三個整數 Ai,Bi,Li.
輸出
若不存在從 1到 N 的路徑，輸出 ?1。否則輸出所需最小費用。
樣例輸入 復制
5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6
樣例輸出 復制
4
提示
數據范圍：
0≤K<N≤1000,1≤P≤2000
題解報告
本題的目標是在加權無向圖上找到一條從 1 號結點到 N 號結點的路徑，使得路徑上第 K + 1 大的邊權盡量小。我們采用二分答案的方法來解決這個問題。
二分的范圍是邊權的取值范圍，這里邊權的最小值可能為 0（雖然題目中未明確提及邊權下限，但根據題意可合理推測），邊權的最大值在數據范圍給出的情況下最大為 1e9（因為后面代碼中有 w = 1e9 的設置）。
對于二分得到的每一個可能的邊權值 mid，我們通過一個基于優先隊列的廣度優先搜索（BFS）來判斷是否存在一條從 1 號基站到 N 號基站的路徑，使得路徑上大于 mid 的邊的數量不超過 k 條。如果存在這樣的路徑，說明當前的 mid 是一個可行解，我們可以繼續縮小上界來尋找更小的可行解；如果不存在這樣的路徑，說明當前的 mid 太小，我們需要增大下界。
總體流程就是：
首先讀取輸入的節點數量 n、邊的數量 m 和免費升級邊的最大數量 k。
然后讀取每條邊的信息（連接的兩個節點 x、y 和邊的權值 z），并將邊的信息存儲在鄰接表 f 和 g 中（f 存儲節點的鄰接關系，g 存儲對應的邊權）。
初始化二分的下界 t 為 0，上界 w 為 1e9，記錄答案的變量 bao 為 -1（表示初始時沒有找到可行解）。
進行二分查找，當 t 小于等于 w 時，計算中間值 mid。調用 pd(mid) 函數判斷 mid 是否為可行解。如果是，則更新答案 bao 為 mid，并將上界 w 更新為 mid - 1；否則將下界 t 更新為 mid + 1。
最后輸出答案 bao，如果最終 bao 仍然為 -1，則表示不存在從 1 到 N 的路徑，輸出 -1；否則輸出 bao，即所需的最小費用。
對于判斷函數：
該函數用于判斷對于給定的邊權值 x，是否存在一條從 1 號基站到 N 號基站的路徑，使得路徑上大于 x 的邊的數量不超過 k 條。
首先，清空優先隊列 q，并初始化距離數組 d 為一個很大的值（這里是 2e9），標記數組 fl 為 1（表示所有節點未被訪問過）。
將 1 號節點的距離設為 0，并將其加入優先隊列 q。
然后進入循環，從優先隊列中取出距離最小的節點 fx 及其距離 fb。如果該節點已經被訪問過（即 fl[fx] == 0），則跳過。
遍歷節點 fx 的所有鄰接節點 sx，計算 sg（如果鄰接邊的權值 g[fx][i] 大于 x，則 sg 為 1，否則為 0）。如果通過節點 fx 到達節點 sx 的距離（d[fx] + sg）小于原來記錄的節點 sx 的距離 d[sx]，則更新 d[sx]，并將節點 sx 及其新的距離加入優先隊列 q。
最后，判斷 d[n] 是否小于等于 k，如果是，則說明存在滿足條件的路徑，返回 true；否則返回 false。
標準程序
#include <bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m,k,i,x,y,z,t,w,mid,bao,d[N],fl[N];
vector <int> f[N],g[N];
priority_queue <pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
bool pd(int x){int fx,fb,sx,sg;while(!q.empty()) q.pop();for(i=1;i<=n;i++) d[i]=2e9,fl[i]=1;d[1]=0;q.push(make_pair(0,1));while(!q.empty()){fx=q.top().second;fb=q.top().first;q.pop();if(fl[fx]==0) continue;for(fl[fx]=i=0;i<f[fx].size();i++){sx=f[fx][i];sg=(g[fx][i]>x);if(d[fx]+sg<d[sx]) d[sx]=d[fx]+sg,q.push(make_pair(d[sx],sx));}}return d[n]<=k;
}
int main(){cin>>n>>m>>k;for(i=1;i<=m;i++) cin>>x>>y>>z,f[x].push_back(y),f[y].push_back(x),g[x].push_back(z),g[y].push_back(z);t=0;w=1e9;bao=-1;while(t<=w){mid=(t+w)/2;if(pd(mid)) bao=mid,w=mid-1;else t=mid+1;}cout<<bao;
}
P3：路障Roadblocks
題目描述
題目描述
貝茜把家搬到了一個小農場，但她常常回到 FJ 的農場去拜訪她的朋友。貝茜很喜歡路邊的風景，不想那么快地結束她的旅途，于是她每次回農場，都會選擇第二短的路徑，而不象我們所習慣的那樣，選擇最短路。
貝茜所在的鄉村有 R(1≤R≤10^5) 條雙向道路，每條路都連接了所有的 N(1≤N≤5000) 個農場中的某兩個。貝茜居住在農場 1，她的朋友們居住在農場 NN（即貝茜每次旅行的目的地）。
貝茜選擇的第二短的路徑中，可以包含任何一條在最短路中出現的道路，并且一條路可以重復走多次。當然第二短路的長度必須嚴格大于最短路（可能有多條）的長度，但它的長度必須不大于所有除最短路外的路徑的長度。
輸入
第1行為兩個整數，N和R，用空格隔開；
第 2…R+1行：每行包含三個用空格隔開的整數 A、B 和D，表示存在一條長度為 D(1≤D≤5000) 的路連接農場A和農場B。
輸出
輸出僅一個整數，表示從農場1到農場N的第二短路的長度。
樣例輸入 復制
4 4
1 2 100
2 4 200
2 3 250
3 4 100
樣例輸出 復制
450
提示
最短路：1→2→4（長度為 100+200=300）
第二短路：1→2→3→4（長度為4（長度為100+250+100=450$）
題解報告
本題的目標是找到從 1 號節點到 N 號節點的第二短路。我們可以使用 Dijkstra 算法的變形來解決這個問題。
步驟：
初始化距離數組 d1 和 d2，分別表示從 1 號節點到其他節點的最短距離和次短距離。將 d1 初始化為無窮大，d2 初始化為一個很大的值。
創建一個優先隊列 q，用于存儲節點及其到源節點的距離。將 1 號節點及其距離 0 加入優先隊列 q。
進行 Dijkstra 算法的迭代過程，每次從優先隊列中取出距離最小的節點 fx 及其距離 fy。
如果當前節點已經訪問過，則跳過。
遍歷當前節點的鄰接節點，計算 sg（如果鄰接邊的權值 g[fx][i] 大于 x，則 sg 為 1，否則為 0）。
如果通過當前節點到達鄰接節點的距離（fy + sg）小于 d1[sx]，則更新 d1[sx] 和 d2[sx]，并將鄰接節點及其新的距離加入優先隊列 q。
如果通過當前節點到達鄰接節點的距離（fy + sg）小于 d2[sx]，則更新 d2[sx]，并將鄰接節點及其新的距離加入優先隊列 q。
最后，輸出 d2[N]，即從 1 號節點到 N 號節點的第二短路的長度。
標準程序
#include <bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m,i,j,x,y,z,fx,fy,lfb,sx,sg,d1[N],d2[N];
vector <int> f[N],g[N];
priority_queue <pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
int main(){cin>>n>>m;for(i=1;i<=m;i++) cin>>x>>y>>z,f[x].push_back(y),f[y].push_back(x),g[x].push_back(z),g[y].push_back(z);for(i=1;i<=n;i++) d1[i]=d2[i]=2e9;d1[1]=0;q.push(make_pair(0,1));for(i=1;i<=5*n;i++){fx=q.top().second;fy=q.top().first;q.pop();for(j=0;j<f[fx].size();j++){sx=f[fx][j];sg=g[fx][j];x=fy+sg;if(x<d1[sx]) d2[sx]=d1[sx],d1[sx]=x;else if(x<d2[sx]) d2[sx]=x;q.push(make_pair(x,sx));}}cout<<d2[n];
}
P4：奶牛交通Traffic
題目描述
題目描述
農場中，由于奶牛數量的迅速增長，通往奶牛宿舍的道路也出現了嚴重的交通擁堵問題。約翰打算找出最忙碌的道路來重點整治。
這個牧區包括一個由M (1≤M≤50000)條單向道路組成的網絡，以及N(1≤N≤5000)個交叉路口，每一條道路連接兩個不同的交叉路口，奶牛宿舍位于第N個路口。每一條道路都由編號較小的路口通向編號較大的路口，這樣就可以避免網絡中出現環。顯而易見所有道路都通向奶牛宿舍。而兩個交叉路口可能由不止一條邊連接。
在準備睡覺的時候，所有奶牛都從他們各自所在的交叉路口走向奶牛宿舍。奶牛只會在入度為0的路口，且所有入度為0的路口都會有奶牛。
幫助約翰找出最忙碌的道路，即計算所有路徑中通過某條道路的最大次數，答案保證可以用32位整數存儲。
輸入
第1行:兩個用空格隔開的整數N和M.
第2…M+1行:每行兩個用空格隔開的整數a，b，表示一條道路從a到b。
輸出
一個整數，表示所有路徑中通過某條道路的最大次數。
樣例輸入 復制
7 7
1 3
3 4
3 5
4 6
2 3
5 6
樣例輸出 復制
4
提示
輸入說明:
通往奶牛宿舍的所有路徑(1 3 4 6 7 )( 1 3 5 6 7 )( 2 3 4 6 7 )( 2 3 5 6 7 )。
輸出說明:
以下是通往谷倉的四條可能路徑：
1 3 4 6 7
1 3 5 6 7
2 3 4 6 7
2 3 5 6 7
題解報告
本題的目標是找到所有路徑中通過某條道路的最大次數。我們可以使用拓撲排序和動態規劃的方法來解決這個問題。
本題要求找出最忙碌的路段，即所有路徑中通過某條道路的最大次數。我們可以使用拓撲排序來解決這個問題。
步驟：
初始化入度數組 join1 和 join2，分別表示每個節點的入度。
創建兩個隊列 q1 和 q2，用于存儲入度為 0 的節點。
遍歷所有節點，將入度為 0 的節點加入隊列 q1。
進行拓撲排序的迭代過程，每次從隊列 q1 中取出一個節點 fx，并將其加入隊列 q2。
遍歷當前節點的鄰接節點，計算 sg（如果鄰接邊的權值 g[fx][i] 大于 x，則 sg 為 1，否則為 0）。
如果通過當前節點到達鄰接節點的距離（fy + sg）小于 d1[sx]，則更新 d1[sx] 和 d2[sx]，并將鄰接節點及其新的距離加入優先隊列 q。
如果通過當前節點到達鄰接節點的距離（fy + sg）小于 d2[sx]，則更新 d2[sx]，并將鄰接節點及其新的距離加入優先隊列 q。
最后，輸出 d2[N]，即從 1 號節點到 N 號節點的第二短路的長度。
標準程序
#include <bits/stdc++.h>
using namespace std;
const int N=50010;
int i,j,n,m,x,y,fx,sx,ma,join1[N],join2[N],d1[N],d2[N];
vector <int> f[N],g[N];
queue <int> q;
int main(){cin>>n>>m;for(i=1;i<=m;i++) cin>>x>>y,f[x].push_back(y),join1[y]++,g[y].push_back(x),join2[x]++;for(i=1;i<=n;i++) if(join1[i]==0) q.push(i),d1[i]=1;while(!q.empty()){fx=q.front();q.pop();for(i=0;i<f[fx].size();i++){sx=f[fx][i];d1[sx]+=d1[fx];join1[sx]--;if(join1[sx]==0) q.push(sx);}}for(i=1;i<=n;i++) if(join2[i]==0) q.push(i),d2[i]=1;while(!q.empty()){fx=q.front();q.pop();for(i=0;i<g[fx].size();i++){sx=g[fx][i];d2[sx]+=d2[fx];join2[sx]--;if(join2[sx]==0) q.push(sx);}}for(i=1;i<=n;i++) for(j=0;j<f[i].size();j++)x=i,y=f[i][j],ma=max(ma,d1[x]*d2[y]);cout<<ma;
}
總結
通過以上四個問題的分析和解決，我們可以看到，圖論中的最短路徑問題在許多實際應用中都有廣泛的應用。通過使用 Dijkstra 算法、拓撲排序和動態規劃等方法，我們可以有效地解決這些問題。同時，這些問題的解決過程也讓我們更加深入地理解了圖論的基本概念和算法。
1. 最短路徑問題：最短路徑問題在計算機科學中，是指在給定圖中，從一個起點到終點的最短路徑問題。最短路徑問題在很多實際應用中都得到了廣泛的應用，如導航系統、網絡優化、路徑規劃等。解決最短路徑問題的關鍵是使用廣度優先搜索（BFS）或深度優先搜索（DFS）算法，或者使用動態規劃等方法。
2. 拓撲排序：拓撲排序是一種用于有向無環圖（DAG）的排序算法。在拓撲排序中，我們將圖中的節點按照它們之間的依賴關系進行排序。拓撲排序的應用非常廣泛，如任務調度、依賴分析等。
3. 動態規劃：動態規劃是一種通過將問題分解為子問題，并利用子問題的解來求解原問題的方法。在最短路徑問題中，我們可以使用動態規劃來求解最短路徑。動態規劃的核心思想是將問題分解為子問題，并利用子問題的解來求解原問題。
4. 二分查找：二分查找是一種在有序數組中查找目標元素的算法。在最短路徑問題中，我們可以使用二分查找來找到最短路徑。二分查找的核心思想是將問題分解為子問題，并利用子問題的解來求解原問題。
5. 優先隊列：優先隊列是一種特殊的隊列，它可以在 O(log n) 的時間復雜度內完成插入和刪除操作。在解決最短路徑問題時，我們可以使用優先隊列來存儲節點及其到源節點的距離，從而實現更高效的算法。
