`

HDU 1596 find the safest road .

 
阅读更多

find the safest road

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1533    Accepted Submission(s): 581

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
 

 

Author
ailyanlu
 

 

Source
 

 

Recommend
8600
 
最短路水题一条,不过要注意题目要求不能到达时候输出what a pity!,我就甘WA两次……
下面贴代码:
4286804 2011-07-29 14:55:02 Accepted 1596 3562MS 6708K 647 B C++ 10SGetEternal{(。)(。)}!
#include <iostream>
using namespace std;
#define MAXI 1011

double g[MAXI][MAXI];
int n;

void Floyd()
{
    int k, u, v;

    for (k = 0; k < n; k++)
        for (u = 0; u < n; u++)
            for (v = 0; v < n; v++)
                if (g[u][k] * g[k][v] > g[u][v])
                    g[u][v] = g[u][k] * g[k][v];
}

int main()
{
    int q, u, v;

    while (scanf("%d", &n) != EOF)
    {
        for (u = 0; u < n; u++)
            for (v = 0; v < n; v++)
                scanf("%lf", g[u] + v);
        Floyd();
        scanf("%d", &q);
        while (q--)
        {
            scanf("%d%d", &u, &v);
            u--; v--;
            if (g[u][v] == 0.0) printf("What a pity!\n");
            else printf("%.3lf\n", g[u][v]);
        }
    }

    return 0;
}

 真系好水…………

分享到:
评论

相关推荐

    hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj

    【标题】"hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj" 提供的信息是关于一个压缩文件,其中包含了一个名为 "HDU 1089.cpp" 的源代码文件,这个文件是为了解决杭州电子科技大学(Hangzhou Dianzi ...

    hdu5102.zip_K.

    标题中的"hdu5102.zip_K."暗示这是一个与编程竞赛相关的题目,通常在HDU(杭州电子科技大学)在线判题系统中出现。这个题目可能是一个编程挑战,要求参赛者解决一个特定的问题,并提交源代码以供自动评判。"K."可能...

    杭电操作系统实验 HDU操作系统实验.zip

    杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU...

    HDU 2000-2099 解题报告.CHM

    解题报告|ACM|程序设计参考程序以及题目的分析

    大学期间操作系统实验-HDU操作系统实验.zip

    HDU操作系统实验.zip大学期间操作系统实验-HDU操作系统实验.zip大学期间操作系统实验-HDU操作系统实验.zip大学期间操作系统实验-HDU操作系统实验.zip大学期间操作系统实验-HDU操作系统实验.zip大学期间操作系统实验-...

    HDU-GO v19.1225.2.zip

    【HDU-GO v19.1225.2.zip】是一个针对杭州电子科技大学(HDU)选课系统的浏览器插件,版本号为v19.1225.2。这个插件的主要功能是优化和提升学生在进行网络选课时的体验,它可能包含了增强界面、自动化操作、数据解析...

    HDU+2000-2099+解题报告.zip

    《杭电OnlineJudge 2000-2099解题报告》是针对杭州电子科技大学(HDU)在线评测系统(OnlineJudge)中2000至2099题目的详细解答集锦,主要涵盖了算法分析、编程技巧以及问题解决策略等内容。这份解题报告以CHM...

    HDU-2000-2099.zip_hdu2000

    【标题】"HDU-2000-2099.zip_hdu2000" 是一个包含杭电(Hangzhou Dianzi University)ACM竞赛题目解题报告的压缩包,覆盖了编号从2000到2099的题目。这个资源对于学习算法、提高编程技巧以及准备ACM/ICPC(国际大学...

    hdu_acm_1084.rar_ACM_HDU10_acm10_hdu_hdu 1084

    【标题】"hdu_acm_1084.rar_ACM_HDU10_acm10_hdu_hdu 1084" 提供的是一个关于杭电(HDU)ACM竞赛第1084题的解决方案。该题目可能是在编程竞赛中常见的算法问题,而ACM(国际大学生程序设计竞赛)是全球知名的编程...

    HDU-ACM_java.rar_hdu

    【标题】"HDU-ACM_java.rar" 是一个针对杭州电子科技大学(HDU)ACM竞赛的资源压缩包,其中包含的是使用Java语言编写的算法解决方案。这个压缩包主要面向那些参与或准备参与ACM国际大学生程序设计竞赛(ICPC)的参赛...

    HDU-2000-2099.rar_hdu

    HDU(杭州电子科技大学在线评测系统)是一个知名的编程竞赛平台,为编程爱好者提供了大量的算法题目进行练习和比赛。这个名为"HDU-2000-2099.rar_hdu"的压缩包包含了该平台从2000到2099共100道题目的源代码。这些...

    hangdianACM.rar_hangdiana_hdu acm_www.hangdianacm_杭电

    这个压缩文件包含的是作者个人提交并解决的ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest)题目,这些题目来源于HDU的在线编程平台。 【描述】"杭电的一些acm题目,都是我自己一个一...

    ACM HDU题目分类

    ACM HDU 题目分类 ACM HDU 题目分类是指对 HDU 在线判题系统中题目的分类,总结了大约十来个分类。这些分类将有助于编程选手更好地理解和解决问题。 DP 问题 DP(Dynamic Programming,动态规划)是一种非常重要...

    HDUACM2010版03递推求解.ppt

    HDUACM2010版03递推求解.ppt

    hdu.rar_hdu

    "hdu.rar_hdu"这个压缩包文件很可能是某位程序员整理的他在HDU上解决过的题目代码集合。这些代码通常包含了对各种算法的应用,例如排序、搜索、图论、动态规划等,对于学习算法和准备编程竞赛的初学者来说是一份宝贵...

    code_hdu.rar_ACM_The First_hdu_test case example

    Please write a program to find the smallest positive integer n that (f(n,m)?n)⊕n=k, or determine it is impossible. Input The first line of the input contains an integer T(1≤T≤10), denoting the ...

    kuangbin acm模板超级好用

    2.18.1 HDU4656 卷积取模 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 2.19 其它公式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 2.19.1 Polya . . . ....

Global site tag (gtag.js) - Google Analytics