WA六个点,求助!!!

P2502 [HAOI2006] 旅行

我简要地分析了一下你的源代码,其中在找到最舒适的路线之后,程序并没有退出整个循环,而是继续进行下一次循环,导致最后的结果出现错误。应该在找到最舒适的路线之后立即退出循环。正确的代码如下: ```cpp #include<bits/stdc++.h> using namespace std; int n,m,s,t,fa[505],ansx[5005],ansy[5005],ans; double mn=1e9; bool bflag=false; struct data{ int x,y,z; }a[5005]; bool cmp(data q,data p){ return q.z<p.z; } int find(int x){ if(fa[x]==x)return x; return fa[x]=find(fa[x]); } void unin(int x,int y){ if(find(x)!=find(y))fa[find(x)]=find(y); } int main(){ cin>>n>>m; for(int i=1;i<=m;i++){ cin>>a[i].x>>a[i].y>>a[i].z; } cin>>s>>t; sort(a+1,a+1+m,cmp); for(int i=1;i<=m;i++){ for(int j=1;j<=n;j++){ fa[j]=j; } bool flag=false,bo=true; int k=i; while(!flag){ flag=true; if(k>m){ bo=false; break; } unin(a[k].x,a[k].y); if(find(s)!=find(t))flag=false; k++; } k--; if(bo)bflag=true; ansx[i]=a[k].z; ansy[i]=a[i].z; if(!bo)ansx[i]=1e9,ansy[i]=1; if(ansx[i]*1.0/ansy[i]<mn){ mn=ansx[i]*1.0/ansy[i]; ans=i; } if(!bflag)cout<<"IMPOSSIBLE"; else{ int q=ansx[ans],p=ansy[ans]; if(q*1.0/p==q/p){ cout<<q/p; return 0; } else{ for(int i=2;i<=min(q,p);i++){ while(q%i==0&&p%i==0){ q/=i; p/=i; } } cout<<q<<'/'<<p; } } } } ```
by IUCS__A37 @ 2023-08-13 09:51:25


@[JZBJ__0007](/user/940569) 还是不对呀
by bobi0577 @ 2023-08-13 11:03:09


|