题解 P1576 【最小花费】

其实是最短路. 把起点和终点反过来求最短路. 就是松弛操作改一改就好. ```cpp #include<bits/stdc++.h> using namespace std; int read() { char s; int k=0,base=1; while((s=getchar())!='-'&&s!=EOF&&!(s>='0'&&s<='9')); if(s==EOF)exit(0); if(s=='-')base=-1,s=getchar(); while(s>='0'&&s<='9') { k=k*10+(s-'0'); s=getchar(); } return k*base; } void write(int x) { if(x<0) { putchar('-'); write(-x); } else { if(x/10)write(x/10); putchar(x%10+'0'); } } int n,m,X,Y,Z,id,s,t,u,v; int to[4000010]; int wi[4000010]; int ne[4000010]; int po[4000010]; int vis[4010]; double dis[4000]; queue<int> q; inline void add(int x,int y,int z) { id++; to[id]=y; wi[id]=z; ne[id]=po[x]; po[x]=id; } int main() { n=read(); m=read(); for (int i=1;i<=m;i++) { X=read();Y=read();Z=read(); add(X,Y,Z);//加双向边 add(Y,X,Z); } t=read();s=read();//起点和终点反一下 for (int i=0;i<=n+1;i++) dis[i]=23333333.0; q.push(s); dis[s]=100.0; vis[s]=1; while (!q.empty()) { u=q.front();q.pop(); vis[u]=0; for (int i=po[u];i;i=ne[i]) { v=to[i]; if (dis[v]>(double)(dis[u])/(1-0.01*wi[i]))//松弛操作 { dis[v]=(double)(dis[u])/(1-0.01*wi[i]); if (vis[v]==0)//入队 { vis[v]=1; q.push(v); } } } } printf("%.8lf",dis[t]);//输出 return 0; } ```