Εκφώνηση

Στη Αριάδνη αρέσει να ταξιδεύει με το τρένο. Κάθε φορά που επισκέπτεται μία χώρα προσπαθεί να επισκεφθεί τις διάφορες πόλεις με το τρένο. Δυστυχώς όμως δεν είναι πάντοτε εφικτό να επισκέπτεται την πόλη που επιθυμεί. Βοηθήστε την Αριάδνη φτιάχνοντας ένα πρόγραμμα που θα δέχεται το δρομολόγιο των τρένων, την πόλη αναχώρησης και την πόλη άφιξης και θα ενημερώνει την Αριάδνη αν είναι εφικτή ή όχι η επίσκεψη της. Σε περίπτωση θετικής απάντησης να τυπώνονται και οι ενδιάμεσες πόλεις από όπου περνά το τρένο.

Δεδομένα εισόδου (αρχείο “train.in”)

Οι πόλεις είναι αριθμημένες με συνεχόμενους ακέραιους αριθμούς από το μηδέν μέχρι το Ν (Ν<=1000). Στην αρχή δίνονται 2 ακέραιοι αριθμοί που αντιστοιχούν στην πόλη αναχώρησης και στην πόλη άφιξης. Στη συνέχεια ακολουθεί το δρομολόγιο των τρένων που αποτελείται από ζευγάρια ακεραίων αριθμών (Α Β) που υποδηλώνει την ύπαρξη δρομολογίου από την πόλη Α στην πόλη Β
Σημείωση: Η ύπαρξη δρομολογίου από την πόλη Α στην Β δεν υποδηλώνει και την ύπαρξη δρομολογίου από την Β στην Α.

Δεδομένα εξόδου (αρχείο “train.out”)

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

Περιορισμοί

• Όριο χρόνου εκτέλεσης: 1 sec.
• Όριο μνήμης: 64 MB.

Παράδειγμα εισόδου

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

Παράδειγμα εξόδου

-1

Παράδειγμα εισόδου 2

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

Παράδειγμα εξόδου 2

2
4
5
1

Εκφώνηση

Σε ένα ρυάκι υπάρχουν n εμπορικοί σταθμοί που αριθμούνται από 1 έως n. Σε κάθε σταθμό i μπορείς να ενοικιάσεις κανό το οποίο είναι δυνατό να επιστραφεί σε οποιοδήποτε άλλο σταθμό j > i. Ζητείται να γραφεί πρόγραμμα το οποίο δέχεται ως είσοδο ένα πίνακα C(i, j) που αντιπροσωπεύει το κόστος ενοικιάσεως από τον σταθμό i έως το σταθμό j (για κάθε 1<=i, j<=n) και επιστρέφει τη πιο φθηνή διαδρομή ενοικιάσεων από το σταθμό 1 έως το σταθμό n. Μπορείτε να υποθέσετε ότι C(i,i)=0, και ότι δεν επιτρέπεται να πάτε αντίθετα στο ρεύμα.

Δεδομένα εισόδου (αρχείο “cano.in”)

Η πρώτη γραμμή εισόδου αποτελείται από ένα θετικό ακέραιο αριθμό n που
αντιπροσωπεύει τον αριθμό των σταθμών. Οι επόμενες n γραμμές αποτελούνται από n ακέραιους αριθμούς η κάθε μια, οι οποίοι διαχωρίζονται με κενό διάστημα και έχουν τιμές μικρότερες από 1000.

Δεδομένα εξόδου (αρχείο “cano.out”)

Το πρόγραμμα πρέπει να επιστρέφει δύο γραμμές εξόδου. Η πρώτη γραμμή εξόδου θα πρέπει να αποτελείται από ένα θετικό ακέραιο αριθμό m που αντιπροσωπεύει τον αριθμό των ενοικιάσεων της πιο φθηνής διαδρομής. Η δεύτερη γραμμή θα πρέπει να αποτελείται από m+1 ακέραιους αριθμούς που υποδηλώνουν τους σταθμούς της πιο φθηνής διαδρομής από τον σταθμό 1 έως το σταθμό n.

Περιορισμοί

• Όριο χρόνου εκτέλεσης: 1 sec.
• Όριο μνήμης: 64 MB.

Παράδειγμα εισόδου

4
0 2 3 7
0 0 2 4
0 0 0 2
0 0 0 0

Παράδειγμα εξόδου

3
1 3 4