30ος ΠΔΠ Καμπ (seniors)
Το μετρό της Θεσσαλονίκης (metro)

Βρισκόμαστε στο έτος 2026, ακριβώς 50 χρόνια από το 1976 όταν πρωτοπάρθηκε η απόφαση για το μετρό της Θεσσαλονίκης. Τα εγκαίνια εξέπληξαν τους πάντες κι οι ανυπόμονοι που είχαν πει και μια κουβέντα παραπάνω, τώρα δεν ξέρουν πού να κρυφτούν απ’ τη ντροπή τους.

Το μετρό είναι τόσο όμορφο που όλος ο κόσμος το χρησιμοποιεί. Δυστυχώς αυτό έφερε πρόβλημα στο επάγγελμα των ταξί και οι ταξιτζήδες ξεκίνησαν τις διαμαρτυρίες. Πιο συγκεκριμένα, έχουν εντοπίσει τους καλύτερους δρόμους της Θεσσαλονίκης και τους μπλοκάρουν. Είναι διατεθειμένοι να σου επιτρέψουν τη διέλευση από έναν μόνο μπλοκαρισμένο δρόμο την μέρα (όχι περισσότερους). Βέβαια, ανάλογα με τις διαπραγματεύσεις των συνδικαλιστών τους επηρεάζεται και η διάθεσή τους, κι αυτό βεβαίως επηρεάζει και την ώρα που θα κάνουν να σου ανοίξουν τον δρόμο που θα ζητήσεις εκείνη τη μέρα.

Παρόλα αυτά, εσύ θεωρείς ότι αφού λόγω του μετρό οι δρόμοι πλέον είναι άδειοι, σε βολεύει να ταξιδεύεις με το αυτοκίνητό σου.

Δεδομένα εισόδου (metro.in)

Η πρώτη γραμμή της εισόδου θα περιέχει δύο φυσικούς αριθμούς \(N\) και \(M\), το πλήθος \(N \leq 10.000\) των διασταυρώσεων της πόλης, και το πλήθος \(M \leq 100.000\) των δρόμων.

Οι επόμενες \(M\) γραμμές περιγράφουν από ένα δρόμο η κάθε μία. Πιο συγκεκριμένα, η \(i\)-οστή από αυτές θα περιέχει τρεις φυσικούς αριθμούς \(u_i, v_i, t_i\) όπου \(1 \leq u_i, v_i \leq N\) οι αριθμοί των διασταυρώσεων που συνδέει ο δρόμος και \(0 \leq t_i \leq 1.000\) ο χρόνος που απαιτείται για να ταξιδέψει κανείς από τη διασταύρωση \(u_i\) στη διασταύρωση \(v_i\). Όλοι οι δρόμοι θεωρούνται μίας κατεύθυνσης. Ο χρόνος \(t_i\) είναι κανονικά θετικός αριθμός, αν όμως δοθεί \(t_i = 0\) εννοείται ότι αυτός ο δρόμος είναι κλειστός.

Ακολουθεί ένας φυσικός αριθμός \(Q \leq 20.000\): το πλήθος των ημερών στις οποίες θέλεις να ταξιδέψεις.

Οι επόμενες \(Q\) γραμμές περιγράφουν από ένα ταξίδι η κάθε μία. Η \(i\)-οστή από αυτές θα περιέχει δύο φυσικούς αριθμούς \(b_i\) και \(d_i\), όπου \(0 \leq b_i \leq 10.000\) ο χρόνος που θα σου πάρει να διασχίσεις ένα μπλοκαρισμένο δρόμο, και \(d_i\) η διασταύρωση-προορισμός σου. Θεωρούμε ότι πάντα η αφετηρία σου θα είναι η διασταύρωση με αριθμό \(1\).

Δεδομένα εξόδου (metro.out)

Η έξοδος πρέπει να περιέχει \(Q\) γραμμές: Η \(i\)-οστή από αυτές θα είναι ο ελάχιστος χρόνος που απαιτείται για το \(i\)-οστό ταξίδι.

Παράδειγμα αρχείων εισόδου - εξόδου

metro.in	metro.out
4 5 1 2 10 1 3 0 3 2 7 1 4 0 4 2 0 3 4 2 3 2 2 2	10 10 9

Εξήγηση: Όταν το κόστος για να διασχίσουμε ένα κλειστό δρόμο είναι \(4\), αυτό σημαίνει ότι στον \(2\) μπορούμε να φτάσουμε απευθείας (συνολικός χρόνος \(10\)), ή μέσω του \(3\) (συνολικός χρόνος \(11\)). Προσοχή: δεν μπορούμε να πάμε μέσω του \(4\) καθώς θα χρειαζόταν να διασχίσουμε \(2\) κλειστούς δρόμους (κάτι που δεν επιτρέπεται). Αντίστοιχα όταν το κόστος είναι \(3\), τότε και οι δύο διαδρομές είναι ίσου συνολικού χρόνου, ενώ όταν το κόστος γίνεται \(2\), μας συμφέρει να πάμε μέσω του \(3\) (συνολικός χρόνος \(9\)).

Περιορισμοί

Όριο χρόνου εκτέλεσης: \(2\) sec.
Όριο μνήμης: \(64\) MB.

Υποπροβλήματα