The first thing you should realize in the problem is that the cost between the various bus lines is always 1 , so you do not even have to use the Dijkstra algorithm or any other algorithm generic shortest path. A simple Search in Width is enough and faster.
The second important point is how to build your graph. From the problem statement you can see that a Campus is connected to the X other campuses by a bus line, which you can use indefinitely (as long as you do not leave the line) to walk between all campi connected by such a line. What this tells you is: All the vertices (the campuses) 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 sample input from the problem:
9 4
6 2 3 4 6 7 9
4 1 3 4 5
3 8 3 4
2 9 8
In the second line we have 2 3 4 6 7 9 (we can ignore the 6 here, since it is only used to inform how many vertices are present in the line). All of these vertices can reach any of the other vertices by paying only a price of 1 , so 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 get from one vertex to another ( this graph represents only the connections given by the first bus line of the example! ).
Summarizing : When reading the problem entry, construct your graph so that all Campi on one line have access to all other Campi on the same line. And run a Wide Search on the graph. This will give you the correct answer.
