题目描述 Description
Z小镇是一个景色宜人的地方,吸引来自各地的观光客来此旅游观光。
Z小镇附近共有N(1<N≤500)个景点(编号为1,2,3,…,N),这些景点被M(0<M≤5000)条道路连接着,所有道路都是双向的,两个景点之间可能有多条道路。也许是为了保护该地的旅游资源,Z小镇有个奇怪的规定,就是对于一条给定的公路Ri,任何在该公路上行驶的车辆速度必须为Vi。频繁的改变速度使得游客们很不舒服,因此大家从一个景点前往另一个景点的时候,都希望选择行使过程中最大速度和最小速度的比尽可能小的路线,也就是所谓最舒适的路线。 输入描述 Input Description
第一行包含两个正整数,N和M。
接下来的M行每行包含三个正整数:x,y和v(1≤x,y≤N,0 最后一行包含两个正整数s,t,表示想知道从景点s到景点t最大最小速度比最小的路径。s和t不可能相同。 输出描述 Output Description
如果景点s到景点t没有路径,输出“IMPOSSIBLE”。否则输出一个数,表示最小的速度比。如果需要,输出一个既约分数。
样例输入 Sample Input
样例1
4 21 2 13 4 21 4样例23 31 2 101 2 52 3 81 3样例33 21 2 22 3 41 3 样例输出 Sample Output
样例1
IMPOSSIBLE样例25/4样例32 数据范围及提示 Data Size & Hint
N(1<N≤500)
M(0<M≤5000)
Vi在int范围内
/* 貌似是最优比率生成树,但不会怎么做,问了问同学,是用并查集做的,很神奇。 把边按边长从小到大排序,枚举i作为生成树的最长边,然后从i到1添边,直到s和t相连,每次对最长边与最短边的比值取小即为答案。至于正确性是显然的,因为它尽量使生成树由边长相近的边组成,然后取小。 */#include#include #include #define M 510#define INF 100000000using namespace std;int fa[M],n,m,s,t;struct node{ int x,y,z;};node e[M*10];bool cmp(const node&a,const node&b){ return a.z