题目

acwing1126. 最小花费

题解

求A到B经过手续费之后的到账100元的初始最大值。每经过一个节点都要*一个小数,只要保证乘的这个小数最大即可。

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N=2010;
int n,m;
int start,target;
double dist[N],g[N][N];
bool st[N];

void dijstrka(){
    dist[start]=1;
    for(int i=1;i<=n;i++){
        int t=-1;
        for(int j=1;j<=n;j++){
            if(!st[j]&&(t==-1||dist[t]<dist[j])){
                t=j;
            }
        }
        st[t]=true;
        for(int j=1;j<=n;j++) dist[j]=max(dist[j],dist[t]*g[t][j]);
            
    }
}
int main(){
    cin>>n>>m;
    while(m--){
        int a,b,c;
        cin>>a>>b>>c;
        double z=(100.0-c)/100;
        g[a][b]=g[b][a]=max(z,g[a][b]);
    }
    cin>>target>>start;
    dijstrka();
    printf("%.8f\n",100/dist[target]);
    return 0;
}