蘇世機(jī)試小課堂，考研機(jī)試不再慌！

I Wanna Go Home

題目描述

The country is facing a terrible civil war----cities in the country are divided into two parts supporting different leaders. As a merchant, Mr. M does not pay attention to politics but he actually knows the severe situation, and your task is to help him reach home as soon as possible."For the sake of safety,", said Mr.M, "your route should contain at most 1 road which connects two cities of different camp." Would you please tell Mr. M at least how long will it take to reach his sweet home?

輸入描述

The input contains multiple test cases.

The first line of each case is an integer N (2<=N<=600), representing the number of cities in the country.

The second line contains one integer M (0<=M<=10000), which is the number of roads.

The following M lines are the information of the roads. Each line contains three integers A, B and T, which means the road between city A and city B will cost time T. T is in the range of [1,500].

Next part contains N integers, which are either 1 or 2. The i-th integer shows the supporting leader of city i.

To simplify the problem, we assume that Mr. M starts from city 1 and his target is city 2. City 1 always supports leader 1 while city 2 is at the same side of leader 2.

Note that all roads are bidirectional and there is at most 1 road between two cities.

Input is ended with a case of N=0.

輸出描述

For each test case, output one integer representing the minimum time to reach home.

If it is impossible to reach home according to Mr. M's demands, output -1 instead.

輸入

2

1

1 2 100

1 2

3

3

1 2 100

1 3 40

2 3 50

1 2 1

5

5

3 1 200

5 3 150

2 5 160

4 3 170

4 2 170

1 2 2 2 1

0

輸出

100

90

540

答案

①讀題:

目標(biāo)是從城市1走到城市2，城市1和2周圍是有很多城市的，給你每個城市之間的距離，且這些城市隸屬兩個陣營，有1和2，走不同陣營的情況只可以出現(xiàn)一次（意思是如果你一開始走了1->2，那之后必須全部在2的陣營走。）求從城市1到城市2的最短距離。

②想出思路：

分別求出城市1和城市2到其陣營中其它城市的最短路徑，然后對陣營間存在的路徑i到j(luò)，求d(1,i)+d(i,j)+d(j,2)的最小值。

③動手編程：

④測試樣例：

⑤提交代碼：

進(jìn)入下面的鏈接提交代碼（或閱讀原文）

https://www.nowcoder.com/practice/0160bab3ce5d4ae0bb99dc605601e971?tpId=40&&tqId=21359&rp=1&ru=/ta/kaoyan&qru=/ta/kaoyan/question-ranking

⑥返回評測結(jié)果：

至此，這道題我們就已經(jīng)完成了。

本題總結(jié)

兩次dijkstra分別求出兩個陣營中的最短路，再遍歷找中間那一條跨陣營的邊，輸出總路徑最小值即可。

蘇世學(xué)社旗下品牌，專注于計(jì)算機(jī)考研

計(jì)算機(jī)考研一手資訊，原創(chuàng)高質(zhì)量干貨

深度的學(xué)習(xí)分享丨咨詢前輩丨個性化指導(dǎo)