題目描述
在n個人中，某些人的銀行賬號之間可以互相轉賬。這些人之間轉賬的手續費各不相同。給定這些人之間轉賬時需要從轉賬金額里扣除百分之幾的手續費，請問A最少需要多少錢使得轉賬后B收到100元。
輸入
輸入包含多組測試用例。
對于每組樣例，第一行輸入兩個正整數n,m,分別表示總人數和可以互相轉賬的人的對數。（0<n<=2000）以下m行每行輸入三個正整數x,y,z。表示標號為x的人和標號為y的人之間互相轉賬需要扣除z%的手續費（z<100）。
最后一行輸入兩個正整數A,B。數據保證A與B之間可以直接或間接地轉賬
輸出
輸出A使得B到賬100元最少需要的總費用。精確到小數點后8位。
樣例輸入
3 3
1 2 1
2 3 2
1 3 3
1 3
樣例輸出
103.07153164
思路：這其實是最短路的一個變形，核心思路就是最短路的思想。
對于x->y的這一條路，收取利率是z，也就是說自己那拿到的利率是(100-v)/100，我們要想最后花的錢最少去得到100塊錢，那么我們就要想方設法使得100塊錢在總錢數中所占的比率越大才可以。所以需要對dijkstra算法就行一點改動，如下所示：

當利率小的時候我們要盡量把它變大。
樸素dijkstra
代碼如下：

#include<iostream> #include<cstdio> #include<cstring> #define ll long long using namespace std;const int maxx=1e4+100; struct edge{int to,next;double v; }e[maxx<<1]; double dis[maxx]; int vis[maxx],head[maxx],tot,n,m;inline void init() {tot=0;for(int i=1;i<=2*m+10;i++) head[i]=-1;for(int i=1;i<=n+10;i++) vis[i]=0,dis[i]=0; } inline void add(int u,int v,double s) {e[tot].next=head[u],e[tot].to=v,e[tot].v=s,head[u]=tot++; } inline double dijkstra(int s,int ee) {dis[s]=1.0;for(int i=head[s];i!=-1;i=e[i].next) dis[e[i].to]=dis[s]*e[i].v;vis[s]=1;for(int k=1;k<=n;k++){double _max=0;int to;for(int i=1;i<=n;i++) if(dis[i]>_max&&!vis[i]) _max=dis[i],to=i;vis[to]=1;for(int i=head[to];i!=-1;i=e[i].next){if(dis[e[i].to]<dis[to]*e[i].v&&!vis[e[i].to]) dis[e[i].to]=dis[to]*e[i].v; }}return (double)(100.0)/dis[ee]; } int main() {while(~scanf("%d%d",&n,&m)){init();int x,y,z;for(int i=1;i<=m;i++){scanf("%d%d%d",&x,&y,&z);add(x,y,(double)(100-z)/100);add(y,x,(double)(100-z)/100);}scanf("%d%d",&x,&y);printf("%.8lf\n",dijkstra(x,y));}return 0; }

運行時間是68ms
priority_queue優化后的代碼如下：

#include<bits/stdc++.h> #define ll long long using namespace std;const int maxx=1e4+100; struct edge{int to,next;double v; }e[maxx<<1]; struct node{int to;double v;node(int a,double c){to=a,v=c;}bool operator <(const node &a)const{return a.v>v;} }; double dis[maxx]; int vis[maxx],head[maxx],tot,n,m;inline void init() {tot=0;for(int i=1;i<=2*m+10;i++) head[i]=-1;for(int i=1;i<=n+10;i++) vis[i]=0,dis[i]=0; } inline void add(int u,int v,double s) {e[tot].next=head[u],e[tot].to=v,e[tot].v=s,head[u]=tot++; } inline double dijkstra(int s,int ee) {priority_queue<node> q;dis[s]=1.0;q.push(node(s,1.0));while(q.size()){node u=q.top();q.pop();if(vis[u.to]) continue;vis[u.to]=1;for(int i=head[u.to];i!=-1;i=e[i].next){int to=e[i].to;if(dis[to]<dis[u.to]*e[i].v) {dis[to]=dis[u.to]*e[i].v;q.push(node(to,dis[to]));}}}return (double)100.0/dis[ee]; } int main() {while(~scanf("%d%d",&n,&m)){init();int x,y,z;for(int i=1;i<=m;i++){scanf("%d%d%d",&x,&y,&z);add(x,y,(double)(100-z)/100);add(y,x,(double)(100-z)/100);}scanf("%d%d",&x,&y);printf("%.8lf\n",dijkstra(x,y));}return 0; }

優化后的運行時間是16ms，快很多了。
努力加油a啊

總結

以上是生活随笔為你收集整理的最小花费（最短路变形+中南大学复试机试）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。