I Wanna Go Home

查看题解 查看答案
题目描述
Time Limit: 1000 ms
Memory Limit: 256 mb

请先登录再刷题,不会做的题目右上可以查看题解和答案~

输入输出格式
输入描述:
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
题目来源
北京大学机考题
重置

提交代码后在此处可查看状态