改一下吧,看着挺不舒服的(
不仅改了一下 LATEX,也略微改了一些疑似机翻的地方(?)
不知道名字问题要不要加 texttt
。
Bessie 和她的妹妹 Elsie 想从粮仓去她们最喜欢的田地,也就是能够使她们一起从粮仓离开,并且能同一时间到达的田地。
这个农场是由 N 块 (1≤N≤100) 编号为 1⋯N 的田地构成的,第一块田地就是粮仓,并且第 N 块田地是她们最喜欢的田地。
这个农场建在山的一边,所以,如果 X<Y 的话则满足第 X 块田地的高度要高于第 Y 块田地的高度。在这之中,有 M 条交错纵横的路径将不同的田地连接起来。
不过,显而易见的是,因为每条路都太陡了,所以这些小路只能沿着从高到低的方向走。例如,一条连接第 5 块田地和 8 块田地的小路只能沿着 5→8 的方向走,而不能沿着其他方向,因为那样会成为上坡路。每两块田地最多只能有一条路径相连接,所以一定有 M≤2N(N−1)。
有可能的是,Bessie 和 Elsie 两个人走同一条小路会耗费不同的时间;比如,通过同一条小路,Bessie 可能会耗费 10 个单位的时间,而 Elsie 会耗费 20 个单位的时间。
此外,Bessie 和 Elsie 只会在通过连接两块田地的小路时耗费时间——因为她们太匆忙了,在穿过田地时不会耗费任何时间,也从来不在任何地方停下来等待。
现在,请你判断出,能够满足使 Bessie 和 Elsie 同时出发并且同时到达她们喜欢的田地的最短的时间。
第一行输入 N 和 M,中间用空格分开。
接下来的 M 行,每行有四个整数 A,B,C,D,其中,A 和B(A<B) 代表着两块用这条小路连接的田地,C 代表 Bessie 通过这条小路的时间,而 D 代表 Elsie 通过这条小路的时间。C 和 D 均在 1⋯100 的范围之内。
一个整数,输出的是能够使两人同时出发并且同时到达目的地的最短时间,如果没有满足条件的答案,则输出 IMPOSSIBLE
。
Bessie 在每一条路都比 Elsie 快两倍。
如果 Bessie 经过 1→2→3 的路线,Elsie 经过 1→3 的路线,他们可以同时到达。
#### 题目描述:
$\texttt{Bessie}$ 和她的妹妹 $\texttt{Elsie}$ 想从粮仓去她们最喜欢的田地,也就是能够使她们一起从粮仓离开,并且能同一时间到达的田地。
这个农场是由 $N$ 块 $(1\leq N\leq 100)$ 编号为 $1\cdots N$ 的田地构成的,第一块田地就是粮仓,并且第 $N$ 块田地是她们最喜欢的田地。
这个农场建在山的一边,所以,如果 $X < Y$ 的话则满足第 $X$ 块田地的高度要高于第 $Y$ 块田地的高度。在这之中,有 $M$ 条交错纵横的路径将不同的田地连接起来。
不过,显而易见的是,因为每条路都太陡了,所以这些小路只能沿着从高到低的方向走。例如,一条连接第 $5$ 块田地和 $8$ 块田地的小路只能沿着 $5\to 8$ 的方向走,而不能沿着其他方向,因为那样会成为上坡路。每两块田地最多只能有一条路径相连接,所以一定有 $M \leq \dfrac{N(N-1)}{2}$。
有可能的是,$\texttt{Bessie}$ 和 $\texttt{Elsie}$ 两个人走同一条小路会耗费不同的时间;比如,通过同一条小路,$\texttt{Bessie}$ 可能会耗费 $10$ 个单位的时间,而 $\texttt{Elsie}$ 会耗费 $20$ 个单位的时间。
此外,$\texttt{Bessie}$ 和 $\texttt{Elsie}$ 只会在通过连接两块田地的小路时耗费时间——因为她们太匆忙了,在穿过田地时不会耗费任何时间,也从来不在任何地方停下来等待。
现在,请你判断出,能够满足使 $\texttt{Bessie}$ 和 $\texttt{Elsie}$ 同时出发并且同时到达她们喜欢的田地的最短的时间。
#### 输入格式:
第一行输入 $N$ 和 $M$,中间用空格分开。
接下来的 $M$ 行,每行有四个整数 $A,B,C,D$,其中,$A$ 和$B(A<B)$ 代表着两块用这条小路连接的田地,$C$ 代表 $\texttt{Bessie}$ 通过这条小路的时间,而 $D$ 代表 $\texttt{Elsie}$ 通过这条小路的时间。$C$ 和 $D$ 均在 $1\cdots100$ 的范围之内。
#### 输出格式:
一个整数,输出的是能够使两人同时出发并且同时到达目的地的最短时间,如果没有满足条件的答案,则输出 `IMPOSSIBLE`。
#### 说明与提示:
$\texttt{Bessie}$ 在每一条路都比 $\texttt{Elsie}$ 快两倍。
如果 $\texttt{Bessie}$ 经过 $1\to 2\to 3$ 的路线,$\texttt{Elsie}$ 经过 $1\to 3$ 的路线,他们可以同时到达。