1 条题解
-
0
#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
- 上传者