1 solutions

  • 0
    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    struct Edge { int x, y, w; };
    vector<Edge> edges;
    int n, m, S, T;
    
    int find(int x, int* parent) {
        return parent[x] == x ? x : parent[x] = find(parent[x], parent);
    }
    
    int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
    
    int main() {
        cin >> n >> m;
        edges.resize(m);
        for (int i = 0; i < m; ++i) 
            cin >> edges[i].x >> edges[i].y >> edges[i].w;
        cin >> S >> T;
        sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
            return a.w < b.w;
        });
    
        int* parent = new int[n + 1];
        int ans_a = -1, ans_b = -1;
        for (int i = 0; i < m; ++i) {
            for (int k = 1; k <= n; ++k) parent[k] = k;
            for (int j = i; j < m; ++j) {
                int fx = find(edges[j].x, parent);
                int fy = find(edges[j].y, parent);
                if (fx != fy) parent[fx] = fy;
                if (find(S, parent) == find(T, parent)) {
                    if (ans_a == -1 || 
                        (double)edges[j].w / edges[i].w < (double)ans_a / ans_b) {
                        ans_a = edges[j].w;
                        ans_b = edges[i].w;
                    }
                    break;
                }
            }
        }
        delete[] parent;
    
        if (ans_a == -1) cout << "IMPOSSIBLE";
        else {
            int g = gcd(ans_a, ans_b);
            ans_a /= g; ans_b /= g;
            if (ans_b == 1) cout << ans_a;
            else cout << ans_a << '/' << ans_b;
        }
        return 0;
    }
    
    
    • 1

    Information

    ID
    257
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    10
    Tags
    (None)
    # Submissions
    3
    Accepted
    1
    Uploaded By