哪位巨佬能帮忙找哪里RE了
查看原帖
哪位巨佬能帮忙找哪里RE了
63931
LikeJ楼主2020/7/20 16:26
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,s,t,x1,y1,x2,y2,mmin=2147483647,fa[5005];
struct node
{
	int x,y,v;
}a[5005];
int find(int x)
{
	if(fa[x]==x)return x;
	else fa[x]=find(fa[x]);
}
void bcj(int x,int y)
{
	int x1=find(x),y1=find(y);
	if(x1!=y1)fa[x1]=y1;
}
bool pd(int x,int y)
{
	int x1=find(x),y1=find(y);
	if(x1!=y1)return true;
	else return false;
}
int gcd(int x,int y)
{
	while(x%y)
	{
		int z=x%y;
		x=y;
		y=z;
	}
	return y;
}
bool cmp(node x,node y)
{
	return x.v<y.v;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	 scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].v);
	scanf("%d%d",&s,&t); 
	sort(a+1,a+m+1,cmp);
	for(int i=1;i<m;i++)
	{
		int ok=0;
		for(int j=1;j<=n;j++)
		 fa[j]=j;
		bcj(a[i].x,a[i].y);
		for(int j=i+1;j<=m;j++)
		{
		 	if(pd(a[j].x,a[j].y))bcj(a[j].x,a[j].y);
		 	if(!pd(s,t)){ok=j;break;}
		}
		if(ok!=0&&a[ok].v-a[i].v<mmin)
		{
			x1=a[i].v;
			y1=a[ok].v;
			mmin=a[ok].v-a[i].v;
		}
	}	
	if(mmin==2147483647)cout<<"IMPOSSIBLE";
	else
	{
		x2=x1/gcd(x1,y1);
		y2=y1/gcd(x1,y1);
		if(y2%x2==0)cout<<y2/x2;
		else cout<<y2<<"/"<<x2;
	}
}

谢谢

2020/7/20 16:26
加载中...