29ος ΠΔΠ B' Φάση Λυκείου
Κάρτες απεριόριστων πτήσεων (uflights)

Ο Κώστας ταξιδεύει πολύ. Η δουλειά του τον θέλει αυτή τη βδομάδα στο Παρίσι, την επόμενη στη Σόφια, μετά από δυο μέρες στο Πεκίνο, ύστερα στην Αθήνα, ουφ, κουράστηκα και να σας τα λέω… Φυσικά ξοδεύει ένα σωρό λεφτά για τα αεροπορικά εισιτήρια.

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

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

Πρόβλημα

Να αναπτύξετε ένα πρόγραμμα σε μια από τις Γλώσσες του IOI (PASCAL, C, C++, Java) το οποίο, αφού διαβάσει τις διαθέσιμες κάρτες απεριορίστων πτήσεων και το κόστος κάθε μίας, θα υπολογίζει το ελάχιστο ποσό που πρέπει να πληρώσει ο Κώστας για να αγοράσει κάποιες από αυτές, έτσι ώστε να μπορεί να ταξιδεύει από οποιοδήποτε αεροδρόμιο σε οποιοδήποτε άλλο.

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

Τα αρχεία εισόδου με όνομα uflights.in είναι αρχεία κειμένου με την εξής δομή: Στην πρώτη γραμμή υπάρχουν δύο ακέραιοι αριθμοί, \(N\) και \(M\), χωρισμένοι μεταξύ τους με ένα κενό διάστημα. Ο αριθμός \(N\) (\(1 \leq N \leq 100.000\)) αντιστοιχεί στο πλήθος των αεροδρομίων και ο αριθμός \(M\) (\(1 \leq M \leq 1.000.000\)) αντιστοιχεί στο πλήθος των διαθέσιμων καρτών απεριορίστων πτήσεων. Κάθε μία από τις επόμενες \(M\) γραμμές περιέχει τρεις ακέραιους αριθμούς, \(A\), \(B\) και \(K\), χωρισμένους ανά δύο με ένα κενό διάστημα, και περιγράφει μία διαθέσιμη κάρτα απεριορίστων πτήσεων μεταξύ των αεροδρομίων \(A\) (\(1 \leq A \leq N\)) και \(B\) (\(1 \leq B \leq N\)), με κόστος \(K\) (\(1 \leq K \leq 100\)). Θεωρούμε ότι τα αεροδρόμια είναι αριθμημένα από \(1\) έως και \(N\) και ότι \(A \neq B\).

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

Τα αρχεία εξόδου με όνομα uflights.out είναι αρχεία κειμένου με την εξής δομή. Έχουν ακριβώς μία γραμμή με έναν ακέραιο αριθμό: Το ελάχιστο συνολικό κόστος ώστε ο Κώστας να μπορεί να μεταβαίνει από οποιοδήποτε αεροδρόμιο σε οποιοδήποτε άλλο.

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

uflights.in	uflights.out
7 9 1 2 50 3 1 10 4 6 80 1 4 40 3 5 20 4 3 30 2 6 60 5 6 70 5 7 90	260

Ο Κώστας μπορεί να επιλέξει να αγοράσει τις κάρτες \(1\leftrightarrow 2\), \(3\leftrightarrow 1\), \(3\leftrightarrow 5\), \(4\leftrightarrow 3\), \(2\leftrightarrow 6\) και \(5\leftrightarrow 7\), με συνολικό κόστος:

\[50 + 10 + 20 + 30 + 60 + 90 = 260\]

Έτσι, μπορεί να ταξιδεύει από οποιοδήποτε αεροδρόμιο σε οποιοδήποτε άλλο, π.χ., αν χρειαστεί να ταξιδέψει από το αεροδρόμιο \(1\) στο αεροδρόμιο \(7\), μπορεί να ακολουθήσει τη διαδρομή \(1\leftrightarrow 3 \leftrightarrow 5 \leftrightarrow 7\). Δεν υπάρχει φθηνότερη επιλογή καρτών με την οποία να μπορεί να πετύχει το σκοπό του.

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