题意：题目大意：有n个城市，m条道路，在每条道路上有一个承载量，现在要求从1到n城市最大承载量，而最大承载量就是从城市1到城市n所有通路上的最大承载量
链接：点我
解题思路：其实这个求最大边可以近似于求最短路，只要修改下找最短路更新的条件就可以了
1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #include<cmath> 6 #include<queue> 7 #include<map> 8 using namespace std; 9 #define MOD 1000000007 10 #define pb(a) push_back(a) 11 const int INF=0x3f3f3f3f; 12 const double eps=1e-5; 13 typedef long long ll; 14 #define cl(a) memset(a,0,sizeof(a)) 15 #define ts printf("***** "); 16 const int MAXN=1010; 17 int n,m,tt,cnt; 18 int dist[MAXN][MAXN]; 19 #define typec int 20 bool vis[MAXN]; 21 int pre[MAXN]; 22 int cost[MAXN][MAXN],lowcost[MAXN]; 23 void Dijkstra(int n,int beg) 24 { 25 for(int i=1;i<=n;i++) 26 { 27 lowcost[i]=0;vis[i]=false;pre[i]=-1; 28 } 29 lowcost[beg]=INF; 30 for(int j=0;j<n;j++) 31 { 32 int k=-1; 33 int Min=0; 34 for(int i=1;i<=n;i++) 35 if(!vis[i]&&lowcost[i]>Min) 36 { 37 Min=lowcost[i]; 38 k=i; 39 } 40 if(k==-1)break; 41 vis[k]=true; 42 for(int i=1;i<=n;i++) 43 if(!vis[i]&&min(lowcost[k],cost[k][i])>lowcost[i]) 44 { 45 lowcost[i]=min(lowcost[k],cost[k][i]); 46 pre[i]=k; 47 } 48 } 49 } 50 int main() 51 { 52 int i,j,k; 53 #ifndef ONLINE_JUDGE 54 freopen("1.in","r",stdin); 55 #endif 56 int ca=1; 57 int tt; 58 scanf("%d",&tt); 59 while(tt--) 60 { 61 scanf("%d%d",&n,&m); 62 cl(cost); 63 int u,v,w; 64 cl(cost); 65 for(i=0;i<m;i++) 66 { 67 scanf("%d%d%d",&u,&v,&w); 68 cost[u][v]=cost[v][u]=max(cost[u][v],w); 69 } 70 /*for(i=1;i<=n;i++) 71 { 72 for(j=1;j<=n;j++) 73 { 74 printf("%d ",cost[i][j]); 75 } 76 printf(" "); 77 }*/ 78 Dijkstra(n,1); 79 printf("Scenario #%d: %d ",ca++,lowcost[n]); 80 } 81 return 0; 82 }