【问题描述】 小白和老白想从谷仓走到他们最喜爱的牧场。他们在同一时间离开谷仓,也在同一时间 到达最喜爱的牧场。整个农场是一个有 N 个牧场,1 号牧场就是谷仓,N 号牧场是他们最喜 爱的牧场。整个农场是建在一个山坡上的,如果 X<Y,则代表 x 号牧场比 Y 牧场要高。有 M 条路径连接一堆牧场。然而,由于每条路径都很陡,每条路只能向下山的方向走。比如,一 4 条连接 5 号和 8 号农场的路只能从 5 走到 8 而不能反过来,因为那样就是向山上走了。每对 牧场之间最多有一条路径,故 M≤N(N-1)/2。 小白和老白可能需要不同的时间来走过一条路径。例如,小白可能花 l0 个单位的时间, 而老白会花 20 个单位(因为他老了),而且他们只在路径上花时间,在牧场上是不花时间 的。 请帮助决定小白和老白至少要花多少时间,使他们能同时到达他们最喜爱的农场。 【输入格式】 第 1 行是 N 和 M,用一个空格分开。 接下来的 M 行,每行有 4 个整数 A、B、C、D,表示 A 牧场和 B 牧场是被连接的,C 是小 白经过这条路要花的时间,D 是老白经过这条路要花的时间。C 和 D 的范围是 1~1000。 【输出格式】 一行一个整数,表示小白和老白至少要花多少时间使他们能同时到达他们最喜爱的农场。 如果这是不可能的,或者根本就没有路径使他们能到达她们最喜爱的农场,在一行输出 “IMPOSSIBLE”。
求代码,代码,代码