本题思路：最短路变形，改变松弛方式即可，dist存的是源结点到当前结点的最长路的最小权值。
参考代码：
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define INF 0x3f3f3f3f 5 using namespace std; 6 7 const int maxn = 1000 + 10; 8 int n, m, k, Case = 0, G[maxn][maxn], dist[maxn]; 9 bool vis[maxn]; 10 11 int Dijkstra(int source, int aid) { 12 for(int i = 1; i <= n; i ++) 13 dist[i] = (i == source ? INF : 0); 14 for(int i = 1; i <= n; i ++) { 15 int minf = -1; 16 for(int j = 1; j <= n; j ++) 17 if(!vis[j] && minf < dist[j]) { 18 minf = dist[j]; 19 k = j; 20 } 21 vis[k] = true; 22 if(minf == - 1) break; 23 for(int j = 1; j <= n; j ++) 24 if(!vis[j] && dist[j] < min(dist[k], G[k][j])) 25 dist[j] = min(dist[k], G[k][j]); 26 } 27 return dist[aid]; 28 } 29 30 int main () { 31 int t, x, y, w; 32 scanf("%d", &t); 33 while(t --) { 34 memset(vis, false, sizeof vis); 35 for(int i = 1; i <= n; i ++) { 36 for(int j = 1; j <= n; j ++) 37 G[i][j] = 0; 38 } 39 scanf("%d %d", &n, &m); 40 for(int i = 1; i <= m; i ++) { 41 scanf("%d %d %d", &x, &y, &w); 42 G[x][y] = G[y][x] = max(G[x][y], w); 43 } 44 printf("Scenario #%d: %d ", ++Case, Dijkstra(1, n)); 45 } 46 return 0; 47 }