首页 > 代码库 > hdu 1596

hdu 1596

#include <stdio.h>#include <string.h>#include <algorithm>using namespace std;#define N 1005#define INF 0x3f3f3f3fdouble dis[N][N],d[N];double vis[N];double  dijkstral(int v0,int n,int t){    int i,x,y;    double temp;    for(i = 1 ; i <= n ; i++)    {        d[i] = dis[v0][i];        vis[i] = 0;    }    d[v0] = 1.0;    vis[v0] = 1;    for(i = 1 ; i <= n ; i++)    {        temp = 0.0 ;        for(y = 1 ; y <= n ; y++)           if(!vis[y] && temp<d[y]) temp = d[x=y];        if(temp == 0.0) return d[t];            vis[x] = 1;        for(y = 1 ; y <= n ; y++)            if(!vis[y] &&dis[x][y]*d[x]>d[y])                d[y] = d[x]*dis[x][y];    }    return d[t];}int main(){    int n,q,i,j,s,t;    while(~scanf("%d",&n))    {        for(i = 1 ; i <= n ; i++)            for(j = 1 ; j <= n ; j++)            scanf("%lf",&dis[i][j]);            scanf("%d",&q);            while(q--)            {                scanf("%d %d",&s,&t);                double ans = dijkstral(s,n,t);                if(ans == 0.0) printf("What a pity!\n");                else printf("%.3lf\n",ans);            }    }    return 0;}