Suche nach dem kürzesten Pfad in einem Graphen mit veränderlichen Gewichten

Go Hard maps

Aufgabe «Suche nach dem kürzesten Pfad in einem Graphen mit veränderlichen Gewichten»

Gegeben ist ein ungerichteter gewichteter Graph mit N Knoten und M Kanten. Die Kantengewichte können sich im Laufe der Zeit ändern: Für jede Kante sind ein Anfangsgewicht und ein Array von Änderungen (Zeitpunkt und neuer Wert) angegeben. Es soll der kürzeste Pfad von Knoten 1 zu Knoten N zum Zeitpunkt T gefunden werden. Der Pfad darf durch beliebige Knoten verlaufen, aber die Kantengewichte werden zum Zeitpunkt T genommen. Wenn kein Pfad existiert, geben Sie -1 aus.

Eingabeformat

Erste Zeile: N M T (1 ≤ N ≤ 1000, 1 ≤ M ≤ 10000, 0 ≤ T ≤ 10^9). Danach M Zeilen: u v w0 k (1 ≤ u,v ≤ N, 1 ≤ w0 ≤ 1000, 0 ≤ k ≤ 100) — Kante, Anfangsgewicht, Anzahl der Änderungen. Dann k Zeilen: ti wi (0 ≤ ti ≤ T, 1 ≤ wi ≤ 1000) — Zeitpunkt und neues Gewicht. Die Änderungen sind nach ti sortiert.

Ausgabeformat

Eine ganze Zahl — die minimale Summe der Kantengewichte auf dem Pfad von 1 nach N zum Zeitpunkt T, oder -1.

Beispiele

Beispiel 1

EINGABE

1 0
2 10 1
5

AUSGABE

5

main.go