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 3Sample Output
0.500 0.400 0.500 1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #include<iostream> 5 #define INF 0xfffffff 6 int n,m; 7 double pri[1111][1111]; 8 double dis[1010]; 9 int vis[1010]; 10 int b,c; 11 using namespace std; 12 void dijkstra() 13 { 14 memset(vis,0,sizeof(vis)); 15 vis[b]=1; 16 for(int i = 1;i <= n;i++) 17 dis[i]=pri[b][i]; 18 for(int i = 1;i <= n;i++) 19 { 20 double M=0; 21 int k=-1; 22 for(int j = 1;j <= n;j++) 23 { 24 if(!vis[j]&&dis[j]>M) 25 M=dis[j],k=j; 26 } 27 if(k==-1) 28 return ; 29 vis[k]=1; 30 for(int j = 1;j <= n;j++) 31 if(!vis[j]&&dis[j]<dis[k]*pri[k][j]) 32 dis[j]=dis[k]*pri[k][j]; 33 } 34 } 35 int main() 36 { 37 while(scanf("%d",&n)!=EOF) 38 { 39 for(int i = 1;i <= n;i++) 40 for(int j = 1;j <= n;j++) 41 pri[i][j]=i==j?1:INF; 42 double a; 43 int t; 44 for(int i = 1;i <= n;i++) 45 { 46 for(int j = 1;j <= n;j++) 47 { 48 scanf("%lf",&a); 49 pri[i][j]=a; 50 } 51 } 52 scanf("%d",&t); 53 while(t--) 54 { 55 scanf("%d %d",&b,&c); 56 dijkstra(); 57 if(dis[c]!=0) 58 printf("%.3lf\n",dis[c]); 59 else 60 printf("What a pity!\n"); 61 } 62 } 63 return 0; 64 } View Code
转载于:https://www.cnblogs.com/llal/p/5737310.html
相关资源：垃圾分类数据集及代码