旅行 题解

洛谷 P2502

解题思路

将速度从小到大排
枚举断点
连接两个点
假如起点可到达终点
更新答案
输出记得化简

---

代码

#include<algorithm> 
#include<iostream>
#include<cstdio>
using namespace std;
int xx,yy,ta,wo,n,m,s,t;
double ans=2147483647;
int f[1000010];
struct hy{
	int x,y,p;
}h[10010];
bool cmp(hy t,hy x)
{
	 return t.p<x.p; 
}
int find(int x)  //寻找父节点
{
	if (f[x]==x) return x;
	return f[x]=find(f[x]);
}
void lj(int x,int y)  //合并
{
	 xx=find(x),yy=find(y); 
	 if (xx!=yy)
		f[xx]=yy; 
}
int hj(int x,int y)  //化简
{
	int r=x%y;
	while (r!=0)
	{ 
		  x=y;
		  y=r;
		  r=x%y;  
	} 
	return y;
}
int main()
{
	scanf("%d%d",&n,&m); 
	for (int i=1;i<=m;i++)
		scanf("%d%d%d",&h[i].x,&h[i].y,&h[i].p);
	scanf("%d%d",&s,&t);
	sort(h+1,h+m+1,cmp);  //快排
    xx=find(s);
    for (int i=1;i<=m;i++)
    {
    	for (int j=1;j<=n;j++)
    	    f[j]=j;
        int j=i; 
		while (j<=m)
		{
			  lj(h[j].x,h[j].y);  //连接两点
			  if (find(s)==find(t))  //起点已可到达终点
		      {
		      	 if (double(h[j].p)/double(h[i].p)<ans)  //更新答案
		      	 { 
		      	 	 ans=double(h[j].p)/double(h[i].p); 
		      	 	 ta=h[j].p;
		      	 	 wo=h[i].p;
		      	 }
		      	 break;
		      }
		      j++; 
		}
    } 
    if (ans!=2147483647)
       if (ta%wo==0)
          printf("%d\n",ta/wo);  //直接输出
          else {
          	   xx=hj(ta,wo);  //化简输出
               printf("%d/%d\n",ta/xx,wo/xx);
          }
       else printf("IMPOSSIBLE");
    return 0;
}