HDU 1690 Bus System 任意点最短路径Floyd

分类：图论

图论

原题： ?pid=1690

题目大意：图中的表是代表不同长度路径的花费，输入所有点的坐标，求任意两点间的最短花费。

因为是求任意两点，这里最好是用floyd算法。题中几大坑：数据可能会超int，要用long long int；坐标可以为负，求距离要用abs绝对值函数。

参考代码如下：

using namespace std;typedef long long int lint;const lint N = 105;lint maze[N][N];lint polint[N];lint l1,l2,l3,l4,c1,c2,c3,c4;lint n,m;void init(){for(lint i=0;i<N;i++){for(lint j=0;j<N;j++){maze[i][j]=INF;}}}lint getlen(lint x){if(x<=l1) return c1;else if(x>l1&&x<=l2) return c2;else if(x>l2&&x<=l3) return c3;else if(x>l3&&x<=l4) return c4;else return INF;}void floyd(){for(lint k=1;k<=n;k++){for(lint i=1;i<=n;i++){for(lint j=1;j<=n;j++){maze[i][j]=min(maze[i][j],maze[i][k]+maze[k][j]);}}}}int main(){lint cases;scanf(“%I64d”,&cases);for(lint k=1;k<=cases;k++){scanf(“,&l1,&l2,&l3,&l4,&c1,&c2,&c3,&c4);scanf(“%I64d %I64d”,&n,&m);for(lint i=1;i<=n;i++){scanf(“%I64d”,&polint[i]);}init();for(lint i=1;i<=n;i++){for(lint j=i+1;j<=n;j++){lint len=getlen(abs(polint[j]-polint[i]));maze[i][j]=len;maze[j][i]=len;}}floyd();printf(“Case %I64d:\n”,k);for(lint i=1;i<=m;i++){lint x,y;scanf(“%I64d %I64d”,&x,&y);if(maze[x][y]!=INF)printf(“The minimum cost between station %I64d and station %I64d is %I64d.\n”,x,y,maze[x][y]);elseprintf(“Station %I64d and station %I64d are not attainable.\n”,x,y);}}return 0;}

上一篇map 用法详解

顶0踩0

，每一个成功者都有一个开始。勇于开始，才能找到成功的路。

相关文章：

你感兴趣的文章：

标签云：