Subway
InterviewTime limit1sMemory limit256 MB
Each station belongs to company A or B; find the route from station 0 to M that minimizes transfers first, then travel time, and report both.
- Level
Medium6 of 10
- Topics
- Graph, Shortest path, Dynamic programming
- Solved
- No attempts yet
Problem
Hyeonguk, a graduate student, usually takes the subway to work at his lab. The subway is run by two companies, A and B. The two companies are rivals, and they hate it when people use the other company's subway. So both A and B charge a high fare every time a passenger transfers to the other company's subway.
Hyeonguk is a poor graduate student, so saving money matters most to him. Let us find the optimal commute route for Hyeonguk. An optimal commute route is the route with the shortest travel time among the routes that minimize the number of transfers. Here, a transfer is counted once each time the company operating the subway station changes along the way.
In the figure above, circles represent subway stations and lines show whether stations are connected. A white station is run by company A, and a black station is run by company B. In this case, taking the route marked in red uses 2 transfers, the fewest possible, and has the shortest travel time.
Input
The first line gives the number of subway stations N and the destination number M, separated by a space. Stations are numbered 0 to N-1 in order, and the starting point is always 0. (2 ≤ N ≤ 1000, 0 < M < 1000)
The next N lines give the company information Ci (0 ≤ i < N) for each subway station as 0 or 1. 0 means company A, and 1 means company B.
The next N lines give the connection state Eij (0 ≤ Eij ≤ 1000) between subway stations as integers. If Eij is 0, station i and station j are not connected. If Eij is greater than 0, the two stations are connected and the travel time is Eij.
Output
Print the number of transfers and the total travel time when using the optimal route, separated by a space.
The starting point and the destination are guaranteed to be connected.