杭电 1596 find the safest road (最短路)
The Find 短路 杭电
2023-09-14 09:09:01 时间
http://acm.hdu.edu.cn/showproblem.php?pid=1596
这道题目与杭电2544最短路的思想是一样的。仅仅只是是把+改成了*,输入输出有些不一样而已。
find the safest road
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 6985 Accepted Submission(s): 2475
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所在的城市和要去的城市
第一行: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<iostream> #include<cstring> #include<cstdio> using namespace std; double map[1010][1010],d[1010]; int v[1010]; int a,b,n; void Dijkstra(int s) { int i,p,j; double min=0; for (i=1; i<=n; i++) { d[i]=map[s][i]; v[i]=0; } v[s]=1; for (i=1; i<n; i++) { min=0; for (j=1; j<=n; j++) { if(!v[j] && d[j]>min) { p=j; min=d[j]; } } v[p]=1; if(min==0)break; for (j=1; j<=n; j++) { if(!v[j] && d[p]*map[p][j]>d[j]) { d[j]=d[p]*map[p][j]; } } } } int main() { int m,i,j; while(~scanf("%d",&n)) { for(i=1; i<=n; i++) { for(j=1; j<=n; j++) { scanf("%lf",&map[i][j]); } } scanf("%d",&m); for(i=0; i<m; i++) { scanf("%d%d",&a,&b); Dijkstra(a); if(d[b]==0) printf("What a pity!\n"); else printf("%.3lf\n",d[b]); } } return 0; }
相关文章
- “xxxxxxxxx”signer information does not match signer information of other classes in the same package
- feature counts定量时报错failed to find the gene identifier
- 【错误记录】编译 Linux 内核报错 ( Unable to find the ncurses package. )
- PHP 之道(PHP: The Right Way):书写更好的 PHP 代码
- ORA-19729: File string is not the initial version of the plugged in datafile ORACLE 报错 故障修复 远程处理
- ORA-22313: cannot use two versions of the same type “string” ORACLE 报错 故障修复 远程处理
- ORA-22955: The cardinality parameter is not within the allowed limits ORACLE 报错 故障修复 远程处理
- ORA-24417: Session pool size has exceeded the maximum limit ORACLE 报错 故障修复 远程处理
- ORA-30963: The indexed column is not of XMLType. ORACLE 报错 故障修复 远程处理
- ORA-31465: cannot obtain a lock on the subscription ORACLE 报错 故障修复 远程处理
- ORA-38438: getVarchar not possible due to “string” datatype in the attribute set ORACLE 报错 故障修复 远程处理
- ORA-46258: Cleanup not initialized for the audit trail ORACLE 报错 故障修复 远程处理
- ORA-48490: The field number exceeds the maximum number [string] ORACLE 报错 故障修复 远程处理
- ORA-53017: The installation file string has an incorrect document type ORACLE 报错 故障修复 远程处理
- ORA-53216: cannot export the ORDDataSource object with an external source ORACLE 报错 故障修复 远程处理
- ORA-55569: The UNDO_RETENTION parameter value should be atmost string, the _highthreshold_undoretention setting. ORACLE 报错 故障修复 远程处理
- ORA-00710: new tablespace name is the same as the old tablespace name ORACLE 报错 故障修复 远程处理
- ORA-01378: The logical block size (string) of file string is not compatible with the disk sector size (media sector size is string and host sector size is string) ORACLE 报错 故障修复 远程处理
- ORA-06811: TLI Driver: could not set the IPX network number at init ORACLE 报错 故障修复 远程处理
- ORA-09958: IMON: two processes with the same ORACLE pid are active ORACLE 报错 故障修复 远程处理
- ORA-13614: The template string is not compatible with the current advisor. ORACLE 报错 故障修复 远程处理
- ORA-16777: unable to find the destination entry of a standby database in V$ARCHIVE_DEST ORACLE 报错 故障修复 远程处理
- ORA-19008: Invalid version of the XMLType ORACLE 报错 故障修复 远程处理
- 修复 Ubuntu 中 “E: The package cache file is corrupted, it has the wrong hash”
- 「Linux 录屏软件下载」功能强大,操作简单!(Note: The translation of the title can be read as Linux Screen Recording Software Download: Powerful Functionality Simple Operation! (linux录屏软件下载)
- MySQL 145: Harness the Power of Relational Database Technology!(mysql145)
- Get the Time on Linux: A Quick Guide to Querying Current Time(linux查询当前时间)
- Exploring the Power of as86 Linux: The Ultimate Guide for Beginners!(as86linux)
- Exploring the Benefits and Features of Oracle Hosts for Your Business Needs(oraclehosts)
- 尝试攻克決勝難關The A to Z of Redis(the a什么redis)