Задача №114309. Убежище
В полутемной комнате Милан сел за стол и начал думать о возможных последствиях ядерной катастрофы в своем городе. Поскольку Милан - мэр города, он очень хорошо знаком с такими событиями.
А именно, он знает, что в его городе живет ровно \(N\) человек и каждый житель живет в своем собственном доме. Между \(M\) парами домов есть дороги, и для каждой дороги известно, сколько времени потребуется для ее прохождения. Наконец, Милан знает, в каких \(K\) домах есть атомные укрытия и сколько людей помещается в каждое укрытие. Учитывая все это, у Милана возникает следующий вопрос: «Сколько времени нужно, чтобы эвакуировать всех жителей города?»
Помогите Милану ответить на этот вопрос.
Конечно, эвакуация означает, что каждый житель попадает в какое-то атомное убежище. Можно предположить, что жители двигаются оптимально (по кратчайшему пути) и что несколько человек могут двигаться по одной дороге одновременно, возможно в разных направлениях. Также можно считать, что между любыми двумя домами есть хотя бы один путь, проходящий по дорогам.
Первая строка содержит натуральные числа N \((1 \le N \le 100000)\), \(M\) \((1 \le M \le 300000)\) и \(K\) \((1 \le K \le 17)\), которые обозначают количество жителей, количество дорог и количество атомных укрытий. Дома пронумерованы числами от \(1\) до \(N\).
В каждой из следующих \(M\) строк даны три натуральных числа \(A\), \(B\) \((1 \le A, B \le N, A \neq B)\) и \(C\) \((1 \le C \le 10^9)\), которые обозначают, что между домами с номерами \(A\) и \(B\) есть дорога, для прохождения которой требуется \(C\) единиц времени.
В каждой из следующих \(K\) строк даны два натуральных числа \(X\) \((1 \le X \le N)\) и \(Y\) \((1 \le Y \le 10^9)\), которые обозначают, что в доме с номером \(X\) есть атомное убежище, где может быть укрыто максимум \(Y\) людей.
Общая вместимость всех укрытий больше или равна \(N\).
В единственной строке выведите минимальное время, необходимое для эвакуации всех жителей города.
В задаче 3 подгруппы:
- (30 баллов) Ограничения: \(N \le 100, M \le 500, K \le 5\)
- (30 баллов) Ограничения: \(K \le 10\)
- (40 баллов) Без дополнительных ограничений.
5 5 2 1 2 1 1 3 3 2 3 4 3 4 1 4 5 1 1 10 4 2
3
7 8 3 1 2 5 2 3 3 3 4 5 1 4 1 4 5 7 5 6 2 6 7 1 4 7 4 3 3 7 3 6 2
5