hdu1596 find the safest road 最短路也能求最大值
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2477 Accepted Submission(s): 978
Problem DescriptionInputOutputSample InputSample OutputAuthor#include<stdio.h>#include<string.h>int n,used[1005];double map[1005][1005],min[1005];void find_short(int s){int i,j,pos;double mm;memset(used,0,sizeof(used));for(i=1;i<=n;i++)min[i]=map[s][i];min[s]=1;used[s]=1;for(i=2;i<=n;i++){pos=0;mm=-1;for(j=1;j<=n;j++){if(!used[j]&&mm<min[j]){pos=j;mm=min[j];}}used[pos]=1;if(mm==-1) break;for(j=1;j<=n;j++)if(!used[j]&&min[pos]*map[pos][j]>min[j])min[j]=min[pos]*map[pos][j];}}int main(){int i,j,m,s,e;while(scanf("%d",&n)!=EOF){for(i=1;i<=n;i++)for(j=1;j<=n;j++)scanf("%lf",&map[i][j]);scanf("%d",&m);while(m--){ scanf("%d %d",&s,&e);find_short(s);if(min[e]!=0) printf("%.3lf\n",min[e]);else printf("What a pity!\n");}}return 0;}
