poj1794-最短路-dijkstra

Heavy Transportation

 http://poj.org/problem?id=1797

题目大意：有n个城市，m条道路，在每条道路上有一个承载量，现在要求从1到n城市最大承载量，而最大承载量就是从城市1到城市n所有通路上的最大承载量
解题思路：其实这个求最大边可以近似于求最短路，只要修改下找最短路更新的条件就可以了

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<math.h>
#include<set>
#include<vector>
#include<sstream>
#include<queue>
#define PI 3.1415926535897932384626
#define inf 0x3f3f3f3f
using namespace std;
const int maxn=1005;
int w[maxn][maxn];
int vis[maxn];
int dis[maxn];
int n;
void dijkstra()
{
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++)
{
dis[i]=w[1][i];
}
dis[1]=0;
vis[1]=1;
for(int i=1;i<=n;i++)
{
int x,mins=inf;
for(int j=1;j<=n;j++)
if(!vis[j]&&dis[j]<mins)
mins=dis[x=j];
vis[x]=1;
for(int j=1;j<=n;j++){
dis[j]=max(dis[j],min(dis[x],w[x][j]));
}
}
}
int main()
{
int t;
scanf("%d",&t);
for(int q=1;q<=t;q++)
{
int m;
scanf("%d%d",&n,&m);
memset(w,inf,sizeof(w));
while(m--)
{
int u,v,val;
scanf("%d%d%d",&u,&v,&val);
w[u][v]=val;
w[v][u]=val;
}
dijkstra();
printf("Scenario #%d:n%dnn",q,dis[n]);
}
}

最后

以上就是平常发夹为你收集整理的poj1794-最短路-dijkstra的全部内容，希望文章能够帮你解决poj1794-最短路-dijkstra所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。