find the safest road
题目：http://acm.hdu.edu.cn/showproblem.php?pid=1596
题意：一条从u 到 v 的通道P 的安全度为Safe(P) = s(e1)*s(e2)…*s(ek) e1,e2,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\n",dist[b]);
}
}
return 0;
}