h2. "Foametea":https://www.infoarena.ro/problema/foametea

Problema.

Problema este împărţită în 4 subtask-uri, fiecare putând fi abordat în moduri diferite.
Pentru subtask-ul 1 putem folosi o percurgere bfs / algoritmul lui Lee, întrucât costurile pe muchii sunt egale cu 1.
Pentru subtask-ul 2 putem parcurge graful in ordinea rezultata din sortarea topologica, deoarece se garanteaza ca graful primit este DAG. Vom retine pentru fiecare nod, t[i] (timpul minim de a ajunge în nodul i) = min{t[j] + l}, unde j are proprietatea că se află la adancime cu 1 mai mica în graf faţă de nodul i, iar l este lungimea muchiei ce uneste j cu i.
Subtask-ul 3 se reduce la problema clasica a aflării drumului cel mai scurt dintre două noduri, care se poate rezolva aplicând algoritmul lui Dijkstra, sau Bellman-Ford.
Pentru rezolvarea ultimului subtask vom extinde ideea de la subtaskul precedent. Va trebui să luăm în calcul faptul că putem ajunge întru-un nod cu un număr variabil de sarmale în traistă. Vom reţine rezultatele intermediare în t[i][j] = timpul minim în care am ajuns în nodul i cu j sarmale. Astfel, pentru Dijkstra, vom folosi stări de tipul {nod, timp, nrSarmale} cu semnificaţia că am ajuns în nodul nod în timp unităţi de timp şi cu nrSarmale în traistă. Dintr-o stare vom trece în următoarele, luând în calcul toate cantităţile posiblile de sarmale pe care le putem aveam în traistă. Rezolvarea cu Bellman-Ford se bazează pe aceeaşi idee. În final, rezultatul va fi min(t[n][j]).

h2. "PS":https://www.infoarena.ro/problema/ps

public

protected