最小花费

本题为最短路的模板题，根据题意分析可知从1->3的代价是0.97 * 100，而从1->2->3的代价为100 * 0.98 * 0.99，比上一条更小，因此 可以总结出最短路的更新策略为如下

//其中j代表的是当前的最大比例,t代表的是到点t的最小比例,i代表的是从t->i的百分比
dist[j] = min(dist[j],dist[t]*w[i])

一开始做的时候没有注意比例，而是采用(1-dist[t]/100) * (1-w[i]/100),这样产生了精度误差，导致没发AC

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N = 1e6+10;

int n,m;
int be,en;
int h[N],ne[N],e[N],idx;
double dist[N],w[N];
int v[N];

void add(int a,int b,double c)
{
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;
}

double spfa()
{
    queue<int> q;
    q.push(be);
    dist[be] = 1;
    v[be] = true;

    while(q.size())
    {
        int t = q.front();
        q.pop();

        v[t] = false;
        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if((dist[j] < dist[t] * w[i]))
            {
                dist[j] = dist[t] * w[i];
                if(!v[j])
                {
                    v[j] = true;
                    q.push(j);
                }
            }
        }
    }

    return 100.0 / dist[en];
}

int main()
{
    memset(h, -1, sizeof h);
    scanf("%d%d",&n,&m);

    for(int i = 1; i <= n; i ++ )
    {
        dist[i] = 0;
    }

    for(int i = 0; i < m; i ++ )
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        //建图的时候就先把数据变成比例，避免产生精度误差
        add(a,b,(100.0 - c) / 100);
        add(b,a,(100.0 - c) / 100);
    }
    scanf("%d%d",&be,&en);

    double t =spfa();

    printf("%.8lf",t);

    return 0;
}