【SPFA】hdu 1596 find the safest road

find the safest road
タイトル:http://acm.hdu.edu.cn/showproblem.php?pid=1596
uからvまでのチャネルPの安全度はSafe(P)=s(e 1)**s(e 2)……***s(ek)e 1,ek 2,ekはPの端で、一番安全な道を探しています.
spfaで一番短絡を求めます.
コード:

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
#define inf 0x7ffffff
double cost[1005][1005];
double dist[1005];
bool visit[1005];
int n,m;
void spfa(int now)
{
    memset(visit,false,sizeof(visit));
    memset(dist,0,sizeof(dist));
    dist[now]=1;
    queue<int> q;
    q.push(now);
    for(; !q.empty();)
    {
        now=q.front();
        q.pop();
        visit[now]=false;
        for(int i=1; i<=n; ++i)
        {
            if(i==now) continue;
            if(dist[i]<dist[now]*cost[now][i])
            {
                dist[i]=dist[now]*cost[now][i];
                if(!visit[i])
                {
                    q.push(i);
                    visit[i]=true;
                }
            }
        }
    }
    return;
}
int main()
{
    int a,b;
    for(; ~scanf("%d",&n);)
    {
        for(int i=1; i<=n; ++i)
            for(int j=1; j<=n; ++j)
                scanf("%lf",&cost[i][j]);
        scanf("%d",&m);
        for(; m--;)
        {
            scanf("%d%d",&a,&b);
            spfa(a);
            if(dist[b]==0) puts("What a pity!");
            else printf("%.3f
",dist[b]);
        }
    }
    return 0;
}

ソース:http://blog.csdn.net/ACM_Ted