[HAOI2006]旅行COMF

第一行包含两个正整数，N和M。
下来的M行每行包含三个正整数：x，y和v。表示景点x到景点y之间有一条双向公路，车辆必须以速度v在该公路上行驶。
最后一行包含两个正整数s，t，表示想知道从景点s到景点t最大最小速度比最小的路径。s和t不可能相同。
1 < N ≤ 500,1 ≤ x,y ≤ N，0 < v < 30000，0 < M ≤ 5000

C++(clang++11) 解法, 执行用时: 250ms, 内存消耗: 632K, 提交时间: 2021-01-14 17:29:31

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;
struct edge
{
	int l,r,w;
}d[maxn];
int mu,zi,n,m,s,t,pre[maxn];
double ans = 1e9;
int gcd(int a,int b){ return b==0?a:gcd(b,a%b); }
void UP(int down,int up)
{
	if( (double)up/down>ans )	return;
	ans = (double)up/down;
	mu = up, zi = down;	
}
bool com(edge a,edge b){ return a.w<b.w; }
int find(int x){ return x==pre[x]?x:pre[x]=find(pre[x]); }
void join(int q,int w){ pre[find(q)]=find(w); return; }
int main()
{
	cin >> n >> m;
	for(int i=1;i<=m;i++)
		scanf("%d%d%d",&d[i].l,&d[i].r,&d[i].w);

	cin >> s >> t;
	sort( d+1,d+1+m,com );
	for(int i=1;i<=m;i++)
	{
		for(int q=1;q<=n;q++)	pre[q] = q;
		for(int j=i;j<=m;j++)
		{
			join( d[j].l,d[j].r );
			if( find(s)==find(t) )	{ UP(d[i].w,d[j].w); break; }
		}
	}
	if( zi==mu&&zi==0 )	printf("IMPOSSIBLE");
	else if( mu%zi==0 )	cout << mu/zi;
	else	cout << mu/gcd(zi,mu) << "/" << zi/gcd(zi,mu);
}

详情