[codevs1001]舒适的路线

[codevs1001]舒适的路线

试题描述

Z小镇是一个景色宜人的地方,吸引来自各地的观光客来此旅游观光。
Z小镇附近共有
N(1<N≤500)个景点(编号为1,2,3,…,N),这些景点被M(0<M≤5000)条道路连接着,所有道路都是双向的,两个景点之间可能有多条道路。也许是为了保护该地的旅游资源,Z小镇有个奇怪的规定,就是对于一条给定的公路Ri,任何在该公路上行驶的车辆速度必须为Vi。频繁的改变速度使得游客们很不舒服,因此大家从一个景点前往另一个景点的时候,都希望选择行使过程中最大速度和最小速度的比尽可能小的路线,也就是所谓最舒适的路线。

输入

第一行包含两个正整数,N和M。
接下来的M行每行包含三个正整数:x,y和v(1≤x,y≤N,0 最后一行包含两个正整数s,t,表示想知道从景点s到景点t最大最小速度比最小的路径。s和t不可能相同。

输出

如果景点s到景点t没有路径,输出“IMPOSSIBLE”。否则输出一个数,表示最小的速度比。如果需要,输出一个既约分数。

输入示例


输出示例

/

数据规模及约定

N(1<N≤500)

M(0<M≤5000)

Vi在int范围内

题解

把 m 条边按照 V 值从小到大排序,然后 O(n2) 扫一遍用并查集维护一下 s, t 间的连通性。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std; int read() {
int x = 0, f = 1; char c = getchar();
while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
return x * f;
} #define maxn 510
#define maxm 5010
#define LL long long
int n, m, s, t;
struct Edge {
int u, v, d;
Edge() {}
Edge(int _1, int _2, int _3): u(_1), v(_2), d(_3) {}
bool operator < (const Edge& t) const { return d < t.d; }
} es[maxm]; LL gcd(LL a, LL b) { return !b ? a : gcd(b, a % b); }
struct Fra {
LL a, b;
Fra() {}
Fra(LL _, LL __): a(_), b(__) {}
void maintain() {
if(a < 0) return ;
LL d = gcd(a, b);
a /= d; b /= d;
return ;
}
bool operator < (const Fra& t) const { return a * t.b < b * t.a; }
} ; int fa[maxn];
int findset(int x) { return x == fa[x] ? x : fa[x] = findset(fa[x]); } int main() {
n = read(); m = read();
for(int i = 1; i <= m; i++) {
int a = read(), b = read(), c = read();
es[i] = Edge(a, b, c);
}
s = read(); t = read(); Fra ans(-1, -1);
sort(es + 1, es + m + 1);
for(int i = 1; i <= m; i++) {
for(int j = 1; j <= n; j++) fa[j] = j;
for(int j = i; j <= m; j++) {
Edge& e = es[j];
int u = findset(e.u), v = findset(e.v);
if(u != v) fa[v] = u;
if(findset(s) == findset(t)) {
if(ans.a < 0) ans = Fra(e.d, es[i].d);
ans = min(ans, Fra(e.d, es[i].d));
break;
}
}
} if(ans.a < 0) return puts("IMPOSSIBLE"), 0;
ans.maintain();
if(ans.b != 1) printf("%lld/%lld\n", ans.a, ans.b);
else printf("%lld\n", ans.a); return 0;
}
上一篇:JDBC——事物管理


下一篇:CODEVS1001 舒适的路线 (并查集)