Recherche du chemin minimal dans un graphe avec poids variables

Go Hard maps

Tâche «Recherche du chemin minimal dans un graphe avec poids variables»

Soit un graphe non orienté pondéré de N sommets et M arêtes. Les poids des arêtes peuvent varier dans le temps : pour chaque arête, un poids initial et un tableau de modifications (instant et nouvelle valeur) sont donnés. Il faut trouver le chemin minimal du sommet 1 au sommet N à l’instant T. Le chemin peut passer par n’importe quel sommet, mais les poids des arêtes sont pris à l’instant T. Si le chemin n’existe pas, afficher -1.

Format d\ entrée

Première ligne : N M T (1 ≤ N ≤ 1000, 1 ≤ M ≤ 10000, 0 ≤ T ≤ 10^9). Ensuite M lignes : u v w0 k (1 ≤ u,v ≤ N, 1 ≤ w0 ≤ 1000, 0 ≤ k ≤ 100) — arête, poids initial, nombre de modifications. Puis k lignes : ti wi (0 ≤ ti ≤ T, 1 ≤ wi ≤ 1000) — instant et nouveau poids. Les modifications sont triées par ti.

Format de sortie

Un seul entier — la somme minimale des poids des arêtes sur le chemin de 1 à N à l’instant T, ou -1.

Exemples

Exemple 1

ENTRÉE

1 0
2 10 1
5

SORTIE

5

main.go