Farmer John cerca in barca il tesoro leggendario su una delle $N$ isole $(1 \le N \le 100)$ del Cowribbean Sea, numerate $1,\ldots,N$.
La mappa richiede partire da1 e finire in $N$ passando per $A_{1}$, $A_{2}$, ..., $A_{M}$, sequenza di $M$ isole $(2 \le M \le 10,000)$, prima che appaia il tesoro. Può visitare queste e altre fuori ordine e più volte, ma deve includere $A_{i}$ nell’ordine della mappa.
FJ evita pirati e conosce il pericolo $(0 \le danger \le 100,000)$ fra ogni coppia. Il totale è la somma di tutti i percorsi attraversati.
Trova la rotta meno pericolosa al tesoro che soddisfi la mappa.
Input
- Riga1: due interi separati da spazio, $N$ e $M$.
- Righe $2,\ldots,M+1$: riga $i+1$ descrive la $i_{th}$ isola obbligatoria con l’intero $A_{i}$.
- Righe $M+2,\ldots,N+M+1$: riga $i+M+1$ ha $N$ interi separati da spazio, pericoli da $i$ a1, 2, ..., $N$. L’$i$-esimo è sempre0.
Output
- Riga1: minimo pericolo per ottenere il tesoro.
Esempi
Input 1
3 4 1 2 1 3 0 5 1 5 0 2 1 2 0
Output 1
7
Nota
3 isole e4 visite:1, 2, ancora1, infine3. Percorsi(1,2), (2,3), (3,1) e inversi valgono5, 2, 1.
La rotta1, 3, 2, 3, 1, 3 dà7 e contiene1, 2, 1, 3. Evitiamo1–2, molto pericoloso.
Autore del problema: Jeffrey Wang, 2007