在具有可变权重的图中寻找最短路径

Go Hard maps

任务 «在具有可变权重的图中寻找最短路径»

给定一个包含 N 个顶点和 M 条边的无向加权图。边的权重会随时间变化：每条边都有一个初始权重和一个变化数组（包含时间点和新值）。需要找到在时间 T 时从顶点 1 到顶点 N 的最短路径。路径可以经过任意顶点，但边的权重取时间 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 排序。

输出格式

一个整数——在时刻T从1到N的路径中边的最小权重和，或-1。

示例

示例 1

输入

1 0
2 10 1
5

输出

5

main.go