Búsqueda del camino mínimo en un grafo con pesos variables

Go Hard maps

Tarea «Búsqueda del camino mínimo en un grafo con pesos variables»

Dado un grafo no dirigido y ponderado de N vértices y M aristas. Los pesos de las aristas pueden cambiar con el tiempo: para cada arista se da un peso inicial y un arreglo de cambios (momento de tiempo y nuevo valor). Se requiere encontrar el camino mínimo desde el vértice 1 hasta el vértice N en el momento de tiempo T. El camino puede pasar por cualquier vértice, pero los pesos de las aristas se toman en el momento T. Si no existe camino, mostrar -1.

Formato de entrada

Primera línea: N M T (1 ≤ N ≤ 1000, 1 ≤ M ≤ 10000, 0 ≤ T ≤ 10^9). Luego M líneas: u v w0 k (1 ≤ u,v ≤ N, 1 ≤ w0 ≤ 1000, 0 ≤ k ≤ 100) — arista, peso inicial, cantidad de cambios. Luego k líneas: ti wi (0 ≤ ti ≤ T, 1 ≤ wi ≤ 1000) — momento de tiempo y nuevo peso. Los cambios están ordenados por ti.

Formato de salida

Un número entero — la suma mínima de los pesos de las aristas en el camino desde 1 hasta N en el momento T, o -1.

Ejemplos

Ejemplo 1

ENTRADA

1 0
2 10 1
5

SALIDA

5

main.go