Emergency Exits

An emergency exit.
The university is set to undergo a comprehensive quality inspection next month. The set of requirements that will be checked are known in advance, and the university has been going through the list, making sure everything is in order.

Under the “Fire Safety” section there is a requirement concerning emergency exits that they are having a hard time assessing. It states that it must be possible to reach an emergency exit from any location within the university building in a reasonable time.

You have been asked to help with assessing the current state of these emergency exits. The university has provided you with a graph representation of the building, where each location in the building is represented as a vertex, and each pathway is represented as a weighted directed edge from one location to another. The weight of an edge represents the time in seconds required to travel along that pathway. Note that each pathway can only be traveled in one direction.

Given at which locations an emergency exit is present, determine the maximum time required to reach the closest emergency exit from any location in the building.


The input consists of:

  • One line with three integers $n$, $m$ and $k$ ($1 \le k \le n \le 2\cdot 10^5$, $0 \le m \le 2\cdot 10^5$), the number of locations, pathways and emergency exits.

  • One line with $k$ integers, the distinct locations of the emergency exits.

  • $m$ lines, the $i$th of which contains three integers $u_ i$, $v_ i$ and $s_ i$ ($1 \le u_ i,v_ i \le n$, $0 \le s_ i \le 10^6$, $u_ i \neq v_ i$), representing a unidirectional pathway from location $u_ i$ to location $v_ i$ that takes $s_ i$ seconds to travel along.

No two pathways have the same source and destination.


Output the minimum time, in seconds, required to reach the closest emergency exit from any location in the building. If it is not possible to reach an emergency exit from all locations in the building, output “danger”.

Sample Input 1 Sample Output 1
4 5 2
3 4
1 2 4
1 3 11
2 4 3
4 2 2
4 3 20
Sample Input 2 Sample Output 2
4 5 1
1 3 10
2 3 2
2 4 5
3 1 10
4 2 1
CPU Time limit 2 seconds
Memory limit 1024 MB
Arnar Bjarni Arnarson, Bjarki Ágúst Guðmundsson, and Unnar Freyr Erlendsson
Source Reykjavík University Spring Contest 2019
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in