Catch The Bus

The National University of Singapore is built on a hill, so even if the distance from A to B seems short from the map, walking over the steep ladder is very exhausting. Fortunately, there's a shuttle bus service.

Suppose that NUS has \(N\) buildings and \(E\) bidirectional roads. A shuttle bus starts moving from building X to building Y (the detailed path will be given). At the same time, Chris starts walking from building A and wants to go to building B. Chris is as fast as the shuttle bus, but walking \(k\) meters requires \(k\) amount of energy (in Joules) while no energy is spent if he travels by a shuttle bus. What is the minimum amount of energy will Chris need to arrive at his destination?

Input File

Details and Assumptions

  • Chris walks as fast as the shuttle bus.
  • Chris can choose to wait at a building to hop onto a bus; no energy is spent in this process.
  • Chris can choose to drop by at any building the bus went through.
  • Chris can choose not to hop onto the bus.
  • The bus will not travel a building more than once.
  • Moving to any buildings is possible.

Input Format

The first line consists of two integers \(N\), \(E\) - the number of buildings and the number of bidirectional roads.
The next \(E\) lines each contains 3 integers \(u, v, t\) describing a bidirectional road connecting building \(u\) and \(v\) of length \(t\).
The next line contains an integer \(M\), the number of buildings the shuttle bus go through.
The next line contains \(M\) integers, describing the path of the shuttle bus in that order.
The last line contains two integers \(A\) and \(B\), the starting building and the destination respectively.

  • \(N\) and \(E\) is as large as 82500 and 110000 respectively.
  • The length of the road does not exceed 100.
  • \(M\) is as large as 1000.

Sample Input

5 5
0 1 1
1 2 1
2 3 1
4 0 1
0 3 100
4 0 3
1 3

Sample Output


Inspired by the number of ladders I need to climb to reach School of Computing, National University of Singapore.

Problem Loading...

Note Loading...

Set Loading...