最小花费(变向求最长路)

题意:https://www.luogu.com.cn/problem/P1576

在n个人中，某些人的银行账号之间可以互相转账。这些人之间转账的手续费各不相同。给定这些人之间转账时需要

从转账金额里扣除百分之几的手续费，请问A最少需要多少钱使得转账后B收到100元。

最小花费(变向求最长路)

看这张图，根据上图关系容易算出A的花费应该为100/（0.86*0.98）

换句话说，就是100/(路上的花费)

让A最小就是让花费最大

由此从A向C跑最长路。只不过原来花费相加，现在相乘。

但就算到了这里，还是有几点要格外小心。

Ⅰ用迪杰拉斯特的话，定义结构体优先级要注意。因为是最长路，所以要边长大的先出来。

Ⅱ链式前向星加边时，边权要转化为小数。如果直接用整数求最长路是行不通的，因为大于1的数可以在两个点间来回跑，而且会一直变大。

#include <bits/stdc++.h>
using namespace std;
const int maxn=200008;
int n,m,s,t;
struct edge{
    int nxt,to;
    double w;
}d[maxn];//链式前向星 
struct node{
    int num;double x;
    bool operator <(const node &tmp)const{
        return x<tmp.x;
    } //为了优先队列 
}temp;
double dis[maxn];
int head[maxn],cnt=1;
void add(int u,int v,double w){
    d[cnt].to=v;d[cnt].nxt=head[u];
    d[cnt].w=w;head[u]=cnt++;
}//加边
int vis[maxn];
void dij(int s)//迪杰特斯拉
{
    priority_queue<node>q;
    dis[s]=1;
    temp.num=s;temp.x=1.0;q.push(temp);
    while(!q.empty()){
        node ans=q.top();
        q.pop();
        if(vis[ans.num])    continue;
        vis[ans.num]=1;
        for(int i=head[ans.num];i;i=d[i].nxt)
        {
            edge e=d[i];
            if(dis[e.to]<dis[ans.num]*e.w){
                dis[e.to]=dis[ans.num]*e.w;
                if(vis[e.to])    continue;
                temp.num=e.to,temp.x=dis[e.to];
                q.push(temp);
            }
        }
    }
    return;
} 
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int l,r;double t;
        cin>>l>>r>>t;
        add(l,r,1.0-t*1.0/100);
        add(r,l,1.0-t*1.0/100);
    }
    int q,w;
    cin>>q>>w;
    dij(q);
    double ans=0;
    ans=100*1.0/(dis[w]);
    printf("%.8lf",ans);
}

原文链接: https://www.cnblogs.com/iss-ue/p/12518550.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/374336

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

最小花费(变向求最长路)

相关推荐