P3116 [USACO15JAN] Meeting Time S

题目描述

$\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。

输入输出样例 1

3 3 
1 3 1 2 
1 2 1 2 
2 3 1 2

2

说明/提示

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

如果 $\texttt{Bessie}$ 经过 $1\to 2\to 3$ 的路线，$\texttt{Elsie}$ 经过 $1\to 3$ 的路线，他们可以同时到达。