深搜,啥都不是30pts
查看原帖
深搜,啥都不是30pts
416242
New_hope楼主2023/7/25 15:02
#include<bits/stdc++.h>
#define L 505
#define LL long long
using namespace std;

struct E{
    LL to,dis;
};
vector<E> edge[10*L];
LL fa[L],son,mother;
float ans;
bool vis[L];

LL find(LL k){
    if(fa[k] == k) return k;
    else return fa[k] = find(fa[k]);
}
LL gcd(LL a,LL b){
    if(a%b == 0) return b;
    else return gcd(b,a%b);
}
void dfs(LL now,LL e,LL maxn,LL minn)
{
    if(vis[now]) return;
    if(now == e){
        if((maxn*1.0/minn) < ans){
            ans = maxn*1.0/minn;
            son = maxn;
            mother = minn;
        }
        return;
    }

    vis[now] = 1;
    for(LL i = 0; i < (LL)edge[now].size(); i ++){
        E v = edge[now][i];
        dfs(v.to,e,max(maxn,v.dis),min(minn,v.dis));
    }
}
int main()
{
    LL n,m;
    cin >> n >> m;
    for(LL i = 1; i <= n; i ++) fa[i] = i;
    for(LL i = 1; i <= m; i ++){
        LL a,b,c;
        cin >> a >> b >> c;
        LL finda = find(a), findb = find(b);
        if(finda != findb) fa[a] = b;
        edge[a].push_back((E){b,c}); 
        edge[b].push_back((E){a,c});
    }

    LL s,e,finds,finde;
    cin >> s >> e;
    finds = find(s), finde = find(e);
    if(finds != finde){
        cout << "IMPOSSIBLE";
        exit(0);
    }

    ans = 30005;
    dfs(s,e,1,30005);
    
    LL t = gcd(son,mother);
    son /= t; mother /= t;
    if(mother == 1) printf("%lld",son);
    else printf("%lld/%lld",son,mother);
    return 0;
}
2023/7/25 15:02
加载中...