算法1

(Dijkstra) $O(mlogn)$

手续费乘积的最短路问题

C++ 代码

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

#define PII pair<double,int>
using namespace std;

const int N = 2010,M = 200005;
int h[M],e[M],ne[M],idx;
double w[M];
double dist[N];
bool st[N];

int n,m,s,t;

void add(int f,int u,double c){
    ne[idx] = h[f];
    w[idx] = 1.0/(1-0.01*c);
    e[idx] = u;
    h[f] = idx++;
}

void Dijkstra(){
    for(int i = 0;i<n;i++)dist[i+1] = 1e9;
    dist[s] = 1;
    priority_queue<PII,vector<PII>,greater<PII>>heap;
    heap.push({1.0,s});

    while(heap.size()){
        PII u = heap.top();
        heap.pop();
        double distance = u.first;
        int v = u.second;
        if(st[v])continue;
        st[v] = true;

        for(int i = h[v];i!=-1;i = ne[i]){
            int j = e[i];
            if(distance * w[i]<dist[j]){
                dist[j] = distance * w[i];
                heap.push({dist[j],j});
            }
        }
    }


}

int main(){
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i = 0;i<m;i++){
        int a,b;
        double c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    cin>>s>>t;
    Dijkstra();
    printf("%.8f",dist[t]*100);

    return 0;
}