思路:

判断两点是否联通,可以用并查集来判断.如果起点和终点联通了,那么我们不妨枚举最大边是多少,然后按顺序枚举那条较小边是多少.然后取个min就是最终的答案了.

代码:

#include <bits/stdc++.h>
using namespace std;
const int N=5005;
int fa[N],id;
struct node{
    int u,v,w;
}e[N];
inline void add(int u,int v,int w)
{
    e[++id].u=u;
    e[id].v=v;
    e[id].w=w;
}

int dsu(int u)
{
    if(fa[u]==u)    return u;
    else            return fa[u]=dsu(fa[u]); 
}

bool cmp(node A,node B)
{
    return A.w>B.w;
}

int main()
{
    int n,m,st,ed;scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)    fa[i]=i;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
        fa[dsu(u)]=dsu(v);
    }scanf("%d%d",&st,&ed);
    if(dsu(st)!=dsu(ed))
    {
        puts("IMPOSSIBLE");return 0;
    }sort(e+1,e+id+1,cmp);
    int fz,fm;double ans=1e10;
    for(int i=1;i<=id;i++)//枚举这个边当最大边使用. 
    {
        for(int j=1;j<=n;j++)    fa[j]=j;
        for(int j=i;j<=id;j++)
        {
            fa[dsu(e[j].u)]=dsu(e[j].v);
            if(dsu(st)==dsu(ed))
            {
                double temp=(double)e[i].w/(double)e[j].w;
                if(temp<ans)    fz=e[i].w,fm=e[j].w,ans=temp;
                break;
            }
        }
    }
    if(fz%fm==0)    printf("%d",fz/fm);
    else            printf("%d/%d",fz/__gcd(fz,fm),fm/__gcd(fz,fm));
    return 0;
}