hdu1596find the safest road最短路floyd

其实就是模板的加法变成了乘法==但是注意“0”的处理!!看了标程才发现(⊙﹏⊙)b eps涉及double就记得用吧

Problem Description
XX星球有很多城市,每个城市之间有一条或多条飞行通道,但是并不是所有的路都是很安全的,每一条路有一个安全系数s,s是在 0 和 1 间的实数(包括0,1),一条从u 到 v 的通道P 的安全度为Safe(P) = s(e1)*s(e2)…*s(ek) e1,e2,ek是P 上的边 ,现在8600 想出去旅游,面对这这么多的路,他想找一条最安全的路。但是8600 的数学不好,想请你帮忙 ^_^
 

Input
输入包括多个测试实例,每个实例包括:
第一行:n。n表示城市的个数n<=1000;
接着是一个n*n的矩阵表示两个城市之间的安全系数,(0可以理解为那两个城市之间没有直接的通道)
接着是Q个8600要旅游的路线,每行有两个数字,表示8600所在的城市和要去的城市
 

Output
如果86无法达到他的目的地,输出"What a pity!",
其他的输出这两个城市之间的最安全道路的安全系数,保留三位小数。
 

Sample Input
3 1 0.5 0.5 0.5 1 0.4 0.5 0.4 1 3 1 2 2 3 1 3
 

Sample Output
0.500 0.400 0.500
#include <iostream>
#include<cstdio>
using namespace std;
double dist[1005][1005];
int main()
{
  //  freopen("cin.txt","r",stdin);
    int n,q,a,b;
    while(~scanf("%d",&n))
    {
         for(int i=0;i<n;i++)
         {
              for(int j=0;j<n;j++)
              {
                   scanf("%lf",&dist[i][j]);
              }
         }
         for(int i=0;i<n;i++)
         {
              for(int j=0;j<n;j++)
              {
                   for(int k=0;k<n;k++)
                   {
                        if(dist[j][i]*dist[i][k]>dist[j][k])
                         dist[j][k]=dist[j][i]*dist[i][k];
                   }
              }
         }
         scanf("%d",&q);
         while(q--)
         {
              scanf("%d%d",&a,&b);
              a--;b--;
              if(dist[a][b]>0.000001)
              printf("%.3lf\n",dist[a][b]);
              else puts("What a pity!");
         }
    }
    return 0;
}


注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-02 00:03
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议