【POJ1797】Heavy Transportation 最短路

题意：无向图上1~n的最大承重。

题解：最短路，spfa时稍稍该改。

不懂看代码，又水又好看。

注意：每组数据后面俩回车，我PE了若干次。。。

#include <set>
#include <list>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 1005
#define inf 0x3f3f3f3f
using namespace std;
int map[N][N],n,m,in[N],dist[N];
int spfa(int s,int t)
{
int u,v;
queue<int>q;
memset(dist,0,sizeof(dist));
memset(in,0,sizeof(in));
dist[s]=inf;
in[s]=1;
q.push(s);
while(!q.empty())
{
u=q.front();q.pop();in[u]=0;
for(v=1;v<=n;v++)
{
if(dist[v]<min(dist[u],map[u][v]))
{
dist[v]=min(dist[u],map[u][v]);
if(!in[v])q.push(v),in[v]=1;
}
}
}
return dist[t];
}
int main()
{
//	freopen("test.in","r",stdin);
int i,g,_g;
int a,b,c;
scanf("%d",&_g);
for(g=1;g<=_g;g++)
{
printf("Scenario #%d:n",g);
memset(map,0,sizeof(map));
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&c);
map[a][b]=c;
map[b][a]=c;
}
printf("%dn",spfa(1,n));
puts("");
}
return 0;
}

最后

以上就是时尚机器猫为你收集整理的【POJ1797】Heavy Transportation 最短路的全部内容，希望文章能够帮你解决【POJ1797】Heavy Transportation 最短路所遇到的程序开发问题。

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