POJ 3615 Cow Hurdles(Folyd变形)
http://poj.org/problem?id=3615
题意:给你一个有向图,然后对于特定的点A与B,要你求出A到B之间所有可行路径的单段路距离最大值的最小值.(有点绕)
分析:
和前几题一样,利用的是Floyd算法的动态规划思想.假设d[i][j]是从i到j所有可行路径中的单段距离的当前最大值.现在有路(i,k)和路(k,j)且如果max(d[i][k],d[k][j])<d[i][j],那么就要更新d[i][j]的值=
max(d[i][k],d[k][j]).
AC代码:
POJ 3615 Cow Hurdles(Folyd变形)
http://poj.org/problem?id=3615
题意:给你一个有向图,然后对于特定的点A与B,要你求出A到B之间所有可行路径的单段路距离最大值的最小值.(有点绕)
分析:
和前几题一样,利用的是Floyd算法的动态规划思想.假设d[i][j]是从i到j所有可行路径中的单段距离的当前最大值.现在有路(i,k)和路(k,j)且如果max(d[i][k],d[k][j])<d[i][j],那么就要更新d[i][j]的值= max(d[i][k],d[k][j]).
AC代码:
#include<cstdio>
#include<algorithm>
#define INF 1e9
using namespace std;
const int maxn = 300+10;
int n,m,t;
int d[maxn][maxn];
void floyd()
{
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(d[i][k]<INF &&d[k][j]<INF)
d[i][j]=min(d[i][j],max(d[i][k],d[k][j]));
}
int main()
{
while(scanf("%d%d%d",&n,&m,&t)==3)
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
d[i][j]= i==j?0:INF;
for(int i=1;i<=m;i++)
{
int u,v,height;
scanf("%d%d%d",&u,&v,&height);
d[u][v]=height;
}
floyd();
while(t--)
{
int u,v;
scanf("%d%d",&u,&v);
printf("%d\n",d[u][v]==INF?-1:d[u][v]);
}
}
return 0;
}
分享到:
相关推荐
poj 3266 Cow School.md
北大POJ3176-Cow Bowling
poj 3672 仅仅是源代码 更多将会继续上传
北大POJ3176-Cow Bowling 解题报告+AC代码
poj 1989 The Cow Lineup.md
poj 3623 Best Cow Line, Gold.md
北大POJ3267-The Cow Lexicon
北大POJ3278-Catch That Cow 解题报告+AC代码
北大POJ3267-The Cow Lexicon 解题报告+AC代码
poj 3673 Cow Multiplication 解题代码
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
搜索......................................................
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
北大POJ1159-Palindrome 解题报告+AC代码
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj分类poj分类poj分类poj分类