題目描述

最近，Elaxia和w的關系特別好，他們很想整天在一起，但是大學的學習太緊張了，他們 必須合理地安排兩個人在一起的時間。Elaxia和w每天都要奔波于宿舍和實驗室之間，他們 希望在節約時間的前提下，一起走的時間盡可能的長。 現在已知的是Elaxia和w**所在的宿舍和實驗室的編號以及學校的地圖：地圖上有N個路 口，M條路，經過每條路都需要一定的時間。 具體地說，就是要求無向圖中，兩對點間最短路的最長公共路徑。 輸入輸出格式 輸入格式：

第一行：兩個整數N和M（含義如題目描述）。 第二行：四個整數x1、y1、x2、y2（1 ≤ x1 ≤ N，1 ≤ y1 ≤ N，1 ≤ x2 ≤ N，1 ≤ ≤ N），分別表示Elaxia的宿舍和實驗室及w**的宿舍和實驗室的標號（兩對點分別 x1,y1和x2,y2）。 接下來M行：每行三個整數，u、v、l（1 ≤ u ≤ N，1 ≤ v ≤ N，1 ≤ l ≤ 10000），表 u和v之間有一條路，經過這條路所需要的時間為l。

輸出格式：

一行，一個整數，表示每天兩人在一起的時間（即最長公共路徑的長度）

分析： 1.本題的難點在于有多條最短路，要求最長的公共最短路。 2.首先解決一條邊是否存在在最短路上的問題。 3.注意到當d[s][u]+w[u][v]+d[v][t]=d[s][t]時，邊(u,v)就會在s到t的最短路徑上，因此，我們不妨對4個點都進行一次最短路。 4.接下來解決最長公共最短路的問題。因為上一步我們已經選出了公共的最短路邊，實際上我們就可以把問題進行分解，找到選出的邊中路徑最長的一條，拓撲排序+BFS就可以解決了 5.錯誤提醒，注意邊數的大?。╩axn*maxn*2）

^_^