| Ուղարկել | Բոլոր լուծումները | Լավագույն լուծումները | Վերադառնալ ցուցակին |
GM14P1 - ԳԼԽԱՎՈՐ ՃԱՆԱՊԱՐՀՆԵՐ |
Քաղաքը, որտեղ ապրում է Արթուրը, ունի N խաչմերուկ, որոնք միմյանց միացած են ճանապարհներով։ Բոլոր ճանապարհները երկկողմանի են։ Ամեն օր Արթուրը տնից գնում է աշխատանքի և հետո նորից վերադառնում է տուն։ Բայց այդ քաղաքի ճանապարհները այնքան էլ լավը չեն և հաճախ են վերանորոգման ենթարկվում։ Արթուրը նկատեց, որ երբ որոշ ճանապարհներ փակվում են վերանորոգման պատճառով, նա կարողանում է տնից աշխատանքի հասնել ճիշտ նույն ժամանակում, ինչ ժամանակում որ հասնում էր մինչ ճանապարհների փակվելը։ Մյուս կողմից կան նաև այնպիսի ճանապարհներ, որոնց փակման դեպքում տնից աշխատանքի հասնելու ժամանակն աճում է։ Իսկ երբեմն Արթուրն ընդհանրապես չի կարողանում տնից աշխատանքի հասնել։ Այդպիսի ճանապարհներն Արթուրն անվանում է գլխավոր։
Օգնե՛ք Արթուրին գտնել քաղաքի բոլոր գլխավոր ճանապարհները։
Մուտքային տվյալներ
Մուտքի առաջին տողում տրված են N և M բնական թվերը (2 ≤ N ≤ 20 000, 1 ≤ M ≤ 100 000), որոնք իրենցից ներկայացնում են համապատասխանաբար քաղաքի խաչմերուկների և ճանապարհների թիվը:
Հաջորդ M տողերը ինֆորմացիա են պարունակում ճանապարհների մասին։ Յուրաքանչյուր ճանապարհ բնութագրվում է երկու խաչմերուկներով, որոնք այդ ճանապարհը միացնում է և ժամանակով, որն անհրաժեշտ է Արթուրին ճանապարհի մի ծայրից մյուսը հասնելու համար։ Ճանապարհն անցնելու ժամանակը 100000֊ը չգերազանցող բնական թիվ է։ Երկու խաչմերուկներ կարող են միացած լինել մի քանի ճանապարհներով, բայց գոյություն չունի որևէ ճանապարհ, որը խաչմերուկը միացնում է ինքն իրեն։
Եթե բոլոր ճանապարհները հասանելի են, ապա Արթուրը միշտ կարող է տնից հասնել աշխատանքի։
Ելքային տվյալներ
Ելքում պետք է արտածել գլխավոր ճանապարհների K քանակը:
Օրինակներ՝
|
N |
stdin |
stdout |
|
1 |
2 2 |
1 |
|
2 |
6 7 |
2 |
| Ավելացրեց. | Հրանտ Հովհաննիսյան |
| Ամսաթիվ. | 2014-10-22 |
| Ժամանակի սահմանափակումը. | 1s |
| Ծրագրի տեքստի սահմանափակումը. | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Լեզուներ. | Բոլորը բացի ASM32 ASM64 GAWK CLPS CLOJURE D ERL FSHARP FORTRAN GOSU HASK ICON ICK NEM NIM OBJC-CLANG PICO PIKE PYPY PYPY3 PY_NBC RUST SCM guile CHICKEN SED TCL WHITESPACE |
| Աղբյուրը. | Գյումրի 2014 |
RSS