[codevs 1001] 편안 한 코스.
우리 엄마................................................................................
나 는 약속 을 하지 않 을 것 이다.
#include
#include
#include
#include
using namespace std;
const int MAXN = 500 + 5;
const int MAXM = 5000 + 5;
struct edge
{
int f,t,v;
bool operator < (const edge &b)const
{
return v < b.v;
}
}l[MAXM];
int n,m;
int fa[MAXN];
int rank[MAXN];
void init()
{
for(int i = 1;i <= n;i ++)
fa[i] = i;
memset(rank,0,sizeof(rank));
return;
}
int find(int x)
{
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
bool same(int x,int y)
{
return find(x) == find(y);
}
void merge(int x,int y)
{
x = find(x);
y = find(y);
if(rank[x] < rank[y])
swap(x,y);
fa[x] = y;
if(rank[x] == rank[y])
rank[y] ++;
return;
}
struct fs
{
int fz,fm;
bool operator < (const fs &b)const
{
return fz * b.fm < b.fz * fm;
}
}zt[MAXM * MAXN];
int tot;
void solve(int s,int t)
{
tot = 0;
sort(l + 1,l + m + 1);
for(int i = 1;i <= m;i ++)
{
init();
zt[tot].fm = l[i].v;
for(int j = i;j <= m;j ++)
{
merge(l[j].f,l[j].t);
zt[tot].fz = l[j].v;
if(same(s,t))
break;
}
if(same(s,t))
tot ++;
}
return;
}
int gcd(int a,int b)
{
if(b == 0)
return a;
return gcd(b,a%b);
}
int s,t;
int main()
{
scanf("%d %d",&n,&m);
for(int i = 1;i <= m;i ++)
scanf("%d %d %d",&l[i].f,&l[i].t,&l[i].v);
scanf("%d %d",&s,&t);
solve(s,t);
sort(zt,zt + tot);
if(!tot)
{
puts("IMPOSSIBLE");
return 0;
}
if(zt[0].fz % zt[0].fm == 0)
{
printf("%d
",zt[0].fz / zt[0].fm);
return 0;
}
int k;
while((k = gcd(zt[0].fm,zt[0].fz)) - 1)
{
zt[0].fm /= k;
zt[0].fz /= k;
}
printf("%d/%d
",zt[0].fz,zt[0].fm);
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
항 저 우 전기 1878 오 라 회 로 (오 라 회 로 의 판단)오 라 회 로 는 펜 이 지면 을 떠 나 지 못 하 게 그림 의 각 변 을 한 번 만 그 릴 수 있 고 출발점 으로 돌아 갈 수 있 는 회 로 를 말한다.이제 오 라 회 로 가 있 는 지 그림 을 정 해 주 시 겠 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.