Поиск минимального пути в графе с изменяемыми весами

Go Сложный maps

Задача «Поиск минимального пути в графе с изменяемыми весами»

Дан неориентированный взвешенный граф из N вершин и M рёбер. Веса рёбер могут изменяться со временем: для каждого ребра задан начальный вес и массив изменений (момент времени и новое значение). Требуется найти минимальный путь от вершины 1 до вершины N в момент времени T. Путь может проходить через любые вершины, но веса рёбер берутся на момент времени T. Если пути не существует, вывести -1.

Формат ввода

Первая строка: N M T (1 ≤ N ≤ 1000, 1 ≤ M ≤ 10000, 0 ≤ T ≤ 10^9). Далее M строк: u v w0 k (1 ≤ u,v ≤ N, 1 ≤ w0 ≤ 1000, 0 ≤ k ≤ 100) — ребро, начальный вес, количество изменений. Затем k строк: ti wi (0 ≤ ti ≤ T, 1 ≤ wi ≤ 1000) — момент времени и новый вес. Изменения отсортированы по ti.

Формат вывода

Одно целое число — минимальная сумма весов рёбер в пути от 1 до N в момент T, или -1.

Примеры

Пример 1

ВВОД

1 0
2 10 1
5

ВЫВОД

5

main.go