胖哥的故事

题目:

大家都知道,在天朝无论使用哪种交通工具出行都是很不安全的,但是当你必须出远门的时候也就不得不冒着生命危险和自己的人生进行一场博弈了。

我们可怜的胖哥现在就遇到了这种囧状,为了参加ACM/ICPC火星赛区的比赛,他必须从天朝所在的星球乘坐某种特殊的交通工具到达那里(Amazing……)。

假设胖哥所在的宇宙有n个星球,胖哥所在的星球编号为1,火星编号为n。

我们姑且认为这种交通工具是一种车,共有m趟车次,每趟车次都从一个星球开往另一个星球,并且每趟车次都有一个失事率,表示了胖哥做这趟车次出事故的概率。

大家都知道,胖哥还小,还没有感受够这个世界,他想尽可能安全的到达火星,于是他请求你给予帮助,希望能够求出一条路线,使得他到达火星的出事概率越小越好。

当然如果从天朝到火星还没通车,那么胖哥自然连冒生命危险的机会也没有,他就可以安心的在家里打游戏了。

题中数据保证如果从A点可以到达B点,那么从B点绝对不可能到达A点

Input

输入一个数字t,表示共有t组测试样例。

对于每组测试样例,首先输入两个数字n和m,表示共有n个星球,有m个车次

接下来跟着是m行,每行先是两个整数x和y,表示有车次从编号为x的星球通往编号为y的星球

然后是一个实数s,表示这辆车的失事率,注意是失事率,也就是胖哥挂掉的概率

Output

如果胖哥不能到达火星,输出“Stayat home!”

否则输出一个实数,表示胖哥到达火星的最小失事率,结果保留五位小数

Sample Iutput

6

2 1

1 2 0.10000

2 2

1 2 0.10000

1 2 0.20000

3 2

1 2 0.10000

2 3 0.10000

3 2

1 2 0.10000

1 2 0.20000

2 1

1 2 0.00000

2 1

1 2 1.00000

Sample Output

Case 1: 0.10000

Case 2: 0.10000

Case 3: 0.19000

Case 4: Stay at home!

Case 5: 0.00000

Case 6: 1.00000

数据范围

t<=100,2<=n<=100,1<=m<=1000,1<=x,y<=n,0<=s<=1

Hint

请使用doudle,输入用%lf,输出用%f

思路:floyd求最大值
分析:
1 题目要求的是最小的失事率。我们知道只要有一辆车失事那么就算失事,所以我们应该要先算安全的概率,然后1-概率。这样才是失事的概率
2 题目要求的最小的失事率,那么就要有最大的安全率,所以我们利用floyd求最大的安全率,然后判断即可。
3 floyd求最大值的时候,应该全部初始化为-1

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define MAXN 110

int t , n , m;
double dis[MAXN][MAXN];

/*初始化*/
void init(){
   for(int i = 1 ; i <= n ; i++)
     for(int j = 1 ; j <= n ; j++)
        dis[i][j] = -1;
}

void floyd(){
   for(int k = 1 ; k <= n ; k++){
      for(int i = 1 ; i <= n ; i++){
         for(int j = 1 ; j <= n ; j++)
            if(dis[i][k] != -1 && dis[k][j] != -1)/*加上这一句判断是否有边*/
              dis[i][j] = max(dis[i][j] , dis[i][k]*dis[k][j]);
      }
   }
}

int main(){
   scanf("%d", &t);
   int Case = 1;
   int a , b;
   double s;
   while(t--){
      scanf("%d%d" , &n , &m);
      init();
      for(int i = 0 ; i < m ; i++){
         scanf("%d%d%lf" , &a , &b , &s);
         s = 1-s;/*求出安全的概率*/
         if(dis[a][b] < s)
           dis[a][b] = s;
      }
      floyd();
      if(dis[1][n] == -1)
        printf("Case %d: Stay at home!\n" , Case++);
      else
        printf("Case %d: %0.5f\n" , Case++ , 1-dis[1][n]);
   }
   return 0;
}
时间: 2024-10-30 08:50:03

胖哥的故事的相关文章

HDU4502-吉哥系列故事——临时工计划

吉哥系列故事--临时工计划 Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others) Total Submission(s): 2744    Accepted Submission(s): 1061 Problem Description 俗话说一分钱难倒英雄汉,高中几年下来,吉哥已经深深明白了这个道理,因此,新年开始存储一年的个人资金已经成了习惯,不过自从大学之后他不好意思再向大人要

hdu 4531吉哥系列故事之乾坤大挪移

题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=4531 这道搜索题挺恶心的...比赛时没有写出来. 首先要解决的问题是怎样判断符合条件的状 态,即所有一样的颜色是连在一起的.我是采用最简单也最搓的方法,按上下左右顺序给每一个小三角 形标号1-36,然后建立一张邻接矩阵图,然后bfs判断. 然后就是主要的暴力枚举部分,每次有 12种状态转移的选择,开始时用dfs,但爆栈了.然后改成bfs,又各种TLE.然后就是不断地优化优化. 判重的状态可以用一个

