hdu 1596 概率dijstra

这道题中，边权属于[0,1]，并且多段路的长度为各段的乘积。联系dijstra算法的特点，我们可以采取类似于dijstra的贪心策略，每次选取到源点距离最大的点，因为现在源点到其他的点的距离都不大于这个距离，以后如果再加上某一段，总的长度便会乘上一个不大于1的数字，就更不可能比现在选取的这个距离大了，所以按照和dijstra算法一样的流程可以求出“最安全的路”。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

const double eps = 1e-4;
const int N = 1001;
double g[N][N];
double dist[N];
bool visit[N];
int n, m;

void dij( int s )
{
    memset( visit, false, sizeof(visit) );
    for ( int i = 0; i <= n; i++ )
    {
        dist[i] = 0;
    }
    dist[s] = 1;
    for ( int i = 1; i <= n; i++ )
    {
        int u = 0;
        for ( int j = 1; j <= n; j++ )
        {
            if ( !visit[j] && dist[j] > dist[u] )
            {
                u = j;
            }
        }
        visit[u] = true;
        for ( int j = 1; j <= n; j++ )
        {
            if ( !visit[j] && g[u][j] > eps )
            {
                if ( dist[u] * g[u][j] > dist[j] )
                {
                    dist[j] = dist[u] * g[u][j];
                }
            }
        }
    }
}

int main ()
{
    while ( scanf("%d", &n) != EOF )
    {
        for ( int i = 1; i <= n; i++ )
        {
            for ( int j = 1; j <= n; j++ )
            {
                scanf("%lf", &g[i][j]);
            }
        }
        scanf("%d", &m);
        while ( m-- )
        {
            int s, t;
            scanf("%d%d", &s, &t);
            dij(s);
            if ( dist[t] < eps )
            {
                printf("What a pity!
");
            }
            else
            {
                printf("%.3lf
", dist[t]);
            }
        }
    }
    return 0;
}