苏世机试小课堂，考研机试不再慌！

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

答案

①读题:

目标是从城市1走到城市2，城市1和2周围是有很多城市的，给你每个城市之间的距离，且这些城市隶属两个阵营，有1和2，走不同阵营的情况只可以出现一次（意思是如果你一开始走了1->2，那之后必须全部在2的阵营走。）求从城市1到城市2的最短距离。

②想出思路：

分别求出城市1和城市2到其阵营中其它城市的最短路径，然后对阵营间存在的路径i到j，求d(1,i)+d(i,j)+d(j,2)的最小值。

③动手编程：

④测试样例：

⑤提交代码：

进入下面的链接提交代码（或阅读原文）

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

⑥返回评测结果：

至此，这道题我们就已经完成了。

本题总结

两次dijkstra分别求出两个阵营中的最短路，再遍历找中间那一条跨阵营的边，输出总路径最小值即可。

苏世学社旗下品牌，专注于计算机考研

计算机考研一手资讯，原创高质量干货

深度的学习分享丨咨询前辈丨个性化指导