BZPRO

#3890. [Usaco2015 Jan]Meeting Time

内存限制：128 MiB 时间限制：10 Sec
提交 提交记录 讨论

题目描述

Bessie和她的妹妹Elsie想要从谷仓旅行到他们最喜欢的地区去。她们会在同一时间离开谷仓，也希望要在同一时
间到达她们的目的地地区。农场由N个地区组成，分别编号为1..N (1 <= N <= 100)，谷仓位于1号区域，而她们的
目的地是N号区域。由于农场是依山而建的，两个区域之间会有高度差，编号小的地区海拔高于编号大的地区的海
拔，即1号地区海拔最高，N号地区海拔最低。会有M条小路两两连接不同地区。因为山路过于陡峭，路只允许以下
坡的方式行走。比如就一条路连接了5号区域和8号区域，那么只允许从5号区域前往8号区域而不允许反向行走。每
两个地区之间至多只有一条路，所以M <= N(N-1)/2。Bessie和Elsie走路所花费的时间是不一样的。比如，走同一
条路，Bessie会需要10个单位时间，而Elsie会要20个。请注意，因为她们在赶时间，所以只会在路上花费时间，
进入或者离开一个区域不需要花费时间，而且她们也不会停下来等对方。请帮忙计算出Bessie和Elsie最短需要多
少时间才能同时出发且同时到达她们的目的地。

输入格式

第一行包含两个以空格分隔的整数，分别为N和M。
接下来M行描述连接区域之间的路的情况
每一行给出四个以空格分隔的整数A B C D，表示A区域和B区域之间有一条路，
Bessie需要C个单位时间来走完这条路，而Elsie需要D个单位时间来走。
C和D都在区间1..100内。

输出格式

输出一个整数。即Bessie和Elsie同时出发且同时达到N号区域所需要的最少时间。
如果无法到达N号区域或者不可能同时到达，请输出单词 "IMPOSSIBLE"（引号不用输出）。

样例

样例输入


			
3 3

1 3 1 2

1 2 1 2

2 3 1 2

样例输出


			
2

SOLUTION NOTES:

Bessie is twice as fast as Elsie on each path, but if Bessie takes the

path 1->2->3 and Elsie takes the path 1->3 they will arrive at the

same time.

数据范围与提示

BZPRO Powered by Remmina.
Github Repository