Αρχική > 26ος ΠΔΠ

26ος ΠΔΠ Καμπ (seniors)
Σύστημα πλοήγησης (driveme)

Έστω ότι δίνεται ένας χάρτης, αποτελούμενος από \(N\) τοποθεσίες και \(M\) δρόμους μονής κατεύθυνσης που συνδέουν αυτές τις τοποθεσίες. Για κάθε δρόμο από την τοποθεσία \(u\) προς την τοποθεσία \(v\) είναι γνωστό το μήκος του \(d_{u,v}\). Θέλουμε να φτιάξουμε ένα σύστημα υποστήριξης πλοήγησης, που θα δίνει κατευθύνσεις στους οδηγούς πώς να πηγαίνουν από μία τοποθεσία σε μία άλλη. Συγκεκριμένα, μας ενδιαφέρει να βρίσκουμε το μήκος της ελάχιστης διαδρομής από μία τοποθεσία σε μία άλλη.

Υπό κανονικές συνθήκες, τα αυτοκίνητα κινούνται όπως δείχνει η κατεύθυνση των δρόμων. Όμως, μερικές φορές, οι οδηγοί παραβιάζουν τον κώδικα οδικής κυκλοφορίας και οδηγούν ανάποδα στους δρόμους! Αυτό είναι φυσικά παράνομο και πρέπει να το αποφεύγουμε! Οι οδηγοί που επιλέγουν να το κάνουν, προσπαθούν να περιορίσουν όσο περισσότερο γίνεται το πλήθος των παρανομιών που κάνουν σε μία διαδρομή, δηλαδή το πλήθος των δρόμων που θα οδηγήσουν με κατεύθυνση αντίστροφη προς την κανονική. Το σύστημα πλοήγησης θέλουμε να «επιτρέπει» στους οδηγούς να κάνουν το πολύ \(K\) παρανομίες.

Δεδομένου του χάρτη και του \(K\), θέλουμε να μπορούμε να απαντάμε σε ερωτήσεις της μορφής: «ποιο είναι το μήκος της ελάχιστης διαδρομής από την τοποθεσία \(u\) στην τοποθεσία \(v\), αν ο οδηγός είναι διατεθειμένος να παρανομήσει το πολύ \(p\) φορές;» (όπου \(0 \leq p \leq K\)).

Αρχεία Εισόδου (driveme.in):

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

Οι επόμενες \(M\) γραμμές αντιστοιχούν στους δρόμους. Κάθε μία θα περιέχει τρεις φυσικούς αριθμούς \(u\), \(v\) και \(d_{u,v}\), χωρισμένους ανά δύο με ένα κενό διάστημα. Θα είναι \(1 \leq u, v \leq N\), και \(1 \leq d_{u,v} \leq 10^6\).

Οι επόμενες \(Q\) γραμμές αντιστοιχούν στις ερωτήσεις. Κάθε μία θα περιέχει τρεις φυσικούς αριθμούς \(u\), \(v\) και \(p\), χωρισμένους ανά δύο με ένα κενό διάστημα. Θα είναι \(1 \leq u, v \leq N\), και \(0 \leq p \leq K\).

Αρχεία Εξόδου (driveme.out):

Η έξοδος πρέπει να αποτελείται από \(Q\) γραμμές, κάθε μία από τις οποίες θα περιέχει έναν ακριβώς φυσικό αριθμό. Η \(k\)-οστή γραμμή της εξόδου θα περιέχει την απάντηση στην \(k\)-οστή ερώτηση. Αν για κάποια ερώτηση δεν υπάρχει διαδρομή από την τοποθεσία \(u\) στην τοποθεσία \(v\) με το πολύ \(p\) παρανομίες, η αντίστοιχη γραμμή της εξόδου πρέπει να περιέχει τη λέξη «IMPOSSIBLE».

Παράδειγμα Αρχείου Εισόδου - Εξόδου:

driveme.in driveme.out
6 9 2 10
2 1 2
3 2 7
4 5 6
1 3 8
1 4 4
5 2 8
5 6 10
1 5 5
4 2 5
1 6 1
3 5 0
1 2 0
3 5 1
1 2 1
4 3 1
6 4 0
2 6 2
6 4 1
6 4 2
15
14
9
13
2
12
IMPOSSIBLE
17
24
16
Ο γράφος του παραδείγματος

Περιορισμοί

  • \(2 \leq N \leq 100\).
  • \(1 \leq M \leq 1.000\).
  • \(0 \leq K \leq 10\).
  • \(1 \leq Q \leq 10.000\).
  • Όρια χρόνου εκτέλεσης: \(1\) sec.
  • Όριο μνήμης: \(64\) MB.