名企笔试：楚楚街2016招聘笔试（航线）

（点击上方公众号，可快速关注）

题目描述

“呼！！终于到了，可是接下来要怎么走才能到达楚楚街港港呢？”亮亮在醋溜港直发愁。

 突然“啾”的一下，一只银色小船出现在亮亮的面前，上面坐着小精灵丹丹“又见面了，有什么可以帮助你的么？”

小精灵向亮亮眨了眨眼睛，微笑着说。 “我想去楚楚街港，但我不知道要怎么走，请问你可以告诉我么？”亮亮按捺着激动的心情轻声问道。

 “楚楚街港呀……那是个特别美好的地方”小精灵歪着头想了想，说“我只能告诉你大海上所有的航线，剩下的就只能靠你自己啦~” 

“只有所有的航线呀”，亮亮的内心再三挣扎，却又没有其他的办法。 “不管有多困难，我一定要达到楚楚街港，请你告诉我吧”亮亮坚定地对小精灵说。 

小精灵欣赏地点了点头，递给亮亮一张航线图，并叮嘱道“时限是1000天，一定要到哦~”，然后如来时一般“啾”的一声，消失了。 

亮亮现在迫切地想要抵达楚楚街港，请问亮亮最快能在第几天抵达楚楚街港呢？

输入描述:

一行包含两个整数 N(2<=N<=500)，M(1<=M<=2000)，用单个空格隔开。表示公有 N 个港，M 条航线。起点为 1，终点为 N。

接下来 M 行，每行包含五个整数P,Q(1<=P,Q<=n), K(1<=K<=1000)，X,Y(0<=X,Y<=10000)，代表 P、Q 两个港有航线并需要 K 天，并且该航线在第 X 天到第 Y 天天气恶劣不可通行。

输出描述:

一个整数，即亮亮最快能在第几天抵达楚楚街港

输入例子:

4 4

2 1 1 7 13

4 3 2 10 11

1 3 8 9 12

2 3 3 2 10

输出例子:

14

请通过评论说出你的解答。如果有必要，请介绍一下解题思路。在评论中分享解题思路可以让其他人了解你的想法。你的解答帮助了其他人，其他人的解答也将帮助到你。期待大家参与 ^_^

关注「算法爱好者」

看更多名企笔试题与解题讨论

↓↓↓