关于此题LaTeX
查看原帖
关于此题LaTeX
380579
BMTXLRC楼主2021/6/12 19:55

改一下吧,看着挺不舒服的(

不仅改了一下 LaTeX\LaTeX,也略微改了一些疑似机翻的地方(?)

不知道名字问题要不要加 texttt

题目描述:

Bessie\texttt{Bessie} 和她的妹妹 Elsie\texttt{Elsie} 想从粮仓去她们最喜欢的田地,也就是能够使她们一起从粮仓离开,并且能同一时间到达的田地。

这个农场是由 NN(1N100)(1\leq N\leq 100) 编号为 1N1\cdots N 的田地构成的,第一块田地就是粮仓,并且第 NN 块田地是她们最喜欢的田地。

这个农场建在山的一边,所以,如果 X<YX < Y 的话则满足第 XX 块田地的高度要高于第 YY 块田地的高度。在这之中,有 MM 条交错纵横的路径将不同的田地连接起来。

不过,显而易见的是,因为每条路都太陡了,所以这些小路只能沿着从高到低的方向走。例如,一条连接第 55 块田地和 88 块田地的小路只能沿着 585\to 8 的方向走,而不能沿着其他方向,因为那样会成为上坡路。每两块田地最多只能有一条路径相连接,所以一定有 MN(N1)2M \leq \dfrac{N(N-1)}{2}

有可能的是,Bessie\texttt{Bessie}Elsie\texttt{Elsie} 两个人走同一条小路会耗费不同的时间;比如,通过同一条小路,Bessie\texttt{Bessie} 可能会耗费 1010 个单位的时间,而 Elsie\texttt{Elsie} 会耗费 2020 个单位的时间。

此外,Bessie\texttt{Bessie}Elsie\texttt{Elsie} 只会在通过连接两块田地的小路时耗费时间——因为她们太匆忙了,在穿过田地时不会耗费任何时间,也从来不在任何地方停下来等待。

现在,请你判断出,能够满足使 Bessie\texttt{Bessie}Elsie\texttt{Elsie} 同时出发并且同时到达她们喜欢的田地的最短的时间。

输入格式:

第一行输入 NNMM,中间用空格分开。

接下来的 MM 行,每行有四个整数 A,B,C,DA,B,C,D,其中,AAB(A<B)B(A<B) 代表着两块用这条小路连接的田地,CC 代表 Bessie\texttt{Bessie} 通过这条小路的时间,而 DD 代表 Elsie\texttt{Elsie} 通过这条小路的时间。CCDD 均在 11001\cdots100 的范围之内。

输出格式:

一个整数,输出的是能够使两人同时出发并且同时到达目的地的最短时间,如果没有满足条件的答案,则输出 IMPOSSIBLE

说明与提示:

Bessie\texttt{Bessie} 在每一条路都比 Elsie\texttt{Elsie} 快两倍。

如果 Bessie\texttt{Bessie} 经过 1231\to 2\to 3 的路线,Elsie\texttt{Elsie} 经过 131\to 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$ 的路线,他们可以同时到达。
2021/6/12 19:55
加载中...