106 miles to Chicago---zoj2797（最短路问题，求概率，模板）

题目链接：http://www.icpc.moe/onlinejudge/showProblem.do?problemId=1797

题意是有 n 个点 m 条边，从a到b的不被抓的概率是p，让求从点1到点n的不被抓的最大概率；

Dijkstra套一下就可以了，注意初始化；

ab到bc不被抓的概率等于ab不被抓的概率乘上bc不被抓的概率；

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

#define met(a, b) memset(a, b, sizeof(a))
#define MOD 1000000007
#define N 2050
#define INF 0x3f3f3f3f

typedef long long LL;

int n, m, G[N][N], vis[N];

double dist[N];

double Dijkstra(int s)
{
    for(int i=1; i<=n; i++)
        dist[i] = G[s][i];

    vis[s] = 1;

    for(int i=1; i<=n; i++)
    {
        double Min = -INF;
        int Index = -1;

        for(int j=1; j<=n; j++)
        {
            if( !vis[j] && Min < dist[j])
            {
                Min = dist[j];
                Index = j;
            }
        }
        if(Index == -1)break;

        vis[Index] = 1;

        for(int j=1; j<=n; j++)
        {
            if( !vis[j] && dist[j] < dist[Index]*G[Index][j]/100.0)
            {
                dist[j] = dist[Index]*G[Index][j]/100.0;
            }
        }
    }
    return dist[n];
}

void Init()
{
    for(int i=0; i<=n; i++)
    {
        for(int j=0; j<=n; j++)
            G[i][j] = -INF;
        dist[i] = -INF;
        G[i][i] = vis[i] = 0;
    }
}

int main()
{
    int a, b, c;
    while(scanf("%d", &n), n)
    {
        Init();

        scanf("%d", &m);

        for(int i=1; i<=m; i++)
        {
            scanf("%d%d%d", &a, &b, &c);
            G[a][b] = G[b][a] = max(G[a][b], c);
        }

        double ans = Dijkstra(1);

        printf("%.6f percent
", ans);
    }
    return 0;
}