题目
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
AC代码······
*****************************************
#include"stdio.h"
float map[1001][1001];
int main()
{
int n,q,i,j,k,a,s,t,mark[1001];
float c,safest[1001];
while(scanf("%d",&n)!=EOF)
{
for(i=1;i<=n;i++)
{
mark[i]=0;
safest[i]=1;
}
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
scanf("%f",&map[i][j]);
}
scanf("%d",&q);
for(k=0;k<q;k++)
{
scanf("%d%d",&s,&t);
for(i=1;i<=n;i++)
safest[i]=map[i][s];
safest[s]=1;
mark[s]=1;
for(i=1;i<=n;i++)
{
c=-1;
for(j=1;j<=n;j++)
{
if(mark[j]==0&&safest[j]>c)
{
c=safest[j];
a=j;
}
}
mark[a]=1;
for(j=1;j<=n;j++)
{
if(!mark[j]&&safest[j]<(safest[a]*map[j][a]))
safest[j]=safest[a]*map[j][a];
}
}
if(safest[t]<=0.0)
printf("What a pity!\n");
else
printf("%.3f\n",safest[t]);
for(i=1;i<=n;i++)
{
mark[i]=0;
safest[i]=1;
}
}
}
return 0;
}
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
AC代码······
*****************************************
#include"stdio.h"
float map[1001][1001];
int main()
{
int n,q,i,j,k,a,s,t,mark[1001];
float c,safest[1001];
while(scanf("%d",&n)!=EOF)
{
for(i=1;i<=n;i++)
{
mark[i]=0;
safest[i]=1;
}
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
scanf("%f",&map[i][j]);
}
scanf("%d",&q);
for(k=0;k<q;k++)
{
scanf("%d%d",&s,&t);
for(i=1;i<=n;i++)
safest[i]=map[i][s];
safest[s]=1;
mark[s]=1;
for(i=1;i<=n;i++)
{
c=-1;
for(j=1;j<=n;j++)
{
if(mark[j]==0&&safest[j]>c)
{
c=safest[j];
a=j;
}
}
mark[a]=1;
for(j=1;j<=n;j++)
{
if(!mark[j]&&safest[j]<(safest[a]*map[j][a]))
safest[j]=safest[a]*map[j][a];
}
}
if(safest[t]<=0.0)
printf("What a pity!\n");
else
printf("%.3f\n",safest[t]);
for(i=1;i<=n;i++)
{
mark[i]=0;
safest[i]=1;
}
}
}
return 0;
}
发表评论
-
杭电1162 最小生成树问题
2012-07-27 15:15 859题目链接:http://acm.hdu.edu.cn/show ... -
杭电2680 迪杰特斯拉算法的应用
2012-07-25 20:43 1049题目描述: Problem Description: One ... -
杭电1272
2012-07-18 15:13 832这道题主要就是判断一下有没有环,还有就是节点数减去边数等于1, ... -
杭电2544 最短路径
2012-07-17 17:31 860Problem Description 在每年的校赛里,所有进 ... -
迪杰斯特拉(Dijkstra)算法
2012-07-17 16:07 1465迪杰斯特拉算法 迪杰斯特拉(Dijkstra)算法思想 ... -
杭电acm部分题目分类
2012-07-07 16:38 3432注:DP代表动态规划 1001 这个就不用说了吧 ... -
动态规划之背包问题
2012-07-07 16:22 842/*在一固定容积为C的背包内装入N件物品, 物品的体积为:w ... -
动态规划之背包问题
2012-07-07 16:12 0/*在一固定容积为C的背包内装入N件物品, 物品的体积为:w1 ... -
背包问题
2012-07-07 10:44 0决策是:第N件物品放或者不放; 由此可以写出动态转移方 ... -
杭电1003代码
2012-07-07 10:24 942#include<stdio.h> int mai ... -
动态规划
2012-07-07 10:21 750动态规划算法 一、基本 ...
相关推荐
图-6-迪杰特斯拉算法.cpp
Python2.7,迪杰特斯拉算法_Python_Dijkstra
迪杰斯特拉(Dijkstra)算法是图论中的一个著名算法,由荷兰计算机科学家艾兹格·迪杰斯特拉在1956年提出。这个算法主要用于解决单源最短路径问题,即从图中的一点(源点)出发,找到到达其他所有点的最短路径。在...
迪杰斯特拉算法的应用背景包括管道铺设、线路安排、厂区布局、设备更新等领域。 迪杰斯特拉算法的思路: 迪杰斯特拉算法的思路是从始点出发,逐步顺序地向外探寻,每向外延伸一步都要求是最短的。这意味着,算法会...
迪杰斯特拉算法可以基于某一载体进行优化,本文主要是基于城市道路载体,希望对大家能有帮助。
迪杰斯特拉(Dijkstra)算法是图论中一个经典的单源最短路径算法,由荷兰计算机科学家艾兹格·迪杰斯特拉在1956年提出。这个算法主要用于解决带权重的有向图中从某一点到其余所有点的最短路径问题。在本案例中,我们...
总的来说,关键路径、迪杰斯特拉算法和弗洛伊德算法是解决路径优化问题的关键工具,广泛应用于项目管理、网络路由、地图导航等领域。结合MFC进行可视化开发,不仅可以提升学习的趣味性,也有助于提升编程和问题解决...
在实际应用中,迪杰斯特拉算法可能会遇到一些优化问题,例如负权边的存在会导致算法失效,这时需要采用其他算法如Bellman-Ford。此外,对于稀疏图(边的数量远小于节点数量的平方),使用邻接表可以节省空间。 总之...
以下是关于迪杰斯特拉算法的详细介绍以及如何应用于这个课设。 **迪杰斯特拉算法**: 迪杰斯特拉算法由荷兰计算机科学家艾兹格·迪杰斯特拉在1956年提出。它是一种贪心算法,每次选择当前未访问节点中距离源节点...
迪杰斯特拉(Dijkstra)算法则是图论中的一种著名算法,用于寻找带权有向图中从一个源节点到其他所有节点的最短路径。在本项目中,我们将深入探讨这个算法及其在数据结构中的应用。 迪杰斯特拉算法的基本思想是使用...
在本数据库课程设计中,我们关注的是《火车出行路线规划及售票系统》,这是一个结合了算法与数据库技术的实际应用项目。核心算法是迪杰斯特拉(Dijkstra)算法,它用于解决最短路径问题,帮助用户找到从一个城市到另...
7S迪杰斯特拉算法可能是对原算法的一种特定实现或者是在解决特定问题时的应用。 在迪杰斯特拉算法中,主要步骤如下: 1. 初始化:选择一个起始节点(通常称为源节点),将该节点的距离设为0,其他所有节点的距离设...
实现迪杰斯特拉算法 Dijkstra void main() { //设置初值 int u=1; //设源点的序号为1 for(int i=0; i; i++) { Visited[i]=0; path[i]=u-1; Distance[i]=Graph[u-1][i]; } Visited[u-1]=1; //源点已...
在实际应用中,迪杰斯特拉算法常用于解决网络路由、交通导航、社交网络分析等多种问题,例如计算互联网中两台计算机之间的最短路由,或者找出城市之间驾车的最短路线。其效率在优化后的实现下可以达到线性时间复杂度...
10. **实际应用**:迪杰斯特拉算法广泛应用于网络路由、GPS导航、社会网络分析等领域,寻找两点间最短的通信路径或最少的费用路径。 通过理解和实现迪杰斯特拉算法,我们可以学习到图的表示方法、优先队列的使用...
用MATLAB实现迪杰斯特拉算法来寻找最短路径,压缩包中DIJ为算法的执行程序,SymMatrix为将邻接矩阵补齐为对称矩阵的程序,两个graph文件存储的两个邻接矩阵,DIJ加载了其中一个进行计算。也可以自己重新编辑邻接矩阵...
在实际应用中,它广泛用于路由、网络优化以及图形算法等领域。这个算法的核心思想是通过不断更新节点的最短路径来逐步构建全局的最短路径树。 在给定的“使用标准模板库写迪杰斯特拉算法”中,我们重点关注两个关键...
迪杰斯特拉算法是由荷兰计算机科学家艾兹格·迪杰斯特拉在1956年提出的,它是一种解决单源最短路径问题的算法,特别适用于加权有向图或无向图。该算法的基本思想是从起始节点开始,逐步扩展到相邻节点,每次选取当前...
迪杰斯科拉(Dijkstra)算法是一种在加权图中寻找最短路径的经典算法,由荷兰计算机科学家艾兹格·迪杰斯科拉在1956年提出。这个算法主要用于解决单源最短路径问题,即从图中的一个特定顶点(源点)出发,找到到达...
迪杰斯特拉(Dijkstra)算法是解决单源最短路径问题的一种经典算法,由荷兰计算机科学家艾兹格·迪杰斯特拉在1956年提出。它主要用于寻找图中一个起点到其他所有点的最短路径。在这个例子中,问题是要帮助Kiki找到从...