P6825: 会议时间
传统题
1.000s
时间限制
256MB
内存限制
0 提交
0 解决
【题目描述】
【题目描述】
贝茜和她的妹妹埃尔西想从谷仓到他们的最喜欢的场地，以便
他们能在同一时间离开谷仓，并在同一时间到达他们最喜欢的地方。有N个农场，编号为1..N
，其中第1块田地包含谷仓，第N块田地是最喜欢的田地。农场建在山坡上，X田在山上如果X < Y，则高度比场地Y
高。然而，由于每条路都相当陡峭，它可以只跟着往下坡方向走。例如，路径在5 -> 8中，连接字段5和字段8方向不是相反，因为这是上坡。每一个对字段最多由一条路径连接，因此M <= N(N-1)/2。
贝茜和埃尔西可能要花不同的时间才能跟上路径;
例如，贝西可能需要10个单位的时间，而埃尔西可能需要20个单位的时间。而且，贝西和埃尔西只在小路上旅行时才花时间在田野之间——因为赶时间，他们总是旅行在零时间内穿过一个区域，从不等待任何地方。
请帮助确定贝西和埃尔西必须采取行动的最短时间，才能使他们
在完全相同的时间到达他们最喜欢的场地。
【输入格式】: (meeting.in)
第一个输入行包含N
和M，用空格分隔。
下面M
行的每一行都描述了一个由四个整数A、B、
C、D组成的路径 径
，其中A
和B (A < B)是由路径连接的字段， C是贝西走这条路所需要的时间，D是埃尔希走这条路所需的时间。C和D都在 1 . . 1000之间。
【
输出格式】(meeting.out)
一个整数，给出贝茜和埃尔希旅行到他们最喜欢的领域，并在同一时刻到达。如果这是不可能的，或者贝西和埃尔西没有办法到达
最喜欢的字段，输出单词IMPOSSIBLE
。
【
样例输入】:
3 3
1 3 1 2
1 2 1 2
2 3 1 2
【
样例输出】:
2
【样例说明】
贝西走每条路的速度都是埃尔西的两倍，但如果贝西走那条路
路径1->2->3
和Elsie走路径1->3，他们将到达 同样的时间。