1. 單源最短路
單一邊權 BFS
原理：由于邊權為單一值，可使用廣度優先搜索（BFS）來求解最短路。BFS 會逐層擴展節點，由于邊權相同，第一次到達某個節點時的路徑長度就是最短路徑長度。
用法：適用于邊權都為 1 的圖，可快速求出從源點到其他所有節點的最短路徑。
代碼：
#include?<iostream>#include?<queue>#include?<vector>using?namespace?std;
const?int?MAXN =?100005;
vector<int>?adj[MAXN];int?dist[MAXN];
void?bfs(int?s)?{
????queue<int>?q;
????fill(dist,?dist +?MAXN,?-1);
????dist[s]?=?0;
????q.push(s);
????while?(!q.empty())?{
????????int?u =?q.front();
????????q.pop();
????????for?(int?v :?adj[u])?{
????????????if?(dist[v]?==?-1)?{
????????????????dist[v]?=?dist[u]?+?1;
????????????????q.push(v);
????????????}
????????}
????}}
int?main()?{
????int?n,?m,?s;
????cin >>?n >>?m >>?s;
????for?(int?i =?0;?i <?m;?i++)?{
????????int?u,?v;
????????cin >>?u >>?v;
????????adj[u].push_back(v);
????????adj[v].push_back(u);
????}
????bfs(s);
????for?(int?i =?1;?i <=?n;?i++)?{
????????cout <<?dist[i]?<<?" ";
????}
????cout <<?endl;
????return?0;
}
0 - 1 邊權雙端隊列 BFS
原理：使用雙端隊列來優化 BFS 過程。對于邊權為 0 的邊，將其終點插入隊頭；對于邊權為 1 的邊，將其終點插入隊尾。這樣能保證隊列中元素的距離是單調遞增的。
用法：適用于圖中邊權只有 0 和 1 的情況。
代碼：
#include?<iostream>#include?<deque>#include?<vector>using?namespace?std;
const?int?MAXN =?100005;
vector<pair<int,?int>>?adj[MAXN];int?dist[MAXN];
void?bfs_01(int?s)?{
????deque<int>?q;
????fill(dist,?dist +?MAXN,?-1);
????dist[s]?=?0;
????q.push_back(s);
????while?(!q.empty())?{
????????int?u =?q.front();
????????q.pop_front();
????????for?(auto?[v,?w]?:?adj[u])?{
????????????if?(dist[v]?==?-1)?{
????????????????dist[v]?=?dist[u]?+?w;
????????????????if?(w ==?0)?{
????????????????????q.push_front(v);
????????????????}?else?{
????????????????????q.push_back(v);
????????????????}
????????????}
????????}
????}}
int?main()?{
????int?n,?m,?s;
????cin >>?n >>?m >>?s;
????for?(int?i =?0;?i <?m;?i++)?{
????????int?u,?v,?w;
????????cin >>?u >>?v >>?w;
????????adj[u].emplace_back(v,?w);
????????adj[v].emplace_back(u,?w);
????}
????bfs_01(s);
????for?(int?i =?1;?i <=?n;?i++)?{
????????cout <<?dist[i]?<<?" ";
????}
????cout <<?endl;
????return?0;
}
樸素迪杰斯特拉
原理：通過貪心策略，每次從未確定最短路徑的節點中選擇距離源點最近的節點，然后以該節點為中間點更新其他節點的距離。
用法：適用于邊權非負且節點數較少的圖，時間復雜度為?O(V2)稠密圖。
代碼：
#include?<iostream>#include?<vector>#include?<climits>using?namespace?std;
const?int?MAXN =?1005;int?graph[MAXN][MAXN];int?dist[MAXN];bool?vis[MAXN];
void?dijkstra(int?s,?int?n)?{
????fill(dist,?dist +?MAXN,?INT_MAX);
????fill(vis,?vis +?MAXN,?false);
????dist[s]?=?0;
????for?(int?i =?0;?i <?n;?i++)?{
????????int?u =?-1;
????????for?(int?j =?1;?j <=?n;?j++)?{
????????????if?(!vis[j]?&&?(u ==?-1?||?dist[j]?<?dist[u]))?{
????????????????u =?j;
????????????}
????????}
????????vis[u]?=?true;
????????for?(int?v =?1;?v <=?n;?v++)?{
????????????if?(!vis[v]?&&?graph[u][v]?!=?INT_MAX)?{
????????????????dist[v]?=?min(dist[v],?dist[u]?+?graph[u][v]);
????????????}
????????}
????}}
int?main()?{
????int?n,?m,?s;
????cin >>?n >>?m >>?s;
????for?(int?i =?1;?i <=?n;?i++)?{
????????for?(int?j =?1;?j <=?n;?j++)?{
????????????if?(i ==?j)?{
????????????????graph[i][j]?=?0;
????????????}?else?{
????????????????graph[i][j]?=?INT_MAX;
????????????}
????????}
????}
????for?(int?i =?0;?i <?m;?i++)?{
????????int?u,?v,?w;
????????cin >>?u >>?v >>?w;
????????graph[u][v]?=?min(graph[u][v],?w);
????}
????dijkstra(s,?n);
????for?(int?i =?1;?i <=?n;?i++)?{
????????cout <<?dist[i]?<<?" ";
????}
????cout <<?endl;
????return?0;}
堆優化迪杰斯特拉
原理：使用優先隊列（小根堆）來優化每次選擇距離源點最近的節點的過程，減少時間復雜度。
用法：適用于邊權非負且節點數較多的稀疏圖，時間復雜度為?O((V+E)logV)。
代碼：
#include?<iostream>#include?<vector>#include?<queue>#include?<climits>using?namespace?std;
const?int?MAXN =?100005;
vector<pair<int,?int>>?adj[MAXN];int?dist[MAXN];
void?dijkstra(int?s)?{
????priority_queue<pair<int,?int>,?vector<pair<int,?int>>,?greater<pair<int,?int>>>?pq;
????fill(dist,?dist +?MAXN,?INT_MAX);
????dist[s]?=?0;
????pq.push({0,?s});
????while?(!pq.empty())?{
????????auto?[d,?u]?=?pq.top();
????????pq.pop();
????????if?(d >?dist[u])?continue;
????????for?(auto?[v,?w]?:?adj[u])?{
????????????if?(dist[v]?>?dist[u]?+?w)?{
????????????????dist[v]?=?dist[u]?+?w;
????????????????pq.push({dist[v],?v});
????????????}
????????}
????}}
int?main()?{
????int?n,?m,?s;
????cin >>?n >>?m >>?s;
????for?(int?i =?0;?i <?m;?i++)?{
????????int?u,?v,?w;
????????cin >>?u >>?v >>?w;
????????adj[u].emplace_back(v,?w);
????}
????dijkstra(s);
????for?(int?i =?1;?i <=?n;?i++)?{
????????cout <<?dist[i]?<<?" ";
????}
????cout <<?endl;
????return?0;}
Bellman - Ford
原理：通過對所有邊進行?V?1?次松弛操作，來更新節點的最短距離。如果圖中存在負環，經過?V?1?次松弛操作后，仍然可以繼續松弛。
用法：適用于存在負權邊的圖，也可用于求解只經過?k?條邊的最短路。
代碼：
#include?<iostream>#include?<vector>#include?<climits>using?namespace?std;
const?int?MAXN =?100005;struct?Edge?{
????int?u,?v,?w;};
vector<Edge>?edges;int?dist[MAXN];
bool?bellman_ford(int?s,?int?n)?{
????fill(dist,?dist +?MAXN,?INT_MAX);
????dist[s]?=?0;
? ? ?int?flag=0;
????for?(int?i =?0;?i <?n ;?i++)?{
????????for?(auto?[u,?v,?w]?:?edges)?{
? ? ? ? ? ??flag=0;
????????????if?(dist[u]?!=?INT_MAX &&?dist[v]?>?dist[u]?+?w)?{
????????????????dist[v]?=?dist[u]?+?w;
? ? ? ? ? ? ? ? ?flag=1;
? ? ? ? ? ? ? ? ?if(i==n)return true;//如果鏈接了n條邊還能松弛就說明有負環
????????????}
????????}
????}
????return?false;
}
int?main()?{
????int?n,?m,?s;
????cin >>?n >>?m >>?s;
????for?(int?i =?0;?i <?m;?i++)?{
????????int?u,?v,?w;
????????cin >>?u >>?v >>?w;
????????edges.push_back({u,?v,?w});
????}
????if?(bellman_ford(s,?n))?{
????????cout <<?"存在負環"?<<?endl;
????}?else?{
????????for?(int?i =?1;?i <=?n;?i++)?{
????????????cout <<?dist[i]?<<?" ";
????????}
????????cout <<?endl;
????}
????return?0;
}
SPFA
原理：SPFA 是 Bellman - Ford 算法的優化版本，使用隊列來維護需要松弛的節點。
用法：適用于存在負權邊的圖，但在某些特殊圖中可能會退化為?O(VE)。
代碼：
#include?<iostream>#include?<vector>#include?<queue>#include?<climits>using?namespace?std;
const?int?MAXN =?100005;
vector<pair<int,?int>>?adj[MAXN];int?dist[MAXN];int?cnt[MAXN];?// 記錄每個節點入隊的次數bool?in_queue[MAXN];
bool?spfa(int?s,?int?n)?{
????fill(dist,?dist +?MAXN,?INT_MAX);
????fill(cnt,?cnt +?MAXN,?0);
????fill(in_queue,?in_queue +?MAXN,?false);
????dist[s]?=?0;
????queue<int>?q;
????q.push(s);
????in_queue[s]?=?true;
????cnt[s]?=?1;
????while?(!q.empty())?{
????????int?u =?q.front();
????????q.pop();
????????in_queue[u]?=?false;
????????for?(auto?[v,?w]?:?adj[u])?{
????????????if?(dist[v]?>?dist[u]?+?w)?{
????????????????dist[v]?=?dist[u]?+?w;
????????????????if?(!in_queue[v])?{
????????????????????q.push(v);
????????????????????in_queue[v]?=?true;
????????????????????cnt[v]++;
????????????????????if?(cnt[v]?>?n)?{
????????????????????????return?true;?// 存在負環
????????????????????}
????????????????}
????????????}
????????}
????}
????return?false;}
int?main()?{
????int?n,?m,?s;
????cin >>?n >>?m >>?s;
????for?(int?i =?0;?i <?m;?i++)?{
????????int?u,?v,?w;
????????cin >>?u >>?v >>?w;
????????adj[u].emplace_back(v,?w);
????}
????if?(spfa(s,?n))?{
????????cout <<?"存在負環"?<<?endl;
????}?else?{
????????for?(int?i =?1;?i <=?n;?i++)?{
????????????cout <<?dist[i]?<<?" ";
????????}
????????cout <<?endl;
????}
????return?0;}
2. 單源最短路和其他算法的結合
二分答案 + 雙端隊列求最短路
以 “可以免費建立?k?條邊，求最小的花費” 為例，二分答案?mid，將邊權大于?mid?的邊視為 1，邊權小于等于?mid?的邊視為 0，使用雙端隊列 BFS 求解最短路，判斷最短路徑上大于?mid?的邊數是否小于等于?k。
縮點 + 最短路
先使用 Tarjan 算法求出圖的強連通分量，然后進行縮點，將每個強連通分量縮成一個點，再在縮點后的圖上進行最短路計算。
首位兩次最短路求節點之間的最大差值（以 2009 年提高組最優貿易問題為例）
分別從起點和終點進行最短路計算，記錄從起點到每個節點的最小價格和從終點到每個節點的最大價格，然后枚舉每個節點，計算最大差值。
3. 單源最短路自身的拓展
多起點多終點用虛擬節點
添加一個虛擬起點和一個虛擬終點，將虛擬起點與所有起點相連，邊權為 0，將所有終點與虛擬終點相連，邊權為 0，然后求解從虛擬起點到虛擬終點的最短路。
分圖層的最短路
以 “拯救大兵瑞恩” 為例，使用三維數組?d[x][y][st]?記錄狀態，其中?(x,y)?表示節點坐標，st?表示當前擁有的鑰匙狀態，只有拿到了鑰匙才能進入到對應層的一些狀態，在 BFS 或 Dijkstra 過程中更新狀態。
新的一個例題：
題目背景
本題原題數據極弱，Subtask 0 中的測試點為原題測試點，Subtask 1 中的測試點為 Hack 數據。
題目描述
C 國有 n 個大城市和 m 條道路，每條道路連接這 n 個城市中的某兩個城市。任意兩個城市之間最多只有一條道路直接相連。這 m 條道路中有一部分為單向通行的道路，一部分為雙向通行的道路，雙向通行的道路在統計條數時也計為 1 條。
C 國幅員遼闊，各地的資源分布情況各不相同，這就導致了同一種商品在不同城市的價格不一定相同。但是，同一種商品在同一個城市的買入價和賣出價始終是相同的。
商人阿龍來到 C 國旅游。當他得知同一種商品在不同城市的價格可能會不同這一信息之后，便決定在旅游的同時，利用商品在不同城市中的差價賺回一點旅費。設 C 國 n 個城市的標號從 1～n，阿龍決定從 1 號城市出發，并最終在 n 號城市結束自己的旅行。在旅游的過程中，任何城市可以重復經過多次，但不要求經過所有 n 個城市。阿龍通過這樣的貿易方式賺取旅費：他會選擇一個經過的城市買入他最喜歡的商品――水晶球，并在之后經過的另一個城市賣出這個水晶球，用賺取的差價當做旅費。由于阿龍主要是來 C 國旅游，他決定這個貿易只進行最多一次，當然，在賺不到差價的情況下他就無需進行貿易。
假設 C 國有 5 個大城市，城市的編號和道路連接情況如下圖，單向箭頭表示這條道路為單向通行，雙向箭頭表示這條道路為雙向通行。
假設 1～n 號城市的水晶球價格分別為 4,3,5,6,1。
阿龍可以選擇如下一條線路：1→2→3→5，并在 2 號城市以 3 的價格買入水晶球，在 3 號城市以 5 的價格賣出水晶球，賺取的旅費數為 2。
阿龍也可以選擇如下一條線路：1→4→5→4→5，并在第 1 次到達 5 號城市時以 1 的價格買入水晶球，在第 2 次到達 4 號城市時以 6 的價格賣出水晶球，賺取的旅費數為 5。
現在給出 n 個城市的水晶球價格，m 條道路的信息（每條道路所連接的兩個城市的編號以及該條道路的通行情況）。請你告訴阿龍，他最多能賺取多少旅費。
輸入格式
第一行包含 2 個正整數 n 和 m，中間用一個空格隔開，分別表示城市的數目和道路的數目。
第二行 n 個正整數，每兩個整數之間用一個空格隔開，按標號順序分別表示這 n 個城市的商品價格。
接下來 m 行，每行有 3 個正整數 x,y,z，每兩個整數之間用一個空格隔開。如果 z=1，表示這條道路是城市 x 到城市 y 之間的單向道路；如果 z=2，表示這條道路為城市 x 和城市 y 之間的雙向道路。
輸出格式
一個整數，表示最多能賺取的旅費。如果沒有進行貿易，則輸出 0。
代碼：
分層圖，第一層原本的圖，第二層，第一層購買后到達的圖，第三層，第二層對應節點賣出的圖
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N=100010;
unordered_map<int,vector<pii>>e;
int n,m;
int a[N];
int dis[N*3];
bool vis[N*3];
void spfa(int s){
? ? memset(dis,-0x3f,sizeof dis);
? ? queue<int> q;
? ? q.push(s);
? ? dis[s]=0;
? ? vis[s]=1;
? ? while(q.size()){
? ? ? ? int u=q.front();
? ? ? ? q.pop();
? ? ? ? vis[u]=0;
? ? ? ? for(auto t:e[u]){
? ? ? ? ? ? int v=t.first,w=t.second;
? ? ? ? ? ? if(dis[v]<dis[u]+w){
? ? ? ? ? ? ? ? dis[v]=dis[u]+w;
? ? ? ? ? ? ? ? if(!vis[v]){
? ? ? ? ? ? ? ? ? ? vis[v]=1;
? ? ? ? ? ? ? ? ? ? q.push(v);
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? }
}
int main(){
? ? scanf("%d%d",&n,&m);
? ? for(int i=1;i<=n;i++){
? ? ? ? scanf("%d",&a[i]);
? ? ? ? e[i].push_back({i+n,-a[i]});
? ? ? ? e[n+i].push_back({i+2*n,a[i]});
? ? }
? ? for(int i=0;i<m;i++){
? ? ? ? int u,v,op;
? ? ? ? scanf("%d%d%d",&u,&v,&op);
? ? ? ? if(op==2){
? ? ? ? ? ? e[u].push_back({v,0});
? ? ? ? ? ? e[u+n].push_back({v+n,0});
? ? ? ? ? ? e[u+2*n].push_back({v+2*n,0});
? ? ? ? ? ? e[v].push_back({u,0});
? ? ? ? ? ? e[v+n].push_back({u+n,0});
? ? ? ? ? ? e[v+2*n].push_back({u+2*n,0});
? ? ? ? }else{
? ? ? ? ? ? e[u].push_back({v,0});
? ? ? ? ? ? e[u+n].push_back({v+n,0});
? ? ? ? ? ? e[u+2*n].push_back({v+2*n,0});
? ? ? ? }
? ? }
? ? spfa(1);
? ? cout<<dis[3*n];
}
?
最短路計數
在更新最短路徑時，記錄路徑數量。如果經過某個點的路徑更短，計數為 1；如果相等，計數累加。
代碼：
#include?<iostream>#include?<vector>#include?<queue>#include?<climits>using?namespace?std;
const?int?MAXN =?100005;const?int?MOD =?1e9?+?7;
vector<pair<int,?int>>?adj[MAXN];int?dist[MAXN];int?cnt[MAXN];
void?dijkstra(int?s)?{
????priority_queue<pair<int,?int>,?vector<pair<int,?int>>,?greater<pair<int,?int>>>?pq;
????fill(dist,?dist +?MAXN,?INT_MAX);
????fill(cnt,?cnt +?MAXN,?0);
????dist[s]?=?0;
????cnt[s]?=?1;
????pq.push({0,?s});
????while?(!pq.empty())?{
????????auto?[d,?u]?=?pq.top();
????????pq.pop();
????????if?(d >?dist[u])?continue;
????????for?(auto?[v,?w]?:?adj[u])?{
????????????if?(dist[v]?>?dist[u]?+?w)?{
????????????????dist[v]?=?dist[u]?+?w;
????????????????cnt[v]?=?cnt[u];
????????????????pq.push({dist[v],?v});
????????????}?else?if?(dist[v]?==?dist[u]?+?w)?{
????????????????cnt[v]?=?(cnt[v]?+?cnt[u])?%?MOD;
????????????}
????????}
????}}
int?main()?{
????int?n,?m,?s;
????cin >>?n >>?m >>?s;
????for?(int?i =?0;?i <?m;?i++)?{
????????int?u,?v,?w;
????????cin >>?u >>?v >>?w;
????????adj[u].emplace_back(v,?w);
????}
????dijkstra(s);
????for?(int?i =?1;?i <=?n;?i++)?{
????????cout <<?dist[i]?<<?" "?<<?cnt[i]?<<?endl;
????}
????return?0;}
最短路和次短路
使用兩個數組分別記錄最短路和次短路，在更新時同時更新這兩個數組。
代碼：
#include?<iostream>#include?<vector>#include?<queue>#include?<climits>using?namespace?std;
const?int?MAXN =?100005;
vector<pair<int,?int>>?adj[MAXN];int?dist1[MAXN];?// 最短路int?dist2[MAXN];?// 次短路
void?dijkstra(int?s)?{
????priority_queue<pair<int,?int>,?vector<pair<int,?int>>,?greater<pair<int,?int>>>?pq;
????fill(dist1,?dist1 +?MAXN,?INT_MAX);
????fill(dist2,?dist2 +?MAXN,?INT_MAX);
????dist1[s]?=?0;
????pq.push({0,?s});
????while?(!pq.empty())?{
????????auto?[d,?u]?=?pq.top();
????????pq.pop();
????????if?(d >?dist2[u])?continue;
????????for?(auto?[v,?w]?:?adj[u])?{
????????????int?new_dist =?d +?w;
????????????if?(new_dist <?dist1[v])?{
????????????????dist2[v]?=?dist1[v];
????????????????dist1[v]?=?new_dist;
????????????????pq.push({dist1[v],?v});
????????????}?else?if?(new_dist <?dist2[v]?&&?new_dist >?dist1[v])?{
????????????????dist2[v]?=?new_dist;
????????????????pq.push({dist2[v],?v});
????????????}
????????}
????}}
int?main()?{
????int?n,?m,?s;
????cin >>?n >>?m >>?s;
????for?(int?i =?0;?i <?m;?i++)?{
????????int?u,?v,?w;
????????cin >>?u >>?v >>?w;
????????adj[u].emplace_back(v,?w);
????}
????dijkstra(s);
????for?(int?i =?1;?i <=?n;?i++)?{
????????cout <<?dist1[i]?<<?" "?<<?dist2[i]?<<?endl;
????}
????return?0;}
4. 全源最短路
Floyd 算法
原理：通過動態規劃的思想，枚舉中間節點?k，更新任意兩點之間的最短距離。
用法：適用于求解任意兩點之間的最短路徑，也可用于處理聯通問題、傳遞閉包和最小環問題。
代碼：
#include?<iostream>#include?<climits>using?namespace?std;
const?int?MAXN =?1005;int?graph[MAXN][MAXN];
void?floyd(int?n)?{
????for?(int?k =?1;?k <=?n;?k++)?{
????????for?(int?i =?1;?i <=?n;?i++)?{
????????????for?(int?j =?1;?j <=?n;?j++)?{
????????????????if?(graph[i][k]?!=?INT_MAX &&?graph[k][j]?!=?INT_MAX)?{
????????????????????graph[i][j]?=?min(graph[i][j],?graph[i][k]?+?graph[k][j]);
????????????????}
????????????}
????????}
????}}
int?main()?{
????int?n,?m;
????cin >>?n >>?m;
????for?(int?i =?1;?i <=?n;?i++)?{
????????for?(int?j =?1;?j <=?n;?j++)?{
????????????if?(i ==?j)?{
????????????????graph[i][j]?=?0;
????????????}?else?{
????????????????graph[i][j]?=?INT_MAX;
????????????}
????????}
????}
????for?(int?i =?0;?i <?m;?i++)?{
????????int?u,?v,?w;
????????cin >>?u >>?v >>?w;
????????graph[u][v]?=?min(graph[u][v],?w);
????}
????floyd(n);
????for?(int?i =?1;?i <=?n;?i++)?{
????????for?(int?j =?1;?j <=?n;?j++)?{
????????????cout <<?graph[i][j]?<<?" ";
????????}
????????cout <<?endl;
????}
????return?0;}
最小環
在 Floyd 算法的基礎上，記錄最小環的長度。
cpp
#include?<iostream>#include?<climits>using?namespace?std;
const?int?MAXN =?1005;int?graph[MAXN][MAXN];int?dist[MAXN][MAXN];
int?floyd_min_cycle(int?n)?{
????int?ans =?INT_MAX;
????for?(int?i =?1;?i <=?n;?i++)?{
????????for?(int?j =?1;?j <=?n;?j++)?{
????????????dist[i][j]?=?graph[i][j];
????????}
????}
????for?(int?k =?1;?k <=?n;?k++)?{
????????for?(int?i =?1;?i <?k;?i++)?{
????????????for?(int?j =?i +?1;?j <?k;?j++)?{
????????????????if?(graph[i][k]?!=?INT_MAX &&?graph[k][j]?!=?INT_MAX &&?dist[i][j]?!=?INT_MAX)?{
????????????????????ans =?min(ans,?graph[i][k]?+?graph[k][j]?+?dist[i][j]);
????????????????}
????????????}
????????}
????????for?(int?i =?1;?i <=?n;?i++)?{
????????????for?(int?j =?1;?j <=?n;?j++)?{
????????????????if?(dist[i][k]?!=?INT_MAX &&?dist[k][j]?!=?INT_MAX)?{
????????????????????dist[i][j]?=?min(dist[i][j],?dist[i][k]?+?dist[k][j]);
????????????????}
????????????}
????????}
????}
????return?ans;
}
int?main()?{
????int?n,?m;
????cin >>?n >>?m;
????for?(int?i =?1;?i <=?n;?i++)?{
????????for?(int?j =?1;?j <=?n;?j++)?{
????????????if?(i ==?j)?{
????????????????graph[i][j]?=?0;
????????????}?else?{
????????????????graph[i][j]?=?INT_MAX;
????????????}
????????}
????}
????for?(int?i =?0;?i <?m;?i++)?{
????????int?u,?v,?w;
????????cin >>?u >>?v >>?w;
????????graph[u][v]?=?min(graph[u][v],?w);
????????graph[v][u]?=?min(graph[v][u],?w);
????}
????int?min_cycle =?floyd_min_cycle(n);
????if?(min_cycle ==?INT_MAX)?{
????????cout <<?"不存在最小環"?<<?endl;
????}?else?{
????????cout <<?"最小環長度為: "?<<?min_cycle <<?endl;
????}
????return?0;
}
5. 最小生成樹
Prim 算法
原理：從一個節點開始，每次選擇與當前生成樹相連的邊中權值最小的邊，將其加入生成樹，直到所有節點都被加入。
用法：適用于稠密圖，時間復雜度為?O(V2)。
代碼：
#include?<iostream>#include?<vector>#include?<climits>using?namespace?std;
const?int?MAXN =?1005;int?graph[MAXN][MAXN];bool?vis[MAXN];int?dist[MAXN];
int?prim(int?n)?{
????fill(vis,?vis +?MAXN,?false);
????fill(dist,?dist +?MAXN,?INT_MAX);
????dist[1]?=?0;
????int?ans =?0;
????for?(int?i =?0;?i <?n;?i++)?{
????????int?u =?-1;
????????for?(int?j =?1;?j <=?n;?j++)?{
????????????if?(!vis[j]?&&?(u ==?-1?||?dist[j]?<?dist[u]))?{
????????????????u =?j;
????????????}
????????}
????????vis[u]?=?true;
????????ans +=?dist[u];
????????for?(int?v =?1;?v <=?n;?v++)?{
????????????if?(!vis[v]?&&?graph[u][v]?!=?INT_MAX)?{
????????????????dist[v]?=?min(dist[v],?graph[u][v]);
????????????}
????????}
????}
????return?ans;}
int?main()?{
????int?n,?m;
????cin >>?n >>?m;
????for?(int?i =?1;?i <=?n;?i++)?{
????????for?(int?j =?1;?j <=?n;?j++)?{
????????????if?(i ==?j)?{
????????????????graph[i][j]?=?0;
????????????}?else?{
????????????????graph[i][j]?=?INT_MAX;
????????????}
????????}
????}
????for?(int?i =?0;?i <?m;?i++)?{
????????int?u,?v,?w;
????????cin >>?u >>?v >>?w;
????????graph[u][v]?=?min(graph[u][v],?w);
????????graph[v][u]?=?min(graph[v][u],?w);
????}
????int?mst =?prim(n);
????cout <<?"最小生成樹的權值為: "?<<?mst <<?endl;
????return?0;}
Kruskal 算法
原理：將所有邊按權值從小到大排序，然后依次選擇邊，如果該邊的兩個端點不在同一個連通分量中，則將該邊加入生成樹，直到所有節點都在同一個連通分量中。
用法：適用于稀疏圖，時間復雜度為?O(ElogE)。
代碼：
#include?<iostream>#include?<vector>#include?<algorithm>using?namespace?std;
const?int?MAXN =?100005;struct?Edge?{
????int?u,?v,?w;
????bool?operator<(const?Edge&?other)?const?{
????????return?w <?other.w;
????}};
vector<Edge>?edges;int?parent[MAXN];
int?find(int?x)?{
????if?(parent[x]?!=?x)?{
????????parent[x]?=?find(parent[x]);
????}
????return?parent[x];}
void?unite(int?x,?int?y)?{
????int?px =?find(x);
????int?py =?find(y);
????if?(px !=?py)?{
????????parent[px]?=?py;
????}}
int?kruskal(int?n)?{
????sort(edges.begin(),?edges.end());
????for?(int?i =?1;?i <=?n;?i++)?{
????????parent[i]?=?i;
????}
????int?ans =?0;
????int?cnt =?0;
????for?(auto?[u,?v,?w]?:?edges)?{
????????if?(find(u)?!=?find(v))?{
????????????unite(u,?v);
????????????ans +=?w;
????????????cnt++;
????????????if?(cnt ==?n -?1)?{
????????????????break;
????????????}
????????}
????}
????return?ans;}
int?main()?{
????int?n,?m;
????cin >>?n >>?m;
????for?(int?i =?0;?i <?m;?i++)?{
????????int?u,?v,?w;
????????cin >>?u >>?v >>?w;
????????edges.push_back({u,?v,?w});
????}
????int?mst =?kruskal(n);
????cout <<?"最小生成樹的權值為: "?<<?mst <<?endl;
????return?0;}
6. 最小生成樹的運用
引入虛擬節點
以 “有?k?個點可以用衛星鏈接，求出讓全部點聯通的最小花費” 為例，添加一個虛擬節點，將該節點與可以用衛星鏈接的?k?個點相連，邊權為 0，然后使用 Kruskal 或 Prim 算法求解最小生成樹。
允許?k?個聯通塊的最小花費
使用 Kruskal 算法，在合并節點的過程中，當合并到?k?個聯通塊時停止，此時的花費即為最小花費。
代碼：
#include?<iostream>#include?<vector>#include?<algorithm>using?namespace?std;
const?int?MAXN =?100005;struct?Edge?{
????int?u,?v,?w;
????bool?operator<(const?Edge&?other)?const?{
????????return?w <?other.w;
????}};
vector<Edge>?edges;int?parent[MAXN];
int?find(int?x)?{
????if?(parent[x]?!=?x)?{
????????parent[x]?=?find(parent[x]);
????}
????return?parent[x];}
void?unite(int?x,?int?y)?{
????int?px =?find(x);
????int?py =?find(y);
????if?(px !=?py)?{
????????parent[px]?=?py;
????}}
int?kruskal(int?n,?int?k)?{
????sort(edges.begin(),?edges.end());
????for?(int?i =?1;?i <=?n;?i++)?{
????????parent[i]?=?i;
????}
????int?ans =?0;
????int?cnt =?n;
????for?(auto?[u,?v,?w]?:?edges)?{
????????if?(find(u)?!=?find(v))?{
????????????unite(u,?v);
????????????ans +=?w;
????????????cnt--;
????????????if?(cnt ==?k)?{
????????????????break;
????????????}
????????}
????}
????return?ans;}
int?main()?{
????int?n,?m,?k;
????cin >>?n >>?m >>?k;
????for?(int?i =?0;?i <?m;?i++)?{
????????int?u,?v,?w;
????????cin >>?u >>?v >>?w;
????????edges.push_back({u,?v,?w});
????}
????int?cost =?kruskal(n,?k);
????cout <<?"允許 "?<<?k <<?" 個聯通塊的最小花費為: "?<<?cost <<?endl;
return?0;
}
安裝streamlit(虛擬環境py3.9))
![[漏洞篇]SSRF漏洞詳解](http://pic.xiahunao.cn/[漏洞篇]SSRF漏洞詳解)
