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;
}

//奶牛跨栏
//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;
}