find the safest road
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1746 Accepted Submission(s): 678
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
简单的最短路,不过这道题是乘法运算,所以初始化和判断稍微改变一下就行了,spfa搞定。
链接:http://acm.hdu.edu.cn/showproblem.php?pid=1596
代码:
#include <iostream>
#include <stdio.h>
#include <memory.h>
#include <queue>
using namespace std;
const int N = 1005;
double map[N][N], dist[N];
bool visit[N];
int n, t;
void input()
{
int i, j;
for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++)
scanf("%lf", &map[i][j]);
}
void spfa(int begin, int end)
{
int i, now;
memset(visit, false, sizeof(visit));
for(i = 0; i <= n; i++) dist[i] = 0; //dist初始化为0
dist[begin] = 1; //dist起点为1
queue<int> Q;
Q.push(begin);
visit[begin] = true;
while(!Q.empty())
{
now = Q.front();
Q.pop();
visit[now] = false;
for(i = 1; i <= n; i++)
{
if(dist[i] < dist[now] * map[now][i]) //乘法
{
dist[i] = dist[now] * map[now][i];
if(visit[i] == false)
{
Q.push(i);
visit[i] = true;
}
}
}
}
}
void output()
{
int ti, tj;
scanf("%d", &t);
while(t--)
{
scanf("%d %d", &ti, &tj);
spfa(ti, tj);
if(dist[tj] != 0) printf("%.3lf\n", dist[tj]);
else printf("What a pity!\n");
}
}
int main()
{
while(scanf("%d", &n) != EOF)
{
input();
output();
}
return 0;
}
分享到:
相关推荐
最短路(HDU-2544).rar
HDU最全ac代码
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
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 ...
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu2101AC代码
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
hdu1290 解题报告 献给杭电五十周年校庆的礼物 (切西瓜问题,即平面分割空间)
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu 1166线段树代码
自己做的HDU ACM已经AC的题目
hdu动态规划算法集锦
hdu题目分类