最小花费

思路

这道题可以用 Dijkstra 算法解决。有两种思路：

1. 采用正向思考，从节点 $u\rightarrow v$ ，要使得花费 RES 最小，仅仅使得其累乘的系数最大即可

$$ RES\times \prod_{i=u}^{v}w_{i,ne[i]}=100 $$

因此转变为求最大系数（距离），但是要注意使用大根堆less，memset初始化问题，以及更新的条件判断（小于还是大于）

1. 采用逆向思考，从目标节点到起始节点 $u\leftarrow v$ 。即可定义 $dist[v]=100$，进行 Dijkstra 到节点 $u$

注意

1. 大根堆和小根堆，取决于求最长还是最短问题。
2. 注意两次 add 。最开始没有注意到两个可以互相转账导致错误。
3. 有时候调试代码出现错误结果，但是实际上提交会 AC 。譬如第二种方法我以为有问题，其错误结果高达100多位数，导致我浪费半个小时排BUG

代码

方法1

#include<bits/stdc++.h>
using namespace std;
const int N=2010,M=2e5+10;
int h[N],e[M],ne[M],w[M];
int idx;
double dist[N];
int st[N];
typedef pair<double,int>PII;
priority_queue<PII,vector<PII>,less<PII>>heap;
int n,m;
void add(int a,int b,int c){
    e[idx]=b;
    ne[idx]=h[a];
    w[idx]=c;
    h[a]=idx++;
}
void dijkstra(int u,int v){
    dist[u]=1;
    heap.push({1,u});
    while(heap.size()){
        auto fr=heap.top();
        heap.pop();
        int ver=fr.second;
        if(st[ver])continue;
        st[ver]=1;
        for(int i=h[ver];i!=-1;i=ne[i]){
            int j=e[i];
            if(dist[j]<dist[ver]*(1-0.01*w[i])){
                dist[j]=dist[ver]*(1-0.01*w[i]);
                heap.push({dist[j],j});
            }
        }
    }
    cout<<setiosflags(ios::fixed)<<setprecision(8)<<100/dist[v]<<endl;
}

int main(){
    memset(h,-1,sizeof h); 
    cin>>n>>m;
    while(m--){
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    int u,v;cin>>u>>v;
    dijkstra(u,v);

}

方法2

#include<bits/stdc++.h>
using namespace std;
const int N=2010,M=2e5+10;
int h[N],e[M],ne[M],w[M];
int idx;
double dist[N];
int st[N];
typedef pair<double,int>PII;
priority_queue<PII,vector<PII>,greater<PII>>heap;
int n,m;
void add(int a,int b,int c){
    e[idx]=b;
    ne[idx]=h[a];
    w[idx]=c;
    h[a]=idx++;
}
void dijkstra(int u,int v){
    memset(dist,0x7f,sizeof dist);

    dist[v]=100;
    heap.push({100,v});
    while(heap.size()){
        auto fr=heap.top();
        heap.pop();
        int ver=fr.second;
        if(st[ver])continue;
        st[ver]=1;
        for(int i=h[ver];i!=-1;i=ne[i]){
            int j=e[i];
            if((dist[j]>(dist[ver]/(1-0.01*w[i])))){
                //cout<<"renew"<<j<<" "<<ver<<" "<<dist[j]<<endl;
                dist[j]=dist[ver]/(1-0.01*w[i]);
                heap.push({dist[j],j});
            }
        }
    }
    cout<<setiosflags(ios::fixed)<<setprecision(8)<<dist[u]<<endl;
}

int main(){
    //不要对dist做 memset 0x3f，因为其为double，每个字节取0x3f会得到极小的数而不是大数。
    memset(h,-1,sizeof h); 
    cin>>n>>m;
    while(m--){
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    int u,v;cin>>u>>v;
    dijkstra(u,v);

}