Hello Miltos, I want to play a game.
Η συσκευή που έχω συνδέσει πάνω σου πρόκειται να εκραγεί. Η ελπίδα σου βρίσκεται στο κλειδί στο δωμάτιο Β. Όμως για να φτάσεις εκεί πρέπει να περάσεις από πολλές παγίδες. Κάποιοι διάδρομοι δεν είναι γεμάτοι με νερό και δε μπορείς να περάσεις. Θα προλάβεις να φτάσεις; Live or die. It's your choice."
Ο Μίλτος το δελφίνι γνωρίζει ότι βρίσκεται στο δωμάτιο Α κι ότι αν φτάσει στο δωμάτιο Γ μπορεί να ενεργοποιήσει την πυρασφάλεια, γεμίζοντας κάθε διάδρομο με νερό. Μπορείς να βοηθήσεις τον Μίλτο να φτάσει ασφαλής και όσο το δυνατόν πιο σύντομα στο δωμάτιο Β αν ο Jigsaw του έχει δώσει χάρτη του σπιτιού;
Στην πρώτη γραμμή δίνονται δύο αριθμοί Ν και Μ, ο αριθμός των δωματίων και των διαδρόμων αντίστοιχα.
Η δεύτερη γραμμή περιέχει τρεις αριθμούς Α, Β, Γ, το δωμάτιο στο οποίο βρίσκεται ο Μίλτος, το δωμάτιο στο οποίο πρέπει να φτάσει, και το δωμάτιο απ' το οποίο μπορεί να ενεργοποιήσει την πυρασφάλεια.
Στην κάθε μία απ' τις επόμενες Μ γραμμές περιέχονται τρεις αριθμοί v1, v2, type, που δηλώνουν διάδρομο που συνδέει το v1 με το v2 ( προφανώς και το v2 με το v1 ). Αν type=0 τότε ο διάδρομος είναι γεμάτος νερό κι ο Μίλτος μπορεί να τον διασχίσει. Αν type=1 τότε ο διάδρομος δεν έχει νερό κι ο Μίλτος για να τον διασχίσει πρέπει πρώτα να έχει περάσει απ' το δωμάτιο Γ.
Έναν αριθμό D, το μήκος της ελάχιστης διαδρομής που πρέπει να κάνει ο Μίλτος ώστε να φτάσει στο δωμάτιο Β.
Θεωρείστε ότι υπάρχει πάντα τρόπος να φτάσει ο Μίλτος στο δωμάτιο Β.
1<=Ν<=10.000
1<=Μ<=100.000
1<=Α,Β,Γ,v1,v2<=N
Θεωρήστε ότι όλοι οι διάδρομοι έχουν μήκος 1.
3 2 1 2 3 1 3 0 1 2 0
1
3 2 1 2 3 1 3 0 1 2 1
3
Δεν μπορεί να πάει απευθείας απ' το 1 στο 2 γιατί ο διάδρομος δεν έχει νερό. Πρέπει πρώτα νε περάσει από το 3 για να ενεργοποιήσει την πυρασφάλεια.