题解 P1576 【最小花费】

简单的一道SPFA。同楼下大神，转化为求最长路，除一下就可以啦。（SPFA不会的自行百度） 重点提醒：数组开够！本人被此坑死了，交了好几遍…… 以下贴代码： ```cpp #include<cstdio> #include<cstring> #include<iostream> using namespace std; int n,m,cnt=0; int head[400001],nxt[400001],to[400001]; int q[400001],f[400001]; double dis[400001],val[400001]; void addedge(int x,int y,double z) { cnt++; nxt[cnt]=head[x]; head[x]=cnt; to[cnt]=y; val[cnt]=z; } void spfa(int a,int b) { int l=0,r=1,u; q[1]=a; f[a]=1; dis[a]=1; while(l<r) { u=q[++l];//手打队列~ f[u]=0; for(int i=head[u];i!=0;i=nxt[i]) { if(dis[to[i]]<dis[u]*val[i])//别忘是乘 { dis[to[i]]=dis[u]*val[i]; if(!f[to[i]]) { q[++r]=to[i]; f[to[i]]=1; } } } } } int main() { memset(dis,0,sizeof(dis)); memset(f,0,sizeof(f)); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { int x,y; double z; scanf("%d%d%lf",&x,&y,&z); addedge(x,y,double((100-z)/100));//邻接表 addedge(y,x,double((100-z)/100)); } int a,b; scanf("%d%d",&a,&b); spfa(a,b);//最短路，其实最长路(￢_￢) printf("%.8lf",100/double(dis[b])); return 0; } ```