10845 - The crusades

十字軍東征

教皇任命殘酷的神聖羅馬帝國皇帝"Frederick Barbarossa"，俗稱紅鬍子(Red Beard)，與英勇的英國君王獅子心查理(King Richard the Lionheart)收復被回教徒佔領的聖地耶路撒冷(Jerusalem)。

兩位君主清楚地知道他們的軍隊不能在出征的路上相遇，否則必定爭鬥不休，因此，他們希望各自選擇不同的行軍路徑抵達耶路撒冷，這表示同一條道路不會同時被兩邊的軍隊選為行軍的路徑。然而，兩邊的人馬可以在城鎮相遇，因為在城鎮上他們懶得理會彼此。

另外還有一個困難，有些狹窄的道路只能容許一定數量的士兵經過，為了解決這個問題，在必要時君主們會把他們的軍隊拆成多個部隊以保證有最多的士兵到達耶路撒冷與回教徒對抗(不論士兵們所屬的國家為何)

給定一張城鎮間由道路兩兩相連的地圖，地圖上會指示每條道路最多可容許士兵通過的數量，並顯示兩國軍隊的起始位置(一定在不同地點)。你的任務是要決定最大抵達耶路撒冷的士兵總數。

Input
第一列有一整數t，用來表示有幾組測試案例(1 ≤ t ≤ 60)。每組測試案例包含整數 N 與 M (5 ≤ N ≤ 12 , 5 ≤ M ≤ 30)，表示地圖上有N個城鎮與M條道路，城鎮從1開始編號到N。接著會有M列，每一列有三個整數A, B, C (1 ≤ A,B ≤ N , 1 ≤ C ≤ 100)，表示A城與B城之間有一條雙向的道路，其最大可通過士兵數為C。最後一列有三個整數F, R, J (1 ≤ F, R, J ≤ N)，表示Frederick的軍隊，Richard的軍隊及耶路撒冷的啟始位置，此三個位置一定不會相同。

Output
每組測試資料的輸出皆以一列來表示能抵達耶路撒冷的最大士兵數。

Sample Input

2
6 6
1 3 10
2 3 5
3 4 11
3 5 11
4 6 11
5 6 2
1 2 6
5 6
1 5 9
1 3 10
3 2 10
3 4 9
3 5 10
5 4 100
1 2 4

Sample Output

12
28

本題難度極高，任何人都不應該嘗試解這道題目，不論你是否是一位夠資格瞧不起別人的業餘程式設計人員，或是夠資格瞧不起業餘程式設計人員的職業程式設計師，或是夠資格瞧不起一般職業程式設計師的資深程式設計專家，不論你是誰都不應該挑戰這道高難度的題目，因為挑戰失敗後只會讓你的信心崩塌並多瞧不起一個人，那就是你自已！ 我也是挑戰失敗的人，不過這題讓我獲得巨大的成就感，因為一直以來都沒資格瞧不起任何人的我，終於有一個讓我瞧不起的對像，那就是我自已，這也是為什麼我要翻譯本題的原因。

原文出處