The first thing you should notice in the problem is that the cost between the various bus lines is always 1
, then you don’t even need to use the dijkstra’s algorithm or any other generic shortest path algorithm. A simple Search in Width is enough and faster.
The second important point is how to build your graph. By the problem statement you can see that a Campus is connected to X other campuses by a bus line, which you can use indefinitely (as long as you don’t get off the line) to walk between all campuses connected by such a line. What that tells you is: all vertices (the campi) of a bus line have access to all other vertices, that is, they are connected in the graph, with edges of weight 1
.
Taking the example input of the problem:
9 4
6 2 3 4 6 7 9
4 1 3 4 5
3 8 3 4
2 9 8
On the second line we have 2 3 4 6 7 9
(we can ignore the 6
here, because it is only used to inform how many vertices are present in the line). All these vertices shown can reach any of the other vertices by paying only a price of 1
, then the representation of these connections in an adjacency matrix is as follows:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
--- --- --- --- --- --- --- --- ---
1 | | | | | | | | | |
2 | | | T | T | | T | T | | T |
3 | | T | | T | | T | T | | T |
4 | | T | T | | | T | T | | T |
5 | | | | | | | | | |
6 | | T | T | T | | | T | | T |
7 | | T | T | T | | T | | | T |
8 | | | | | | | | | |
9 | | T | T | T | | T | T | | |
where T
indicates that there is an edge connecting two vertices, and the absence of T
indicates that it is not possible to reach from one vertex to another (this graph represents only the connections given by the first bus line in the example!).
In short: When reading the input of the problem, build your graph so that all Campi of a line have access to all other Campi of the same line. And run a Width Search on the graph. This will give you the correct answer.