1 solutions
-
0
Guest MOD
-
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