本题关联比赛
山东省选（随意做）

关于 Elaxia的路线的近10条评论(全部评论)
边数 50W 垃圾出题人，不给边的范围 Sky_miner 2016-10-10 07:34 6楼
LOSER 2016-10-02 17:44 5楼
回复 @L_in : 为啥不用记忆化搜索 AntiLeaf 2016-08-04 06:25 4楼
先宽搜，再深搜里套深搜，果断T了7个少memset N遍可以多过一个终于先建无向图并bfs4次，再建最短路上的公共边的有向图，再dfs一遍，然后居然没超时！！感觉自己都快写废了。。 _Itachi 2016-08-03 19:47 3楼
编号搞不对所以W了一堆= = AntiLeaf 2016-08-03 14:01 2楼
我去。。输入输出文件到底是啥啊 travel!.in or out 不对 traval!.in or out 也不对。。疯了。 belong.zmx 2011-10-02 14:18 1楼

423. Elaxia的路线

★★☆ 输入文件：travel!.in 输出文件：travel!.out 简单对比
时间限制：1 s 内存限制：256 MiB

最近，Elaxia和w**的关系特别好，他们很想整天在一起，但是大学的学习太紧张了，他们必须合理地安排两个人在一起的时间。Elaxia和w**每天都要奔波于宿舍和实验室之间，他们希望在节约时间的前提下，一起走的时间尽可能的长。

现在已知的是Elaxia和w**所在的宿舍和实验室的编号以及学校的地图：地图上有N个路口，M条路，经过每条路都需要一定的时间。

具体地说，就是要求无向图中，两对点间最短路的最长公共路径。

第一行：两个整数$N$和$M$（含义如题目描述）。

第二行：四个整数$x1、y1、x2、y2（1 ≤ x1 ≤ N，1 ≤ y1 ≤ N，1 ≤ x2 ≤ N，1 ≤y2 ≤ N）$，分别表示Elaxia的宿舍和实验室及w**的宿舍和实验室的标号（两对点分别为$x1, y1$和$x2, y2$）。

接下来$M$行：每行三个整数，$u、v、l（1 ≤ u ≤ N，1 ≤ v ≤ N，1 ≤ l ≤ 10000）$，表示$u$和$v$之间有一条路，经过这条路所需要的时间为$l$。

一行，一个整数，表示每天两人在一起的时间（即最长公共路径的长度）。

对于30%的数据，$N ≤ 100$；

对于60%的数据，$N ≤ 1000$；

对于100%的数据，$N ≤ 1500$，输入数据保证没有重边和自环。