1 /************************************************************** 2     Problem: 1050 3     User: rausen 4     Language: C++ 5     Result: Accepted 6     Time:7548 ms 7     Memory:1396 kb 8 ****************************************************************/ 9  10 #include <cstdlib>11 #include <cstdio>12 #include <cmath>13 #include <algorithm>14 #include <iostream>15 #include <utility>16  17 #define one first18 #define two second19 using namespace std;20  21 pair <int, pair<int, int> > a[10000];22 int m, n, s, t, f1, f2, fa[1000];23  24 int find(int x){25     int f = fa[x];26     if (f == x) return f;27     f = find(f);28     fa[x] = f;29     return f;30 }31  32 void add(int x, int y){33     int f1 = find(x), f2 = find(y);34     if (f1 != f2) fa[f1] = f2;35 }36  37 int main(){38     int x, y, v, anss = 0;39     double ans = 100000000;40     scanf("%d %d\n", &n, &m);41     for (int i = 1; i <= m; ++i){42         scanf("%d %d %d\n", &x, &y, &v);43         a[i].one = v;44         a[i].two.one = x;45         a[i].two.two = y;46     }47     scanf("%d %d\n", &s, &t);48     sort(a + 1, a + m + 1);49     for (int i = 1; i <= m; ++i){50         for (int j = 1; j <= n; ++j)51             fa[j] = j;52         for (int j = i; j <= m; ++j){53             add(a[j].two.one, a[j].two.two);54             f1 = find(s);55             f2 = find(t);56             if (f1 == f2)57                 if (ans > (double)a[j].one / a[i].one){58                     ans = (double)a[j].one / a[i].one;59                     anss = i;60                     x = a[j].one;61                     y = a[i].one;62                     break;63                 }64         }65     }66     if (anss == 0){67         cout<<"IMPOSSIBLE"<<endl;68         return 0;69     }70     for (int i = 2; i <= y; ++i)71         while (x % i == 0 && y % i == 0){72             x /= i;73             y /= i;74         }75     if (y == 1) printf("%d\n", x); else printf("%d%c%d\n", x, ‘/‘, y);76 }