请听一个故事------&amp;gt;寒门再难出贵子

[7哥导读]本文是一位银行的HR写的,他工作了10年,接待了一群到银行实习的实习生,然后观察他们发生的一系列的故事.像小说,但比我们看过的小说更精彩:像现实,但比我们了解的现实更残酷.文章来源天涯社区,作者:永乐大帝二世. 一看标题就吸引了我,<寒门再难出贵子>.因为我出生在寒门,深刻理解作者为什么说寒门再难出贵子,如果你一会儿看到文章中治国的故事,你就可以联想到我.当然,理解不代表认同. 文章中的寒门,还不是家庭贫困,而是小城市.小城镇的学生.讲述了好几个残酷故事,应该是真实的故事.否则我不

胖子哥的大数据之路(7)- 传统企业切入核心or外围

一.引言 昨天和一个做互联网大数据(零售行业)的朋友交流,关于大数据传统企业实施的切入点产生了争执,主要围绕两个问题进行了深入的探讨: 问题1:对于一个传统企业而言什么是核心业务,什么是外围业务? 问题2:大数据传统企业实施切入点到底是从核心开始还是该从外围介入? 两个问题有关联关系,如果界定不了核心与外围的边界,那么第二个问题也就无从回答.在此与大家共享,希望更多的人能参与进来发表自己的观点. 二.探讨案例 某品牌电视产品厂商,主营业务是电视机生产.目前规划要做转型做数据化运营,通过内嵌入在电

郑州“西瓜哥”做客大河网聊爱情

西瓜哥常赞走进央视<向幸福出发>节目录制现场(@主持人张明 微博图片)央视CCTV-3<向幸福出发>节目录制现场 "郑州西瓜哥卖瓜救妻 爱心接力引发倾城之爱"引发了社会各界的广泛关注.8月7日,经过大河网牵线搭桥,"西瓜哥"常赞走进了中央电视台<向幸福出发>的演播室,参与了节目录制."西瓜哥"常赞的故事和郑州这座城市的大爱与温情,让现场的观众感动落泪. "西瓜哥"走进央视<向幸福出发&

龇牙哥蹿红互联网PS帝乱入经典游戏

在互联网时代,每个一段时间就会有一个杯具人物被PS帝看中,然后被PS成各种模样流传于网上.近日,一个戴着眼镜笑着露齿的的男孩成功的"被走红".由于他的笑容太过于"灿烂",露出了整齐洁白的牙齿,被 网友膜拜奉为"龇牙哥". PS高手们各展所长,将这位男孩及其照片里的三位同学被PS成了各种各样的卡通造型,如<葫芦娃>.<奥特曼>.<火影忍者>.<忍者神龟>.<灌篮高手>等.也有玩家参与到了P

并发网2014.10月阅读量Top10

Top1 线上性能问题初步排查方法 有时候有很多问题只有在线上或者预发环境才能发现,而线上又不能Debug,所以线上问题定位就只能看日志,系统状态和Dump线程,本文只是简单的介绍一些常用的工具,帮助定位线上问题--(1,853人阅读) Top2 Java锁的种类以及辨析(四):可重入锁 本文里面讲的是广义上的可重入锁,而不是单指JAVA下的ReentrantLock.可重入锁,也叫做递归锁,指的是同一线程 外层函数获得锁之后 ,内层递归函数仍然有获取该锁的代码,但不受影响.在JAVA环境下 R

《Java特种兵》1.5 功底补充

本文是<Java特种兵>的样章感谢博文视点和作者授权本站发布 1.5 功底补充 看完1.4节发现胖哥废话很多貌似没啥干货了 为了不让大家认为功底只有String那么一点点东西胖哥就再增加对原生态类型.集合类的说明这两方面的内容相信所有的Java开发者都必然会用到. 1.5.1 原生态类型 原生态类型是"神马" 原生态类型就是Java中不属于对象的那5%部分. 那到底是哪些东西呢 包含boolean.byte.short.char.int.float.long.double这

《Java特种兵》1.8 老A是在逆境中迎难而上者

本文是<Java特种兵>的样章,感谢博文视点和作者授权本站发布 1.8 老A是在逆境中迎难而上者 小胖哥虽然不是一个"传道者",但是喜欢小小论道,因为在人生的道路上,很多时候你我都会面临许多纠结的事情,而这个时候我们的态度会决定命运,而道就是道理和方法. ◎ 作为"程序员",每天被要求修改代码是否会烦躁不堪,甚至觉得失去工作的价值?当有人说你的代码有很多Bug时,你会像小鸟或老鸟一样反应吗? ◎ 作为"架构师",成天被程序员说这里(那