首页 > 代码库 > 415. [HAOI2009] 旅行
415. [HAOI2009] 旅行
★★ 输入文件：toura.in 输出文件：toura.out 简单对比
时间限制：1 s 内存限制：128 MB
试题描述
小明住在城市1，而他的朋友小芳住在城市n。最近小明收到小芳的邀请，准备于近期赴约。可是由于最近下了很多暴雨，很多道路都被淹没。从城市1出发到城市n之间有很多小城镇，并且两个小城镇之间有一条直接道路相连。小明经过对近期天气和地形的科学分析，绘出了每条道路能顺利通行的概率。
为了能顺利到达目的地，请帮助小明找出一条最稳妥的路线，也就是从城市1出发到达城市n的路线中能顺利通行的最大概率。
输入数据
文件第一行包含两个整数n和m，n为城市数，m为道路条数。
接下来m行，每行包含三个整数a，b，p ( 1<=p<=100 )，表示小城镇a与小城镇b间有一条道路，顺利通过这条道路的概率为p%。
输出数据
一个实数P，为到达城市n的最大概率，P精确到小数点后6位。
样例输入
.bmp)
5 7
5 2 100
3 5 80
2 3 70
2 1 50
3 4 90
4 1 85
3 1 70
样例输出
61.200000
样例说明：选择路线为1-4-3-5，概率为85%*90%*80%=61.2%
测试数据范围
30%的数据，n<=1000，m<=3000
100%的数据，n<=10000，m<=30000
代码并非自己写的，那个eps是个什么鬼，有点搞不懂：
#include<cstdio>#include<algorithm>#include<queue>#include<iostream>using namespace std;const int N=1e5+10;const double eps=1e-9;struct edge{int f,t,l;}w[N];int n,m,head[N],next[N],tail[N],cnt;void add(int f,int t,int l){ w[++cnt]=(edge){f,t,l}; if (!head[f]) head[f]=tail[f]=cnt; else tail[f]=next[tail[f]]=cnt; }double dis[N];bool inque[N];void spfa(){ queue<int> Q; for (int i=1;i<=n;i++) dis[i]=0; dis[1]=1;Q.push(1); while (!Q.empty()) { int v=Q.front();Q.pop(); inque[v]=0; for (int i=head[v];i;i=next[i]) if (dis[w[i].t]+eps<dis[v]/100*w[i].l) { dis[w[i].t]=dis[v]/100*w[i].l; if (!inque[w[i].t]) inque[w[i].t]=1,Q.push(w[i].t); } }}int main(){ freopen("toura.in","r",stdin); freopen("toura.out","w",stdout); scanf("%d%d",&n,&m); for (int i=1,f,t,l;i<=m;i++) { scanf("%d%d%d",&f,&t,&l); add(f,t,l);add(t,f,l); } spfa(); printf("%.6lf\n",100*dis[n]); return 0;}
415. [HAOI2009] 旅行
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。