Strade e Guadagni

Attenzione: Questo task ha un tempo limite di 10 minuti per l'invio della soluzione. Una volta richiesto un input, il timer partirà in automatico, e dopo la scadenza non sarà più possibile inviare una soluzione per quell'input. È sempre possibile richiedere un nuovo input, per cui non preoccuparti se il timer scade: dovrai semplicemente richiedere e scaricare un nuovo input.

Per aiutarti con questo task, abbiamo preparato delle tracce di soluzione, che includono solo le parti di lettura dell'input e scrittura dell'output (da tastiera e su schermo). Puoi decidere se leggere/scrivere su file decommentando le opportune righe di codice.

• Scarica la traccia in C: guadagni.c
• Scarica la traccia in C++: guadagni.cpp
• Scarica la traccia in C#: guadagni.cs
• Scarica la traccia in Go: guadagni.go
• Scarica la traccia in JavaScript: guadagni.html
• Scarica la traccia in Java: guadagni.java
• Scarica la traccia in Pascal: guadagni.pas
• Scarica la traccia in Python: guadagni.py
• Scarica la traccia in VisualBasic: guadagni.vb

Descrizione del problema

Noemi sta programmando la sua prossima vacanza in Truffandia! In Truffandia ci sono $N$ città collegate da $M$ strade bidirezionali (cioè ogni strada è attraversabile in entrambi i versi). Per percorrere ogni strada Noemi impiega un giorno di cammino.

Noemi infatti ha deciso che non vuole spendere soldi per questa vacanza, e si manterrà solo grazie agli introiti degli interessanti podcast che registrerà sul suo viaggio! Il pubblico di Noemi è molto affezionato e costante: al netto delle spese per alimentarsi, Noemi sa che riceverà una rendita di $1$ moneta al termine di ogni giornata del suo viaggio, direttamente sul suo conto.

In ognuna delle $N$ città c'è un servizio di navette: nella città numero $i$ spendendo $C_i$ monete Noemi può spostarsi con una navetta in una delle città collegate alla città $i$, risparmiandosi un giorno di cammino. Purtroppo gli abitanti di Truffandia non sono molto corretti: infatti, ogni volta che Noemi spenderà soldi per una navetta il suo conto si azzererà completamente. Non solo, anche appena atterrerà in Truffandia il suo conto si azzererà completamente!

Noemi partirà quindi dalla città $0$ con $0$ monete sul conto, e vorrebbe sapere quale è il minor numero di giorni di cammino che dovrà fare per raggiungere la $N-1$-esima città, sfruttando la rete di strade e le navette quando possibile. Sapresti aiutarla?

Formato di input

La prima riga del file di input contiene un intero $T$, il numero di casi di test. Seguono $T$ casi di test, numerati da $1$ a $T$. Ogni caso di test è preceduto da una riga vuota.

Ogni caso di test è composto come segue:

• una riga contenente i due interi $N$, $M$.
• $M$ righe, la $i$-esima contenente due interi $A_{i}$, $B_{i}$ che indicano la presenza di una strada bidirezionale tra $A_{i}$ e $B_{i}$.
• una riga contenente gli $N$ interi $C_{0}, \, \ldots, \, C_{N-1}$.

Formato di output

Il file di output deve contenere la risposta ai casi di test che sei riuscito a risolvere. Per ogni caso di test che hai risolto, il file di output deve contenere una riga con la dicitura

"Case #test: x"

dove $\mathtt{test}$ è il numero del caso di test (a partire da $1$) e l'intero $\mathtt{x}$ è il numero di giorni di cammino che servono a Noemi per raggiungere la sua meta.

Assunzioni

• $T = 10$, nei file di input che scaricherai saranno presenti esattamente $10$ casi di test.
• $1 \le N \le 10\ 000$.
• $1 \le M \le 10\ 000$.
• $0 \le A_i,B_i \le N-1$ per ogni $0 \le i \le M-1$.
• $1 \le C_i \le 100\ 000$ per ogni $0 \le i \le N-1$.
• è garantito sia possibile raggiungere la città $N-1$ partendo dalla città $0$.

Nei primi $2$ casi di test la rete di strade è un albero: M = N-1.

Esempi di input/output

---

Input:

3

6 7
0 1
2 1
5 4
3 5
0 2
2 4
3 0
3 3 1 2 3 2

6 6
0 1
2 1
5 4
0 1
3 0
2 4
3 1 3 2 1 3

5 4
0 1 
3 1 
2 3 
4 2 
3 3 2 1 1

---

Output:

Case #1: 2
Case #2: 2
Case #3: 3

---

Spiegazione

Nel primo caso d'esempio Noemi può:

• camminare per un giorno sulla strada $0 \rightarrow 2$. A fine giornata troverà sul conto una moneta.
• prendere la navetta sulla strada $2 \rightarrow 4$.
• camminare per un giorno sulla strada $4 \rightarrow 5$ raggiungendo la destinazione finale.

in totale Noemi cammina $2$ giorni, e non si può fare di meglio.

Nel secondo caso d'esempio Noemi può:

• camminare per un giorno sulla strada $0 \rightarrow 1$. A fine giornata troverà sul conto una moneta.
• prendere la navetta sulla strada $1 \rightarrow 2$.
• camminare per un giorno sulla strada $2 \rightarrow 4$. A fine giornata troverà sul conto una moneta.
• prendere la navetta sulla strada $4 \rightarrow 5$ raggiungendo la destinazione finale.

in totale Noemi cammina $2$ giorni, e non si può fare di meglio.

Nel terzo caso d'esempio la disposizione delle città di Truffandia è: