Description
给你一个无向图，N(N<=500)个顶点, M(M<=5000)条边，每条边有一个权值Vi(Vi<30000)。给你两个顶点S和T，求一条路径，使得路径上最大边和最小边的比值最小。如果S和T之间没有路径，输出”IMPOSSIBLE”，否则输出这个比值，如果需要，表示成一个既约分数。 备注： 两个顶点之间可能有多条路径。
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
【样例输入2】
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
给你一个无向图，N(N<=500)个顶点, M(M<=5000)条边，每条边有一个权值Vi(Vi<30000)。给你两个顶点S和T，求一条路径，使得路径上最大边和最小边的比值最小。如果S和T之间没有路径，输出”IMPOSSIBLE”，否则输出这个比值，如果需要，表示成一个既约分数。 备注： 两个顶点之间可能有多条路径。
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
【样例输入2】
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
解析
本来一看还以为是最短路，但是最短路会使某些情况不能实现..
那么我们就要用一种特殊的方法..
我们先将全部边从小到大排序，然后我们就枚举最小的边是哪条，通过最小生成树取到最大的边，那么最小的比值就一目明了了。。
/**************************************************************Problem: 1050User: chenyushuo2012Language: C++Result: AcceptedTime:8060 msMemory:936 kb
****************************************************************/#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
int fa[510];
int ffa ( int x ){if ( fa[x] == x ) return x;return fa[x] = ffa (fa[x]);
}
struct node {int x, y, d;
}a[11000]; int n, m;
bool cmp ( node x, node y ){return x.d < y.d;
}
int st, ed;
int ans_x, ans_y;
int gcd ( int x, int y ){if ( x == 0 ) return y;return gcd ( y%x, x );
}
int main (){int i, j, k;scanf ( "%d%d", &n, &m );for ( i = 1; i <= m; i ++ ){scanf ( "%d%d%d", &a[i].x, &a[i].y, &a[i].d );}sort ( a+1, a+m+1, cmp );scanf ( "%d%d", &st, &ed );ans_x = 9999999; ans_y = 1;for ( i = 1; i <= m; i ++ ){for ( j = 1; j <= n; j ++ ) fa[j] = j;for ( j = i; j <= m; j ++ ){int xx = a[j].x, yy = a[j].y;fa[ffa(xx)] = ffa(yy);if ( ffa (st) == ffa (ed) ){if ( a[j].d * ans_y < a[i].d * ans_x ){ans_y = a[i].d;ans_x = a[j].d;k = gcd ( ans_x, ans_y );ans_x /= k;ans_y /= k;break;}}}}if ( ans_y == 1 ){if ( ans_x == 9999999 ) printf ( "IMPOSSIBLE\n" );else printf ( "%d\n", ans_x );}else printf ( "%d/%d\n", ans_x, ans_y );return 0;
}