.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » spp

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
spp


Timp maxim de execuţie / test:
0.2s
Memorie totala disponibilă / stivă:
16MB / 1MB

În regatul său, Balaurul nu mai este aşa iubit. Nu se ştie exact de ce. Probabil din cauza temperamentului. Cert este însă faptul că mulţi îi doresc moartea, iar cei de la Serviciul de Pază şi Protecţie au mari probleme în a asigura securitatea Majestăţii Sale Arhirel.
Regatul este compus din N oraşe numerotate de la 1 la N. Între ele există drumuri, cu sens unic. Fiecare drum are un cost pe care SPP-ul trebuie să-l plăteasca pentru a asigura securitatea pe acel drum. Capitala este oraşul numărul 1 (acolo se află şi Balaurul).
Din cauza reducerilor de buget, SPP-ul asigură securitatea doar pe traseele de la capitală la orice oraş.

Cerinţă

Ajutaţi SPP-ul să aleagă o submulţime de drumuri, astfel încât costul total de securizare al drumurilor alese să fie minim şi B.A. să poata ajunge din capitală (oraşul 1) la orice oraş, mergând numai pe drumuri securizate.

Date de intrare

Pe prima linie a fişierului spp.in se află 2 numere naturale N şi M, separate printr-un spaţiu, reprezentând numarul de oraşe şi respectiv numărul de drumuri. Pe urmatoarele M linii se află câte 3 numere separate de câte un spaţiu S D C care descriu un drum şi anume: de la oraşul S la oraşul D există un drum de cost C.

Date de ieşire

Fişierul spp.out va conţine o linie cu un singur număr întreg, costul total al securizării.

Restricţii

• 1 < N < 2 001
• 1 < M < 50 001
• 0 <
costului de securizare al unui drum < 1001
• de la un oraş la altul într-un sens există maxim un drum, însă poate exista un alt drum de sens opus
• nu există drum de la un oraş la el însuşi
• tot timpul există soluţie
• 50% din teste nu vor conţine trasee care trec de două ori prin acelaşi oraş (nu există traseu de la un oraş la el însuşi)

Exemple

spp.inspp.outExplicaţii
4 4 1 2 13 1 3 15 2 4 14 3 4 3 31 Alegem drumurile: 1 -> 2, 1 -> 3 şi 3 -> 4.
Astfel putem ajunge din 1 in orice oras, iar costul total este minim.

autor: Marius Andrei
propunător: Prof. Emanuela Cerchez
Liceul de Informatica ″Grigore Moisil″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
surse trimise | ajutor