Գտնել ամենակարճ ճանապարհը 4
Ձեզ տրված է քարտեզ, որը բաղկացած է
n քաղաքից և m երկկողմանի ճանապարհից, որոնք կապում են այդ քաղաքները: Յուրաքանչյուր ճանապարհի երկարությունը ոչ բացասական ամբողջ թիվ է, որը նշանակված է -ով: Ձեր խնդիրը ամենակարճ ճանապարհը գտնելն է 1-ին քաղաքից մինչև n-րդ քաղաքը:💡
Ուշադրություն դարձրեք, որ այս առաջադրանքում անհրաժեշտ է գտնել և՛ ամենակարճ ճանապարհի երկարությունը, և՛ ինքը՝ ճանապարհը:
Մուտք
Մուտքի առաջին տողում տրված են երկու ամբողջ թվեր
n և m (), որոնք ցույց են տալիս քաղաքների քանակը և ճանապարհների քանակը, համապատասխանաբար:Հաջորդ
m տողերից յուրաքանչյուրում տրված են երեք ամբողջ թվեր , և , որոնք նկարագրում են ճանապարհը և քաղաքների միջև, որի երկարությունը է ():Ելք
Ելքում պետք է տպել երկու ամբողջ թիվ
k և l, որոնք բաժանված են բացատով: Այստեղ k-ն ամենակարճ ճանապարհում ընդգրկված քաղաքների քանակն է, իսկ l-ը՝ այդ ճանապարհի երկարությունը:Հաջորդ տողում պետք է տպել
k ամբողջ թիվ (բացատով բաժանված), որոնք հերթով ներկայացնում են ամենակարճ ճանապարհի քաղաքները:Եթե կա մեկից ավելի ամենակարճ ճանապարհ, կարող եք արտածել ցանկացածը: Նկատի ունեցեք, որ անհրաժեշտ չէ նվազագույնի հասցնել
k-ի արժեքը:Օրինակներ
Մուտք | Ելք |
4 5
1 2 3
1 3 5
2 4 3
3 4 3
1 4 7 | 3 6
1 2 4 |
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 5 MB