Problem
Viene fornito un grafico aciclico ponderato diretto. È necessario trovare il percorso più breve in esso
dal vertice s al vertice t.
Inserimento:
La prima riga del file di input contiene quattro numeri interi n, m, s e t - rispettivamente il numero di vertici, i bordi del grafico, i vertici iniziale e finale (1 <= n <= 100000; 0 <= m <= 200000; 1 < ;= s, t <= n).
Le m righe successive contengono le descrizioni dei bordi, una per riga.
Il numero di bordo i è descritto da tre numeri interi b
i, e
i e w
i - rispettivamente l'inizio, la fine e la lunghezza del bordo ( 1 <= b
i, e
i <= n;|w
i| <= 1000).
Il grafico non contiene cicli e loop.
Uscita:
La prima riga del file di output deve contenere un singolo numero intero, la lunghezza del percorso più breve da s a t.
Se non esiste un percorso da s a t, stampa "Irraggiungibile".
Esempi:
| Input |
Uscita |
2 1 1 2
1 2 -10
| -10 |
2 1 2 1
1 2 -10
| Irraggiungibile |