两种做法：
1.边的权值为手续费z，从b向a跑最短路，边跑边处理答案
2.边的权值为汇率，从a向b跑最短路，边跑边处理答案
#include<cstdio> #include<iostream> #include<queue> using namespace std; queue<double>q; double path[100010],n,m,z,dis[100010],vis[100010]; int x,y,A,B,k; struct node{ int u,v,nxt; double w; }edge[200010]; void add(int xx,int yy,double zz) { edge[++k].u =xx; edge[k].v =yy; edge[k].w =1-zz/100; edge[k].nxt =path[xx]; path[xx]=k; } int main() { scanf("%lf%lf",&n,&m); for(int i=1;i<=m;++i) { scanf("%d%d%lf",&x,&y,&z); add(y,x,z);add(x,y,z); } scanf("%d%d",&A,&B); for(int i=0;i<=n;++i) dis[i]=0x3fff; dis[B]=100;vis[B]=1; q.push(B); while(!q.empty()) { int now=q.front() ; q.pop() ; vis[now]=0; for(int i=path[now];i;i=edge[i].nxt ) { if(dis[edge[i].v]>dis[edge[i].u]/edge[i].w) { dis[edge[i].v]=dis[edge[i].u]/edge[i].w; if(!vis[edge[i].v]) { q.push(edge[i].v ); vis[edge[i].v]=1; } } } } printf("%.8lf",dis[A]); return 0; }
#include<iostream> #include<cstdio> #include<queue> #include<cstring> using namespace std; const int N=2507,M=1e6; struct node{ int u,v,nxt; double w; }e[M<<1]; int n,m,num,s,t,head[N]; double dis[N]; bool vis[N]; queue<int>q; int qread() { int x=0; char ch=getchar(); while(ch<'0' || ch>'9')ch=getchar(); while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; } void Add(int u,int v,int w) { e[++num].u=u; e[num].v=v; e[num].w=1.0-w/100.0; e[num].nxt=head[u]; head[u]=num; } void SPFA() { for(int i=1;i<=n;++i) dis[i]=100000.0; dis[t]=100;vis[t]=1; q.push(t); int u,v; while(!q.empty()) { u=q.front();q.pop(); vis[u]=0; for(int i=head[u];i;i=e[i].nxt) { v=e[i].v; if(dis[v]>dis[u]/e[i].w) { dis[v]=dis[u]/e[i].w; if(!vis[v]) { vis[v]=1; q.push(v); } } } } } int main() { scanf("%d%d",&n,&m); int u,v,w; for(int i=1;i<=m;i++) { u=qread();v=qread();w=qread(); Add(u,v,w); Add(v,u,w); } scanf("%d%d",&s,&t); SPFA(); printf("%.8lf ",dis[s]); return 0; }