题解 P1576 【最小花费】

· · 题解

这道题本质上就是一道最短路的变种，转账时候收取1%手续费可以理解为这条边边权为0.99，而且边权是相乘而不是相加

为了更好理解，这里解释一下样例：要求从1到3，如果从1到2，手续费1%，那么钱数就乘0.99；2到3再乘0.98，这样总倍数是0.9702，优于直接1给3的0.97倍，所以答案是100/0.97。

p.s.注意不是转化率，是到账100元最少需要的总费用！！！

这是我用priority_queue优化过的dijkstra写的代码

关于dijkstra的详细知识可以看P4779的题解或者最短路 - OI Wiki

#include <bits/stdc++.h>
using namespace std;
struct edge{
    int to,nxt;
    double dis;
}e[100002];
double head[2002],dis[2002];
bool vis[100002];
int n,m,s,cnt,a,b;
void addedge(int u,int v,int d){
    e[++cnt].dis=1.0-d/100.0;
    e[cnt].to=v;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
struct node{
    double dis;
    int pos;
    bool operator <(const node &x)const{
        return x.dis<dis;
    }
};
priority_queue<node>q;
void init(){
    for(int i=1;i<=n;i++)
        dis[i]=0x7fffffff;
}
void dijkstra(){
    dis[a]=1.0;
    q.push((node){1.0,a});
    while(!q.empty()){
        node tmp=q.top();
        q.pop();
        int x=tmp.pos;
        if(vis[x])continue;
        vis[x]=1;
        for(int i=head[x];i;i=e[i].nxt){
            int y=e[i].to;
            if(dis[y]>dis[x]*e[i].dis){
                dis[y]=dis[x]*e[i].dis;
                if(!vis[y])q.push((node){dis[y],y});
            }
        }
    }
}
int main() {
    int i;
    cin>>n>>m;
    init();
    for(i=0;i<m;i++){
        int u,v,d;
        scanf("%d%d%d",&u,&v,&d);
        addedge(u,v,d);
    }
    cin>>a>>b;
    dijkstra();
    printf("%.8lf",100/dis[b]);
    return 0;
}

copy题解的同志们发现“祖国江山一片红”——而且样例还过了，是不是很神奇？ 这是为什么呢？

让我们来分析一下题目

bug1：要求对方到账100元且自己花费最少，那么就是要求总倍数最高，也就是说

求的是最长路而不是最短路！！！！！

所以我们需要在松弛操作时找尽可能长的边，同时把运算符“<”重载成“>”，保证找到的路径最长

于是copy题解的同志们把这两处改了却发现“大红灯笼高高挂” 都在bug后面标序号1了，怎么可能没有bug2呢？

bug2：继续读题，可以发现题目中的第一行描述是：

在n个人中，某些人的银行账号之间可以互相转账。

互相！！！

由于这份代码的核心部分是P4779（单源最短路径）的变体，所以之前写的时候一直当转账是单向的在处理，其实这题的图是无向图，也就是说我们要 双向建边！

于是copy题解的同志加了一个addedge后发现“万紫千红总是春” 事实上因为建一条双向边相当于两条单向边，所以我们所有关于边的数组空间都要开2倍 （其实我所有数组都开了2倍）

献上码风奇特的代码（保证AC）

#include <bits/stdc++.h>
using namespace std;
struct edge{
    int to,nxt;
    double dis;
}e[200010];
double head[4010],dis[4010];
bool vis[200010];
int n,m,s,cnt,a,b;
void addedge(int u,int v,int d){ //建边
    e[++cnt].dis=1.0-d/100.0;
    e[cnt].to=v;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
struct node{
    double dis;
    int pos;
    bool operator <(const node &x)const{
        return x.dis>dis;  //注意重载成大于！！！
    }
};
priority_queue<node>q;
void init(){  //初始化
    for(int i=1;i<=n;i++)
        dis[i]=0;   //注意不要设置成正无穷！！！
}
void dijkstra(){   //优先队列优化的dijkstra
    dis[a]=1.0;
    q.push((node){1.0,a});
    while(!q.empty()){
        node tmp=q.top();
        q.pop();
        int x=tmp.pos;
        if(vis[x])continue;
        vis[x]=1;
        for(int i=head[x];i;i=e[i].nxt){
            int y=e[i].to;
            if(dis[y]<dis[x]*e[i].dis){  //注意这里是发现更大的dis时更新！！！
                dis[y]=dis[x]*e[i].dis;
                if(!vis[y])q.push((node){dis[y],y});
            }
        }
    }
}
int main() {
    int i;
    cin>>n>>m;
    init();
    for(i=0;i<m;i++){
        int u,v,d;
        scanf("%d%d%d",&u,&v,&d);
        addedge(u,v,d);
        addedge(v,u,d);  //注意建边2次！！！
    }
    cin>>a>>b;
    dijkstra();
    printf("%.8lf",100.0/dis[b]);  //注意是100/dis[b]
    return 0;
}