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不可能相同。
1<N<=500,1<=x,y<=N，0<v<30000，0<M<=5000
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
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
IMPOSSIBLE
【样例输出2】
5/4
【样例输出3】
2
正解：并查集
解题报告：
考场上开始写了一个SPFA，然而是萎的，然后又yy了一下，感觉枚举答案中的两条边似乎可行，但是做不到O（1）判断可行性。
之后想出来一种更优秀的算法：我只需要枚举最大权值的边，然后比它权值小的边都可以用，知道S和T连通就更新一下答案，从大往小枚举。
具体见代码：
1 //It is made by jump~ 2 #include <iostream> 3 #include <cstdlib> 4 #include <cstring> 5 #include <cstdio> 6 #include <cmath> 7 #include <algorithm> 8 #include <ctime> 9 #include <vector> 10 #include <queue> 11 #include <map> 12 #include <set> 13 #ifdef WIN32 14 #define OT "%I64d" 15 #else 16 #define OT "%lld" 17 #endif 18 using namespace std; 19 typedef long long LL; 20 const int MAXN = 520; 21 const int MAXM = 10011; 22 int n,m,s,t,ecnt; 23 int father[MAXN]; 24 int ans1,ans2; 25 double ans; 26 struct edge{ 27 int u,v,z; 28 }e[MAXM]; 29 30 inline int getint() 31 { 32 int w=0,q=0; 33 char c=getchar(); 34 while((c<'0' || c>'9') && c!='-') c=getchar(); 35 if (c=='-') q=1, c=getchar(); 36 while (c>='0' && c<='9') w=w*10+c-'0', c=getchar(); 37 return q ? -w : w; 38 } 39 40 inline int find(int x){ 41 if(father[x]!=x) father[x]=find(father[x]); 42 return father[x]; 43 } 44 45 inline int gcd(int x,int y){ 46 if(y==0) return x; 47 return gcd(y,x%y); 48 } 49 50 inline bool cmp(edge q,edge qq){ return q.z<qq.z; } 51 52 inline void work(){ 53 n=getint(); m=getint(); 54 for(int i=1;i<=m;i++){ e[i].u=getint(); e[i].v=getint(); e[i].z=getint(); } 55 s=getint(); t=getint(); 56 sort(e+1,e+m+1,cmp); 57 int r1,r2; ans=(1<<30); 58 double now; 59 for(int i=1;i<=m;i++){ 60 for(int j=1;j<=n;j++) father[j]=j; 61 for(int j=i;j>=1;j--) { 62 r1=find(e[j].u); r2=find(e[j].v); 63 if(r1!=r2) father[r2]=r1; 64 r1=find(s); r2=find(t); 65 if(r1==r2) { 66 now=(double)e[i].z/(double)e[j].z; 67 if(now<ans) { ans=now; ans1=e[i].z; ans2=e[j].z; } 68 break; 69 } 70 } 71 } 72 if(ans==(1<<30)) { printf("IMPOSSIBLE"); return ; } 73 74 int gong=gcd(ans1,ans2); 75 if(ans1==ans2) printf("1"); 76 else if(gong==ans2) printf("%d",ans1/ans2); 77 else printf("%d/%d",ans1/gong,ans2/gong); 78 } 79 80 int main() 81 { 82 work(); 83 return 0; 84 }