30分大雾AC#1#1#4
查看原帖
30分大雾AC#1#1#4
677091
MnZnOIer楼主2024/8/19 19:24
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, m, f[505], st, ed, p, q;
double ans = 1e30, tmp;
struct node{int u, v, w;}a[5005];
bool cmp (node a, node b){return a.w > b.w;}
int find (int x){return (f[x] == x ? x : f[x] = find (f[x]));}
signed main ()
{
	ios::sync_with_stdio (0), cin.tie (0), cout.tie (0);
	cin >> n >> m;
	for (int i = 1; i <= n; ++ i)f[i] = i;
	for (int i = 1; i <= m; ++ i)
	{
		cin >> a[i].u >> a[i].v >> a[i].w;
		f[find (a[i].u)] = find (a[i].v);
	}
	cin >> st >> ed;
	if (find (st) != find (ed))
	{
		cout << "IMPOSSIBLE";
		return 0;
	}
	sort (a + 1, a + m + 1, cmp);
	for (int i = 1; i <= m; ++ i)
	{
		for (int j = 1; j <= n; ++ j)f[j] = j;
		for (int j = i; j <= m; ++ j)
		{
			int w1 = a[i].w, w2 = a[j].w, uu = a[j].u, vv = a[j].v;
			f[find (uu)] = find (vv);
			if (find (st) == find (ed))
			{
				tmp = double (w1 / w2);
				if (tmp < ans)
				{
					ans = tmp;
					p = w1, q = w2;
					break;
				}
			}
		}
	}
	int pqg = __gcd (p, q);
	if (p % q == 0)cout << p / q;
	else cout << p / pqg << '/' << q / pqg;
	return 0;
}
2024/8/19 19:24
加载中...