HDU 1596 find the safest road

最短路问题。

Dijkstra，SPFA，Floyd 都可求。题意非常明了，求最安全的路，乘起来就好了。

有个小优化就是SPFA 算过的起点就不再去算了。

还有推断一下终点，開始没推断，WA了一发。

#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#include<stack>
#include<iostream>
#include<list>
#include<set>
#include<cmath>
#define INF 0x7fffffff
#define eps 1e-6
#define LL long long
using namespace std;
int n,m;
struct edge
{
    int v;
    double s;
};
vector<edge>g[1001];
double dis[1001][1001];
bool spf[1001];
void SPFA(int start)
{
    queue<int>q;
    bool vis[1001];
    memset(vis,0,sizeof(vis));

    dis[start][start]=1;
    vis[start]=1;
    q.push(start);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        vis[u]=0;
        for(int j=0;j<g[u].size();j++)
        {
            int v=g[u][j].v;
            double s=g[u][j].s;
            if(dis[start][v]<dis[start][u]*s)
            {
                dis[start][v]=dis[start][u]*s;
                if(!vis[v])
                {
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=1;i<=n;i++)
        {
            g[i].clear();
            spf[i]=0;
        }

        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
        {
            double s;
            scanf("%lf",&s);
            if(i==j)continue;
            edge now;
            now.v=j,now.s=s;
            g[i].push_back(now);
        }
        scanf("%d",&m);
        memset(dis,0,sizeof(dis));
        while(m--)
        {
            int start,thend;
            scanf("%d%d",&start,&thend);
            if(!spf[start])
            {
                SPFA(start);
                spf[start]=1;
            }
            if(dis[start][thend]!=0&&thend>0&&thend<=n)//推断终点
            printf("%.3f
",dis[start][thend]);
            else
                puts("What a pity!");
        }
    }
}