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

27ος ΠΔΠ Καμπ (κοινά)
Αεροδρόμια και τρένα (airports)

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

Σκοπός των μηχανικών είναι όλες οι πόλεις να συνδέονται με όλες τις άλλες πόλεις. Δύο πόλεις θεωρούνται συνδεδεμένες αν συνδέονται σιδηροδρομικά (μπορεί και μέσω ενδιάμεσων πόλεων) ή αν καθεμία τους συνδέεται σιδηροδρομικά με άλλη πόλη που έχει αεροδρόμιο.

Γράψτε ένα πρόγραμμα που να υπολογίζει το ελάχιστο κόστος για να συνδεθούν όλες οι πόλεις μεταξύ τους.

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

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

Κάθε μία από τις επόμενες \(M\) γραμμές της εισόδου θα περιέχει δύο φυσικούς αριθμούς \(i\) και \(A_i\) χωρισμένους μεταξύ τους με ένα κενό διάστημα, που δηλώνουν το κόστος \(A_i\) κατασκευής αεροδρομίου στην \(i\)-οστή πόλη. Θεωρήστε ότι οι πόλεις είναι αριθμημένες από \(1\) έως \(N\) και ότι για κάθε πόλη θα δηλώνεται το πολύ ένα κόστος αεροδρομίου.

Κάθε μία από τις επόμενες \(K\) γραμμές της εισόδου θα περιέχει τρεις φυσικούς αριθμούς \(i\), \(j\), και \(B_{ij}\), χωρισμένους μεταξύ τους με ένα κενό διάστημα, που δηλώνουν το κόστος κατασκευής σιδηροδρομικής γραμμής που να συνδέει την \(i\)-οστή και την \(j\)-οστή πόλη. Θεωρήστε ότι οι σιδηροδρομικές γραμμές λειτουργούν και προς τις δύο κατευθύνσεις, ότι οι αριθμοί \(i\) και \(j\) είναι διαφορετικοί και ότι μεταξύ ενός ζεύγους πόλεων θα δηλώνεται το πολύ ένα κόστος σιδηροδρομικής γραμμής. Θεωρήστε επίσης ότι αν κατασκευαστούν όλες οι σιδηροδρομικές γραμμές, τότε κάθε πόλη θα είναι συνδεδεμένη με κάθε άλλη.

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

Η έξοδος πρέπει να αποτελείται από μία γραμμή που θα περιέχει έναν μόνο φυσικό αριθμό: το ελάχιστο κόστος για να συνδεθούν όλες οι πόλεις.

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

airports.in airports.out
7 2 8
1 5
7 3
1 2 3
1 3 2
6 4 2
3 5 2
5 2 1
5 6 9
6 7 2
2 3 5
17

Εξήγηση παραδείγματος: Το ελάχιστο κόστος προκύπτει αν κατασκευαστούν τα δύο αεροδρόμια στις πόλεις \(1\) και \(7\), με κόστος \(5+3=8\), και οι σιδηροδρομικές γραμμές μεταξύ των πόλεων \((1, 3)\), \((3, 5)\), \((5, 2)\), \((6, 7)\) και \((6, 4)\) με κόστος \(2+2+1+2+2=9\), δηλαδή συνολικό κόστος \(8+9=17\).

Ο γράφος του παραδείγματος

Περιορισμοί

  • \(2 \leq N \leq 10.000\).
  • \(0 \leq M \leq N\).
  • \(N−1 \leq K \leq 500.000\).
  • \(1 \leq A_i \leq 100.000\).
  • \(1 \leq B_{ij} \leq 100.000\).
  • Όριο χρόνου εκτέλεσης: \(1\) sec.
  • Όριο μνήμης: \(64\) MB.