Cesty v orientovaném acyklickém grafu

Zadání

Budeme uvažovat grafy, v nichž jsou jak uzly tak hrany ohodnoceny celými čísly.
Uzlová délka cesty v grafu je rovna součtu vah všech uzlů této cesty. Hranová délka cesty v grafu je rovna součtu vah všech hran této cesty. Cestu nazveme hranově přípustnou, pokud v grafu neexistuje žádná jiná cesta s větší hranovou délkou.
Hranově přípustnou cestu v grafu nazveme uzlově optimální, pokud v grafu neexistuje žádná jiná hranově přípustná cesta s větší uzlovou délkou.

Obr. 1. Ilustrace k Příkladům 1, 2, 3 níže. Váhy uzlů jsou vyznačeny na tmavém pozadí. Uzlově optimální cesty vedou: V případě a) uzly 3 − 1 − 0, v případě b) uzly 2 − 0 − 1 − 5 nebo 2 − 3 − 4 − 5 nebo 2 − 6 − 7 − 5, v případě c) uzly 6 − 5 − 7.

Úloha

Určete uzlovou délku a hranovou délku některé uzlově optimální cesty v daném orientovaném acyklickém grafu.

Vstup

První řádek obsahuje dvě celá čísla N, M oddělená mezerou a představující (v tomto pořadí) počet uzlů a hran v daném acyklickém orientovaném grafu. Uzly grafu jsou číslovány 0, 1, …, N−1. Na druhém řádku jsou ve vzrůstajícím pořadí čísel uzlů uvedeny váhy uzlů. Jednotlivé vahy jsou odděleny mezerami. Následuje M řádků, každý specifikuje jednu hranu grafu. Řádek obsahuje tři celá čísla A, B, C (v tomto pořadí) oddělená mezerou a představující hranu z uzlu A do uzlu B s váhou C.
Platí: 2 ≤ N ≤ 10⁴, 2 ≤ M ≤ 10⁶. Všechny váhy uzlů i hran nepřesáhnou v absolutní hodnotě 10³.

Výstup

Výstup obsahuje jeden textový řádek s dvěma celými čísly UD a HD oddělenými mezerou. UD představuje uzlovou délku některé uzlově optimální cesty v daném grafu, HD představuje hranovou délku téže cesty.

Příklady

Příklad 1

Vstup

4 5
-1 -1 -3 -1
1 0 10
2 1 -5
3 2 -5
3 1 15
2 0 25

Výstup

-3 25

Graf v Příkladu 1 je znázorněn na Obrázku 1a).

Příklad 2

Vstup

8 9
1 6 100 2 5 100 3 4
2 0 20
2 3 30
2 6 10
0 1 30
3 4 10
6 7 20
1 5 10
4 5 20
7 5 30

Výstup

207 60

Graf v Příkladu 2 je znázorněn na Obrázku 1b).

Příklad 3

Vstup

8 8
10 40 90 20 50 90 30 60
0 2 2
2 1 5
3 2 2
2 4 4
3 5 2
5 4 1
6 5 5
5 7 2

Výstup

180 7

Graf v Příkladu 3 je znázorněn na Obrázku 1c).

Veřejná data

Veřejná data k úloze jsou k dispozici. Veřejná data jsou uložena také v odevzdávacím systému a při každém odevzdání/spuštění úlohy dostává řešitel kompletní výstup na stdout a stderr ze svého programu pro každý soubor veřejných dat.

Veřejná data