Flody算法:多源最短路径（动规思想） 其实相比Dijkstra算法-堆优化版本（单源最短路径）外面再套一个for循环改为多源最短路径，写法更简洁，但是for循环套Dijkstra算法-堆优化，时间复杂度更低，O(n^2logn) 重点：状态转移方程 dp[i][j] = min(dp[i][j], max(dp[i][k], dp[k][j])) max取的是路径中的最高栏，min取的是所有路径中高栏最矮的。 ``` #include <bits/stdc++.h> using namespace std; int main() { int n,m,t; cin>>n>>m>>t; int mp[n+1][n+1]; int dp[n+1][n+1]; const int INF = 1e6 + 4; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { mp[i][j] = INF; } } while(m--) { int s,e,v; cin>>s>>e>>v; mp[s][e] = v; } for(int k = 1;k<=n;k++) { for(int i = 1;i<=n;i++) { for(int j = 1;j<=n;j++) { if(mp[i][k] != INF && mp[k][j] != INF) mp[i][j] = min(mp[i][j], max(mp[i][k], mp[k][j])); } } } while(t--) { int s,e; cin>>s>>e; cout<<(mp[s][e] == INF? -1 : mp[s][e])<<'\n'; } return 0; } ```

```cpp //奶牛跨栏 //https://dashoj.com/p/141 //dijkstra+图+邻接表+求瓶颈最短路的最小值 #include <bits/stdc++.h> using namespace std; using pi = pair<int,int>; const int N = 301; const int INF = 0x3f3f3f3f; struct node{ int v; int dis; bool operator < (const node & a) const{ return dis > a.dis; } }; vector<pi> adj[N]; int dist[N][N];//起点到终点的最短路 ,也充当记忆数组 bool flag[N];//是否在S中 void dijkstra(int u){ priority_queue<node> pq; for(int i = 0;i < N;i++){ dist[u][i] = INF; } dist[u][u] = 0; pq.push({u,0}); memset(flag, 0, sizeof(flag));//必要，不然会出bug while(!pq.empty()){ node it = pq.top(); pq.pop(); int t = it.v; if(flag[t]){ continue; } flag[t] = true; for(auto edge : adj[t]){ int i = edge.first; int w = edge.second; if(!flag[i] && dist[u][i] > max(dist[u][t],w)){ dist[u][i] = max(dist[u][t],w); pq.push({i,dist[u][i]}); } } } } int main(){ ios::sync_with_stdio(false); cin.tie(0); int n,m,t; int s,e,h; cin >> n >> m >> t; while(m--){ cin >> s >> e >> h; adj[s].push_back({e,h}); } for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { dist[i][j] = INF; } } while(t--){ int st,et; cin >> st >> et; int& res = dist[st][et]; if(res != INF){ cout << res << "\n"; continue; } dijkstra(st); if(res == INF){ cout << -1 << "\n"; }else{ cout << res << "\n"; } } return 0; } ```