90分,wa了一个点,求助
查看原帖
90分,wa了一个点,求助
377440
Y2y7m楼主2022/3/2 22:43
#include<bits/stdc++.h>

using namespace std;
#define int long long
int root[510];
struct dot
{
	int x,y,z;
}a[10010];
int gcd(int a,int b)
{
	if(b==0)
		return a;
	return gcd(b,a%b);
}
int getroot(int x)
{
	if(root[x]==x)
		return x;
	return root[x]=getroot(root[x]);
}
bool cmp(dot a,dot b)
{
	return a.z<b.z;
}
signed main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	    cin>>a[i].x>>a[i].y>>a[i].z;
	int s,t;
	cin>>s>>t;
	sort(a+1,a+m+1,cmp);
	int ans1=0,ans2=0;
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=n;j++)
			root[j]=j;
		int p;
		bool f=0;
		for(int j=i;j<=m;j++)
		{
			int fx=getroot(a[j].x),fy=getroot(a[j].y);
			root[fx]=fy;
			if(getroot(s)==getroot(t))
			{
				f=1;
				p=j;
				break;				
			}
		}
		if(i==1&&!f)
		{
			cout<<"IMPOSSIBLE"<<endl;
			return 0;
		}
		if(getroot(s)!=getroot(t))
			break;
		if(ans1*a[i].z>=ans2*a[p].z)
			ans1=a[p].z,ans2=a[i].z;
	}
	int e=gcd(ans1,ans2);
	if(e==ans1)
	    cout<<ans2/e<<endl;
	else if(ans2==t)
		cout<<ans1/e<<endl;
	else
		cout<<ans1/e<<"/"<<ans2/e<<endl;
	return 0;
}
2022/3/2 22:43
加载中...