旅行

Description

Z小镇是一个景色宜人的地方，吸引来自各地的观光客来此旅游观光。Z小镇附近共有N个景点（编号为1,2,3,…,N），这些景点被M条道路连接着，所有道路都是双向的，两个景点之间可能有多条道路。也许是为了保护该地的旅游资源，Z小镇有个奇怪的规定，就是对于一条给定的公路Ri，任何在该公路上行驶的车辆速度必须为Vi。速度变化太快使得游客们很不舒服，因此从一个景点前往另一个景点的时候，大家都希望选择行使过程中最大速度和最小速度的比尽可能小的路线，也就是所谓最舒适的路线。

Input

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

Output

如果景点s到景点t没有路径，输出“IMPOSSIBLE”。否则输出一个数，表示最小的速度比。如果需要，输出一个既约分数。

Sample Input

样例1
4 2
1 2 1
3 4 2
1 4

样例２
3 3
1 2 10
1 2 5
2 3 8
1 3

样例3
3 2
1 2 2
2 3 4
1 3

Sample Output

样例1
IMPOSSIBLE

样例2
5/4

样例3
2

Hint

【数据范围】
1＜N＜＝500
1＜＝x,y＜＝N，0＜v＜30000，x≠y
0＜M＜＝5000

题目分析

找出一条能连通两个目标点的路径，使这条路径的最大速度与最小速度的比值最小

解题思路

这题我们可以用并查集，把边排序一遍，然后枚举起始边，并查集连续，直到两个点先连为止，再求最大速度和最小速度，最后求比值

注意

并查集要用判断深度和路径压缩
输入和输出要用scanf和printf
防止超时

AC代码

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,s,t,x1,y1,x2,y2,fa[5005],rank[5005];
double mmin=2147483647;
struct node//结构体
{
   
	int x,y,v;//x是其中一个点，y是另外一个点，v是两点之间的距离
}a[5005];
int find(int x)//找爸爸
{
   
	if(fa[x]==x)return x;//找爸爸
	else return fa[x]=find(fa[x]);//路径压缩
}
void bcj(int x,int y)//合并并查集
{
   
	int x1=find(x),y1=find(y);//找爸爸
	if(x1!=y1)//合并并查集
	{
   
		if(rank[x1]<rank[y1])fa[x1]=y1;//要弄深度的判断，不然会超时
		if(rank[x1]>rank[y1])fa[y1]=x1;
		if(rank[x1]==rank[y1])fa[x1]=y1,rank[y1]++;
	}
}
bool pd(int x,int y)//判断是否属于同一集合
{
   
	int x1=find(x),y1=find(y);//找爸爸
	if(x1!=y1)return true;//返回值
	else return false;
}
int gcd(int x,int y)//最大公因数
{
   
	while(x%y)
	{
   
		int z=x%y;
		x=y;
		y=z;
	}
	return y;
}
bool cmp(node x,node y)//结构体快排需要
{
   
	return x.v<y.v;
}
int main()
{
   
	scanf("%d%d",&n,&m);//记住要用scanf和printf，不然会超时
	for(int i=1;i<=m;i++)//输入
	 scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].v);
	scanf("%d%d",&s,&t); 
	sort(a+1,a+m+1,cmp);//结构体快排
	for(int i=1;i<=m;i++)//枚举每一个点
	{
   
		int ok=0;//判断是否有结果
		for(int j=1;j<=n;j++)//初值
		 fa[j]=j;
		bcj(a[i].x,a[i].y);//连接最短的那条边
		for(int j=i;j<=m;j++)//枚举它后面的边
		{
   
		 	if(pd(a[j].x,a[j].y))bcj(a[j].x,a[j].y);//如果不属于一个集合，就连通边
		 	if(!pd(s,t)){
   ok=j;break;}//如果目标的两个点相通，就退出
		}
		if(ok!=0&&double(a[ok].v)/a[i].v<mmin)//目标点相通，并且比值小
		{
   
			x1=a[i].v;//存储
			y1=a[ok].v;//存储
			mmin=double(a[ok].v)/a[i].v;//更改比值
		}
	}	
	if(mmin==2147483647)printf("%s","IMPOSSIBLE");//两个点无法相通
	else//两个点相通
	{
   
		x2=x1/gcd(x1,y1);//除以最大公因数
		y2=y1/gcd(x1,y1);
		if(x2==1||y2==1)printf("%d",y2/x2);//如果能整除就输出整除结果
		else printf("%d/%d",y2,x2);//否则输出最简分数形式
	}
}

谢谢