| Ուղարկել | Բոլոր լուծումները | Լավագույն լուծումները | Վերադառնալ ցուցակին |
CANC - Ավտոճանապարհային ցանց |
Ավտոճանապարհային ցանցը բաղկացած է որոշակի քանակությամբ մայրուղիներից: Մայրուղիներից յուրաքանչյուրը իրար է միացնում ճիշտ երկու քաղաք: Ճանապարհ կանվանենք զույգ առ զույգ իրարից տարբեր քաղաքների այնպիսի հաջորդականությունը, որում ցանկացած երկու հարևան քաղաքներ միացած են մայրուղով: Ճանապարհի երկարությունը հավասար է այն մայրուղիների երկարությունների գումարին, որոնցից այն բաղկացած է: Ցանցը կառուցված է այնպես, որ քաղաքների յուրաքանչյուր զույգի միջև գոյություն ունի միակ ճանապարհ:
Որոշ մայրուղիներ պետք է վերանորոգվեն: Ծախսերը նվազեցնելու նպատակով վերանորոգող կազմակերպությունը վերանորոգում է միայն ամբողջական ճանապարհներ, որոնք անցնում են առնվազն երկու քաղաքներով: Շփոթմունքից խուսափելու համար յուրաքանչյուր քաղաքով պետք է անցնի ճիշտ մեկ վերանորոգված ճանապարհ:
Ղեկավարությունը ուզում է, որ վերանորոգված մայրուղիների երկարությունների գումարը լինի առավելագույնը: Օգնեք ղեկավարությանը գտնել այդ գումարը:
Մուտքը
Առաջին տողը պարունակում է քաղաքների N քանակը (1 ≤ N ≤ 2000): Քաղաքները համարալաված են 1..N թվերով: Հաջորդ N-1 տողերը պարունակում են երեք ամբողջ թվեր` A, B, C, ինչը նշանակում է, որ կա A քաղաքը B քաղաքին միացնող C երկարությամբ մայրուղի (1 ≤ A, B ≤ N, 1 ≤ C ≤ 1000000):
Ելքը
Արտածել մի թիվ - խնդրի պատասխանը։
Օրինակ
Մուտքը.9
1 2 1
2 4 2
3 4 1
4 5 5
6 5 1
5 7 2
7 8 1
8 9 2 Ելքը. 11
| Ավելացրեց. | Andreasyan |
| Ամսաթիվ. | 2012-05-02 |
| Ժամանակի սահմանափակումը. | 2s |
| Ծրագրի տեքստի սահմանափակումը. | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Լեզուներ. | C CSHARP C++ 4.3.2 CPP CPP14 JAVA PAS-GPC PAS-FPC PYTHON3 |
| Աղբյուրը. | հանրապետական 2012 |
թաքցնել մեկնաբանությունները
|
2023-01-31 15:16:04
nice language |
|
|
2014-06-17 03:24:47 Spar!k
entadrvuma vor patasxan goyutyun uni. tenc test chka aysinqn. |
|
|
2014-06-01 23:30:34 Tigran Galstyan
@mushegh verj@ inch er?? |
|
|
2013-12-11 18:12:00 Mushegh
4 1 2 1 1 3 1 1 4 1 patasxany inch e? |
RSS