Taco's Shortest Path Challenge

You are given a network of N rooms connected by M bidirectional paths. Each path has an associated time cost. Starting from a given room S, your task is to determine the shortest time required to reach each of a given list of key rooms. If a key room is unreachable from the starting room, output -1 for that room.

The problem requires you to implement Dijkstra's algorithm for finding the shortest path in a weighted graph. The time taken along a path is denoted by an edge weight. Formally, if you have a graph \(G=(V, E)\) with vertices \(V\) and weighted edges \(E\), and if \(d(u,v)\) represents the minimum time to travel from \(u\) to \(v)\), then for each key room \(k\) you must compute:

\[ d(k) = \begin{cases} \min_{\text{paths } P \text{ from } S \text{ to } k}\; \sum_{(u,v) \in P} T(u,v) & \text{if such a path exists}, \\ -1 & \text{otherwise.} \end{cases} \]

inputFormat

The input is read from stdin and is formatted as follows:

N M S
A1 B1 T1
A2 B2 T2
...
AM BM TM
K
key1 key2 ... keyK

Here,

• N: Number of rooms (vertices).
• M: Number of paths (edges).
• S: The starting room.
• Each of the next M lines contains three integers, A, B and T, indicating there is an undirected path between room A and room B with time cost T.
• K: The number of key rooms.
• The last line contains K space-separated integers representing the key rooms.

outputFormat

The output should be written to stdout as a single line containing K space-separated integers. Each integer represents the shortest time required to reach the corresponding key room from room S. If a key room is unreachable, output -1 for that room.

6 7 1
1 2 4
1 3 2
2 4 7
2 5 1
3 5 3
4 6 2
5 6 5
4
3 4 5 6

2 11 5 10