31ος ΠΔΠ Γ' Φάση
Ελάχιστη απόσταση (shortpowtwo)

Δίνεται ένας κατευθυνόμενος γράφος με βάρη στις ακμές, τα οποία είναι (μεγάλες) δυνάμεις του \(2\). Ζητείται να υπολογιστεί η ελάχιστη απόσταση από την κορυφή \(S\) στην κορυφή \(T\). Επειδή η απόσταση αυτή μπορεί να είναι πολύ μεγάλος αριθμός, ζητείται να υπολογίσετε το υπόλοιπο της ακέραιας διαίρεσης (modulo) της απόστασης με τον αριθμό \(10^9+7\).

Πρόβλημα

Nα αναπτύξετε ένα πρόγραμμα σε μια από τις γλώσσες της IOI (Pascal, C, C++, Java) το οποίο θα διαβάζει τις ακμές του γράφου και τις κορυφές \(S\) και \(T\) και θα βρίσκει το υπόλοιπο της ακέραιας διαίρεσης (modulo) της ελάχιστης απόστασης από την \(S\) στην \(T\) με τον αριθμό \(10^9+7\).

Αρχεία εισόδου

Το αρχείο εισόδου με όνομα shortpowtwo.in είναι αρχείο κειμένου. Η πρώτη γραμμή περιέχει δύο ακεραίους \(N\) και \(M\) χωρισμένους μεταξύ τους με ένα κενό διάστημα: το πλήθος των κορυφών και το πλήθος των ακμών του γράφου, αντίστοιχα. Κάθε μία από τις επόμενες \(M\) γραμμές περιγράφει μία ακμή: περιέχει τρεις ακέραιους αριθμούς \(u\), \(v\) και \(w\) χωρισμένους ανά δύο με ένα κενό διάστημα, οι οποίοι σημαίνουν ότι υπάρχει μία ακμή από την κορυφή με αριθμό \(u\) προς την κορυφή με αριθμό \(v\), με βάρος \(2^w\). Οι κορυφές είναι αριθμημένες από \(1\) μέχρι και \(N\). Η επόμενη και τελευταία γραμμή περιέχει δύο ακέραιους αριθμούς \(S\) και \(T\), χωρισμένους με ένα κενό διάστημα: τους αριθμούς των κορυφών αφετηρίας και προορισμού.

Αρχεία εξόδου

Το αρχείο εξόδου με όνομα shortpowtwo.out είναι αρχείο κειμένου αποτελούμενο από μία μόνο γραμμή που περιέχει ακριβώς έναν ακέραιο αριθμό: το υπόλοιπο της ακέραιας διαίρεσης (modulo) της ελάχιστης απόστασης από την κορυφή \(S\) στην κορυφή \(T\) με τον αριθμό \(10^9+7\). Αν δεν υπάρχει μονοπάτι από την κορυφή \(S\) στην κορυφή \(T\), η γραμμή αυτή πρέπει να περιέχει τον αριθμό \(−1\).

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

1^o

shortpowtwo.in	shortpowtwo.out
4 4 1 4 2 1 2 0 2 3 0 3 4 0 1 4	3

2^o

shortpowtwo.in	shortpowtwo.out
4 3 1 2 4 2 3 5 3 4 6 1 4	112

3^o

shortpowtwo.in	shortpowtwo.out
4 2 1 2 0 3 4 1 1 4	-1

Προσοχή! Φροντίστε να διαβάζετε την είσοδο και να εκτυπώνετε την έξοδο αποδοτικά, ειδικά αν προγραμματίζετε σε C++ ή Java.

Περιορισμοί

Περιορισμοί:

• Για περιπτώσεις ελέγχου συνολικής αξίας 20%, θα είναι: \(1 \leq N \leq 1000\), \(0 \leq M \leq 1.000\), \(0 \leq w \leq 10\)
• Για περιπτώσεις ελέγχου συνολικής αξίας 40%, θα είναι: \(1 \leq N \leq 100.000\), \(0 \leq M \leq 100.000\), \(0 \leq w \leq 10\)
• Για περιπτώσεις ελέγχου συνολικής αξίας 65%, θα είναι: \(1 \leq N \leq 100.000\), \(0 \leq M \leq 100.000\), \(0 \leq w \leq 500\)
• Για περιπτώσεις ελέγχου συνολικής αξίας 100%, θα είναι: \(1 \leq N \leq 100.000\), \(0 \leq M \leq 100.000\), \(0 \leq w \leq 100.000\)

Παρατηρήσεις:

• Mορφοποίηση: Στην έξοδο, όλες οι γραμμές τερματίζουν με ένα χαρακτήρα newline.
• Mέγιστος χρόνος εκτέλεσης: \(2\) sec.
• Mέγιστη διαθέσιμη μνήμη: \(256\) MB.