MZ自测——遥远的村庄（并查集）
3、遥远的村庄
village.c/cpp/pas
1s/64M
【问题描述】
XX住在一个遥远的村庄里，这个村庄有N户居民（编号为1,2,3…N），他们之间由M条道路连接起来，道路可以双向通行。第i条道路的距离记为Wi。
一天XX需要第s户居民家去到第t户居民家，他想，既然反正都要去，那为什么不顺便干点有意思的事呢，于是他决定找出一条完美路线。在所有可从s到达t的路线中，如果该路线上最大距离路段和最小距离路段比最小，那么XX则认为这就是完美路线。
【输入数据】
输入文件名：village.in
输入第一行为n,m两个数，表示村庄里的有n户居民，他们之间有m条路。
接下来m行每行3个数a,b,c，分别表示从a到b的距离为c。
最后一行是两个数s,t，表示YCX要从s去t。
【输出数据】
输出文件名：village.out
一行，一个数表示完美路线上最大距离路段和最小距离路段比，注意，该比值如果不是整数请用最简分数表示。如果不能到达，则直接输出”Impossible”（引号内字符，首字母大写，其余小写）。
【输入样例】
样例1
4 2
1 21
3 42
1 4
样例2
3 3
1 210
1 25
2 38
1 3
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！