题解 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](https://www.luogu.org/problem/P4779)的题解或者[最短路 - OI Wiki](https://oi-wiki.org/graph/shortest-path/) ```cpp #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：继续[读题](https://www.luogu.org/problem/P1576)，可以发现题目中的第一行描述是： ### 在n个人中，某些人的银行账号之间可以*互相*转账。 ## 互相！！！ 由于这份代码的核心部分是P4779（**单源**最短路径）的变体，所以之前写的时候一直当转账是单向的在处理，其实这题的图是无向图，也就是说我们要 _双向建边！_ ~~于是copy题解的同志加了一个addedge后发现“万紫千红总是春”~~ 事实上因为建一条双向边相当于两条单向边，所以我们所有关于边的数组空间都要开2倍 ~~（其实我所有数组都开了2倍）~~ 献上码风奇特的代码（保证AC） ```cpp #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; } ```