Problem
Besi terletak pada rangkaian N (2≤N≤10
5) bucu berlabel 1…N dan portal 2N berlabel 1…2N. Setiap portal menghubungkan dua bucu berbeza u dan v (u≠v). Satu set portal boleh menyambungkan beberapa pasangan bucu.
Setiap bucu v bersebelahan dengan empat portal berbeza. Senarai portal v diberikan oleh pv=[p
v,1,p
v,2,p
v,3,p< sub>v ,4].
Kedudukan semasa anda boleh diwakili oleh pasangan tertib (bucu semasa, portal semasa); iaitu sepasang (v,p
v,i) dengan 1≤v≤N dan 1≤i≤4. Anda boleh menggunakan salah satu daripada operasi berikut untuk menukar kedudukan semasa anda:
Tukar bucu semasa dengan bergerak melalui portal semasa.
Tukar portal semasa. Pada setiap puncak, dua portal pertama dalam senarai dipasangkan dan dua portal terakhir dalam senarai juga dipasangkan. Jadi jika keadaan semasa anda ialah (v,p
v,2), maka anda boleh bertukar untuk menggunakan portal (v,p
v,1) dan kembali. Begitu juga, jika kedudukan semasa anda ialah (v,p
v,3) anda boleh beralih ke portal (v,p
v,4) dan ke belakang. tiada penukaran lain dibenarkan (cth anda tidak boleh bertukar dari portal pv,2 ke portal) p
v,4).
Terdapat 4N negeri yang berbeza secara keseluruhan. Malangnya, mana-mana negeri mungkin tidak boleh dicapai dari mana-mana negeri dengan urutan operasi yang diberikan. Oleh itu, untuk kos cv (1≤c
v≤1000) bulan, anda boleh menyusun semula senarai portal bersebelahan dengan v, dalam sebarang susunan yang anda inginkan. Selepas itu, dua portal pertama dalam senarai digabungkan menjadi satu pasangan, dan dua portal terakhir menjadi pasangan lain.
Contohnya, jika anda menyusun semula portal v dalam susunan [p
v,3,p
v,1,p
v,2, p
v,4], Ini bermakna. bagaimana jika anda berada di atas v,
Jika anda berada dalam portal p
v,1, anda boleh bertukar ke portal p
v,3 dan kembali
Jika anda berada dalam portal p
v,2, anda boleh beralih ke portal p
v,4 dan kembali
Kini anda tidak boleh bertukar daripada portal p
v,1 kepada p
v,2, atau daripada portal p
v,3 kepada portal p
v,4 dan sebaliknya.
Kira bilangan bulan minimum yang diperlukan untuk mengubah suai rangkaian sedemikian rupa untuk menjadikan setiap negeri boleh dicapai dari setiap negeri. Adalah dijamin bahawa data ujian dibina sedemikian rupa sehingga terdapat sekurang-kurangnya satu cara untuk mengubah suai rangkaian dengan cara ini.
Input:
Baris pertama mengandungi N.
Setiap baris N seterusnya menerangkan satu bucu. Rentetan v+1 mengandungi 5 integer yang dipisahkan ruang c
v,p
v,1,p
v,2,p
v ,3,p
v,4.
Ia dijamin bahawa bagi setiap v semua p
v,1,p
v,2,p
v,3,p
v, 4 adalah berbeza, dan setiap portal muncul dalam senarai tepat dua bucu.
Output:
Satu baris mengandungi bilangan bulan minimum yang diperlukan untuk mengubah suai rangkaian untuk menjadikan setiap negeri boleh dicapai dari negeri lain.
Contoh
| # |
Input |
Output |
Penjelasan |
| 1 |
5
10 1 4 8 9
11 1 2 5 6
12 9 10 2 3
3 4 3 6 7
15 10 8 7 5 |
13 |
Ia sudah cukup untuk menukar senarai bucu 1 dan 4. Ini memerlukan c1+c4=13 muns. Pilih atur ialah: p1=[1,9,4,8] dan p4=[7,4,6,3]. |