HBC19963[HAOI2006]旅行COMF题解

一个忧伤的美男子算法基础篇 2023-11-16 10:05:01 89 0

题库丰富多样，涵盖各个领域，全网最全C++题库，让您在练习中不断成长！

给你一个无向图，N个顶点, M条边，每条边有一个权值Vi，给你两个顶点S和T ，求一条路径，使得路径上最大边和最小边的比值最小，如果S和T之间没有路径，输出”IMPOSSIBLE”，否则输出这个比值，如果需要，表示成一个既约分数，备注：两个顶点之间可能有多条路径。

给你一个无向图，N(N ≤ 500)个顶点, M(M ≤ 5000)条边，每条边有一个权值Vi(Vi < 30000)。给你两个顶点S和T ，求一条路径，使得路径上最大边和最小边的比值最小。如果S和T之间没有路径，输出”IMPOSSIBLE”，否则输出这个比值，如果需要，表示成一个既约分数。备注：两个顶点之间可能有多条路径。