题目传送：http://acm.hdu.edu.cn/showproblem.php?pid=1596
分析：Dijkstra变体，最短路径判断计算方式：Safe(P) = s(e1)*s(e2)…*s(ek) e1,e2,ek是P 上的边。 判断方式：lowcost[pre]*cost[pre][j]>lowcost[j]
代码：
//2013-10-30 10:54:06 Accepted 1596 1484MS 9788K 1836 B C++ 空信高手
#include <iostream>
#include <iomanip>
using namespace std; /*==================================================*\
| Dijkstra 数组实现O （N^2 ）
| Dijkstra --- 数组实现( 在此基础上可直接改为STL 的Queue实现)
| lowcost[] --- beg 到其他点的最近距离
| path[] -- beg为根展开的树，记录父亲结点
\*==================================================*/
const int N=;
int path[N],vis[N];
double cost[N][N],lowcost[N];
void Dijkstra(int n,int beg)
{
int i,j;
double max;
memset(vis,,sizeof(vis));
vis[beg]=;
for(i=; i<n; i++)
{
lowcost[i]=cost[beg][i];
path[i]=beg;
}
lowcost[beg]=;
path[beg]=-;
int pre=beg;
for(i=; i<n; i++)
{
max=;
for(j=; j<n; j++)
//下面的加法可能导致溢出，INF不能取太大
if(vis[j]==&&lowcost[pre]*cost[pre][j]>lowcost[j])
{
lowcost[j]=lowcost[pre]*cost[pre][j];
path[j]=pre;
}
for(j=; j<n; j++)
if(vis[j]==&&lowcost[j]>max)
{
max=lowcost[j];
pre=j;
}
vis[pre]=;
}
} int main()
{
// freopen("input.txt","r",stdin);
int n,m,i,j,a,b;
while(scanf("%d",&n)!=EOF&&n)
{
memset(cost,,sizeof(cost));
memset(lowcost,,sizeof(lowcost));
for(i=; i<n; i++)
for(j=; j<n; j++)
cin>>cost[i][j];
cin>>m;
while(m--)
{
cin>>a>>b;
Dijkstra(n,a-);
if(lowcost[b-]!=)cout<<setiosflags(ios::fixed)<<setprecision()<<lowcost[b-]<<endl;
else cout<<"What a pity!"<<endl;
}
}
return ;
}