Busca pelo caminho mínimo em um grafo com pesos variáveis

Go Hard maps

Tarefa «Busca pelo caminho mínimo em um grafo com pesos variáveis»

Dado um grafo não direcionado ponderado com N vértices e M arestas. Os pesos das arestas podem mudar ao longo do tempo: para cada aresta é fornecido um peso inicial e um array de alterações (instante de tempo e novo valor). É necessário encontrar o caminho mínimo do vértice 1 ao vértice N no instante de tempo T. O caminho pode passar por quaisquer vértices, mas os pesos das arestas são considerados no instante T. Se não existir caminho, imprimir -1.

Formato de Entrada

Primeira linha: N M T (1 ≤ N ≤ 1000, 1 ≤ M ≤ 10000, 0 ≤ T ≤ 10^9). Em seguida, M linhas: u v w0 k (1 ≤ u,v ≤ N, 1 ≤ w0 ≤ 1000, 0 ≤ k ≤ 100) — aresta, peso inicial, número de alterações. Depois, k linhas: ti wi (0 ≤ ti ≤ T, 1 ≤ wi ≤ 1000) — instante de tempo e novo peso. As alterações estão ordenadas por ti.

Formato de Saída

Um único número inteiro — a soma mínima dos pesos das arestas no caminho de 1 até N no instante T, ou -1.

Exemplos

Exemplo 1

ENTRADA

1 0
2 10 1
5

SAÍDA

5

main.go