1 条题解

  • 0
    @ 2023-11-27 13:33:55
    #include<bits/stdc++.h>
    using namespace std;
    typedef long long LL;
    typedef pair<LL,LL>PLL;
    const int N=5e3+5;
    const int inf=0x3f3f3f3f;
    struct node{
    	int x,y,c;
    }a[N];
    bool cmp(node n1,node n2){
    	return n1.c<n2.c;
    }
    int fa[N];
    int get(int x){
    	if(fa[x]==x)return x;
    	return fa[x]=get(fa[x]);
    }
    int main(){
    	int n,m;scanf("%d%d",&n,&m);
    	for(int i=1;i<=m;i++){
    		scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].c);
    	}
    	sort(a+1,a+m+1,cmp);
    	int s,t;scanf("%d%d",&s,&t);
    	PLL res={inf,1};
    	for(int i=1;i<=m;i++){
    		for(int j=1;j<=n;j++)fa[j]=j;
    		for(int j=i;j<=m;j++){
    			int x=a[j].x,y=a[j].y;
    			int tx=get(x),ty=get(y);
    			if(tx!=ty){
    				fa[tx]=ty;
    			}
    			if(get(s)==get(t)){
    				LL u=a[j].c*res.second;
    				LL v=res.first*a[i].c;
    				if(u<v){
    					res={a[j].c,a[i].c};
    				}
    				break;
    			}
    		}
    	}
    	if(res.first==inf){
    		puts("IMPOSSIBLE");
    	}
    	else{
    		int gcd=__gcd(res.first,res.second);
    		res.first/=gcd,res.second/=gcd;
    		if(res.second==1){
    			printf("%lld",res.first);
    		}
    		else printf("%lld/%lld",res.first,res.second);
    	}
    	return 0;
    }
    
    • 1

    信息

    ID
    1050
    时间
    1000ms
    内存
    256MiB
    难度
    6
    标签
    (无)
    递交数
    20
    已通过
    12
    上传者