Fişierul intrare/ieşire:marathon.in, marathon.outSursăIIOT 2021-22 Runda 4
AutorAlessandro BortolinAdăugată destefdascalescuStefan Dascalescu stefdascalescu
Timp execuţie pe test2.5 secLimită de memorie524288 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Marathon

After weeks of training, William finally found out how to win a marathon: by cheating! He teamed up with a skillful driver, his friend Alessandro, and is planning on driving instead of running.

The marathon takes place in the beautiful city of Pordenone, which is formed by N intersections and M bidirectional roads. Each road is exactly w[i] meters long.

The marathon starts at intersection 0 and ends at intersection N-1. Marathoners must go through K checkpoints given in the array S, however, they can run through any route between two consecutive checkpoints.

William's plan is the following:

He will run from the starting line to the first checkpoints, then he will sneak into Alessandro's car and reach the second checkpoint, next, he will run another piece to the following checkpoint. After that, he will sneak again into Alessandro's car and reach the following checkpoint and so on until he reach the finishing line.

Since William wants to win the marathon, he will always take the shortest path between two checkpoints. However, while trying to hide the evidence of the cheat, William lost the original arrangement of the checkpoints!

In order to plan for the worst case scenario, William is interested in the maximum distance he will have to run among all the possible checkpoint arrangements. Can you help him?

Date de intrare

The first line of the input file marathon.in contains the integers N and M. The second line contains the integer K, followed by K integers S_i, K even.

Each of the following M lines contains 3 integers u, v and w describing a road of length w connecting intersections u and v.

Date de ieşire

You will need to write in the output file marathon.out a single integer: the maximum distance that William will have to run among all the possible checkpoint arrangements.

Restricţii

  • 1 ≤ N ≤ 500
  • 1 ≤ M ≤ N * (N-1) / 2
  • 0 ≤ K ≤ N-2, K even.
  • 0 ≤ u, v ≤ N-1
  • 0 ≤ w ≤ 10^9
  • For tests worth 25 points, K = 0.
  • For tests worth 35 more points, 0 ≤ K ≤ 18

Exemplu

marathon.inmarathon.out
7 8
2 4 3
0 1 5
0 2 3
1 4 1
2 3 4
1 3 13
4 5 6
1 6 10
5 6 2
27
marathon.inmarathon.out
4 5
0
0 1 4
0 2 2
1 2 0
1 3 6
2 3 9
8

Explicaţie

In the first sample case, the maximum distance is obtained from the arrangement [4, 3]:

First, William will run from 0 to 4, the shortest path is 0 -> 1 -> 4 with length 5 + 1 = 6;

Then Alessandro will take William to 3. Finally William will run from 3 to 6, the shortest path is 3 -> 2 -> 0 -> 1 -> 4 -> 5 -> 6 with length 4 + 3 + 5 + 1 + 6 + 2 = 21.

The total distance is 6 + 21 = 27.

In the second sample case there are no checkpoints, so William must run directly from 0 to 3. The shortest path is 0 -> 2 -> 1 -> 3.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?