Solutii la concursul acm 2013 etapa nationala partea I

Solutii la concursul ACM ICPC 2013 etapa nationala partea I

Problema aceasta ne dădea un graf ponderat şi ne cerea să aflăm timpul minim în care putem traversa graful din nodul $S$ în nodul $D$ şi în care strângem cel putin $k$ unităţi de lemn. Atunci când traversăm o muchie primim $10$ unităţi de lemn in plus.

În ciuda faptului că problema e o problemă clasică de drum minim, ea a fost rezolvată de puţine echipe. Pentru a rezolva formăm un graf în care nodurile sunt determinate de perechi de forma $(nod iniţial, cantitate de lemn)$. În plus mai observăm că putem împărţi cantităţile de lemn la 10. Acum trebuie doar să aplicăm un algoritm de drum minim pentru a afla timpul de parcurgere din nodul $(S,0)$ în nodul $(D,⌈K/10⌉)$. Pentru a lua AC era suficienta folosirea algoritmului Bellman Ford cu coadă

În ciuda faptului că problema e o problemă clasică de drum minim, ea a fost rezolvată de puţine echipe. Pentru a rezolva formăm un graf în care nodurile sunt determinate de perechi de forma $(nod iniţial, cantitate de lemn)$. În plus mai observăm că putem împărţi cantităţile de lemn la 10 şi că nu ne interesează cantităţile de lemn mai mari decât $,⌈K/10⌉$. Acum trebuie doar să aplicăm un algoritm de drum minim pentru a afla timpul de parcurgere din nodul $(S,0)$ în nodul $(D,⌈K/10⌉)$. Pentru a lua AC era suficienta folosirea algoritmului Bellman Ford cu coadă.

h2. 'J. Template Library Management':http://acm.tju.edu.cn/toj/vcontest/showp9268_J.html

public

protected