最短路
#include<stdio.h> #include<string.h> #define max 0.0 double map[1001][1001],f[1001]; int n,m,st,en,mark[1001]; void Dijkstra() { int i,j,k; double min; for(i=1;i<=n;i++) f[i]=map[st][i]; for(i=1;i<=n;i++) { min=max; for(j=1;j<=n;j++) if(!mark[j]&&min<f[j]) {min=f[j];k=j;} if(min==max)break; mark[k]=1; for(j=1;j<=n;j++) if(!mark[j]&&f[j]<f[k]*map[k][j]) f[j]=f[k]*map[k][j]; } if(f[en]>0) printf("%.3f\n",f[en]); else printf("What a pity!\n"); } int main() { int i,j,a,b,c; while(scanf("%d",&n)!=EOF) { memset(mark,0,sizeof(mark)); for(i=1;i<=n;i++) for(j=1;j<=n;j++) scanf("%lf",&map[i][j]); scanf("%d",&m); while(m--) { memset(mark,0,sizeof(mark)); scanf("%d%d",&st,&en); Dijkstra(); } } return 0; }