题目描述 Description

Z小镇是一个景色宜人的地方，吸引来自各地的观光客来此旅游观光。 Z小镇附近共有 N(1

输入描述 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 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

数据范围及提示 Data Size & Hint

N(1

分析

并查集随便写 其实有点像最小生成树 /233

代码

#include <bits/stdc++.h> #define Max 10005 #define INF 1e7 using namespace std; char word; int N, M; int father [Max], Count; int Answer_Max = INF, Answer_Min, Maxn, Minn; struct node { int from; int to; int dis; }Edge [Max]; inline void AddEdge(int from, int to, int dis) { Count++; Edge [Count].from = from; Edge [Count].to = to; Edge [Count].dis = dis; } bool comp (const node a, const node b) { return a.dis < b.dis; } int find (int x) { if (father [x] == x) return x; else return father [x] = find (father [x]); } inline void read (int &now) { now = 0; word = getchar (); while (word < '0' || word > '9') word = getchar (); while (word >= '0' && word <= '9') { now = now * 10 + (int)(word - '0'); word = getchar (); } } int Gcd (int x, int y) { return y == 0 ? x : Gcd (y, x % y); } int main() { read (N); read (M); int x, y, v; for (int i = 1; i <= M; i++) { read (x); read (y); read (v); AddEdge (x, y, v); } sort (Edge + 1, Edge + 1 + M, comp); int start, end; read (start); read (end); for (int k = 1; k <= M; k++) { for (int i = 1; i <= N; i++) father [i] = i; Minn = Edge [k].dis; Maxn = Edge [k].dis; for (int i = k; i <= M; i++) { int x = find (Edge [i].from); int y = find (Edge [i].to); if (x != y) { father [x] = y; Maxn = max (Maxn, Edge [i].dis ); } if (find (start) == find (end)) break; } if (find (start) == find (end)) if (double (Maxn) / double (Minn) < double (Answer_Max) / double (Answer_Min)) { Answer_Max = Maxn; Answer_Min = Minn; } } if (Answer_Min == 0) cout << "IMPOSSIBLE"; else { int now = Gcd (Answer_Max, Answer_Min); Answer_Max /= now; Answer_Min /= now; if (Answer_Min == 1) cout << Answer_Max << endl; else cout << Answer_Max << "/" << Answer_Min << endl; } }