hdu 1596 find the safest road(最短路，模版题)

题目

这是用Dijsktra做的，稍加改动就好，1000ms。。好水。。

#define  _CRT_SECURE_NO_WARNINGS

#include<string.h>
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;

const int MAXN=1010;  

#define typec double  
const typec INF=0x3f3f3f3f;//防止后面溢出，这个不能太大  
bool vis[MAXN];  
typec cost[MAXN][MAXN];
typec lowcost[MAXN];
void Dijkstra(int n,int beg)  
{  
    for(int i=1;i<=n;i++)
    {
        lowcost[i]=cost[beg][i];vis[i]=false;
    }
    for(int i=1;i<=n;i++)
    {
        typec temp=0;
        int k=-1;
        for(int j=1;j<=n;j++)
            if(!vis[j]&&lowcost[j]>temp)
            {
                temp=lowcost[j];
                k=j;
            }
        vis[k]=true;
        for(int l=1;l<=n;l++)
            if(!vis[l])
                if(lowcost[l]<lowcost[k]*cost[k][l])
                    lowcost[l]=lowcost[k]*cost[k][l];
    }
}


int main()
{
    int n,m,i,j,s,t;
    while(scanf("%d",&n)!=EOF)
    {

        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                scanf("%lf",&cost[i][j]);

        scanf("%d",&m);
        while(m--)
        {
            scanf("%d%d",&s,&t);
            Dijkstra(n,s);
            if(lowcost[t]==0)
                printf("What a pity!
");
            else 
                printf("%.3lf
",lowcost[t]);
        }
    }
    return 0;
}

听说floyd也能过，但我就这就不写了