题目链接
本来对弗洛伊德很没信心，1000个城市，还好，还是过了，最裸的有4000+ms，因为是无向图加了下优化，3000+ms，这个。。。。
#include <stdio.h> #include <string.h> double p[1001][1001]; int main() {int i,j,k,n,m,sv,ev;while(scanf("%d",&n)!=EOF){for(i = 1; i <= n; i ++)for(j = 1; j <= n; j ++)scanf("%lf",&p[i][j]);for(k = 1; k <= n; k ++)for(i = 1; i <= n; i ++)for(j = 1; j < i; j ++){if(p[i][j] < p[i][k]*p[k][j]){p[i][j] = p[i][k]*p[k][j];p[j][i] = p[i][j];}}scanf("%d",&m);for(i = 1; i <= m; i ++){scanf("%d%d",&sv,&ev);if(p[sv][ev] != 0)printf("%.3lf\n",p[sv][ev]);elseprintf("What a pity!\n");}}return 0;
}
