走亲访友

坐车最长的时间和坐车最短的时间的比值尽可能的小。

输入格式：

第一行输入两个正整数 $,，分别代表站点的个数以及所有站点之间路的条数。$

接下来的

最后一行输入两个正整数分别代表小丁家所在的站点和小丁姥姥家所在的站点。

输出格式：

若不能到达姥姥家，输出 IMPOSSIBLE，否则输出一个数代表最小的时间比。

如果需要，输出一个最简分数。

输入样例:

输出样例：

5/4

#include <bits/stdc++.h>

#define int long long
using namespace std;

int n, m, pre[505], fenzi, fenmu;
double temp = 0x3f3f3f3f;
struct edge {
    int s, t, w;
} e[5005];

void init() {
    for (int i = 1; i <= n; i++)
        pre[i] = i;
}

int find(int x) {
    if (pre[x] == x)
        return x;
    return pre[x] = find(pre[x]);
}

void merge(int x, int y) {
    pre[find(x)] = find(y);
}

int cmp(edge a, edge b) {
    return a.w < b.w;
}

signed main() {
    //freopen("in", "r", stdin);
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
        cin >> e[i].s >> e[i].t >> e[i].w;
    sort(e + 1, e + m + 1, cmp);
    int u, v;
    cin >> u >> v;
    for (int i = 1; i <= m; i++) {
        double maxx = -1, minx = 0x3f3f3f3f;
        init();
        for (int j = i; j <= m; j++) {
            merge(e[j].s, e[j].t);
            maxx = max(maxx, 1.0 * e[j].w);
            minx = min(minx, 1.0 * e[j].w);
            if (find(u) == find(v)) {
                if (maxx / minx < temp) {
                    temp = maxx / minx;
                    fenzi = maxx;
                    fenmu = minx;
                }
                break;
            }
        }
    }
    if (temp == 0x3f3f3f3f) cout << "IMPOSSIBLE" << endl;
    else {
        int g = __gcd(fenzi, fenmu);
        fenzi /= g;
        fenmu /= g;
        if (fenmu == 1) cout << fenzi << endl;
        else cout << fenzi << "/" << fenmu << endl;
    }
    return 0;
}

View Code

并查集对关系的维护

maxx/minn的最小每种都找一遍在这之前可以排浩顺序，按照w（毕竟题目就是求的这个）

剩下的就简单了