Problema grafuri orientate

1. Un client doreşte să cumpere un produs care se găseşte în n magazine. El vrea să-l cumpere la cel mai mic preţ. Pentru aceasta va trebui să meargă în p magazine indicate unde ştie că produsul se găseşte la ofertă. Clientul se deplasează cu autoturismul. Se poate ajunge de la un magazin la altul pe o stradă. Unele străzi sunt cu sens unic. Ştiind că în total sunt m străzi, cum se poate ajunge de la un magazin la altul şi timpul necesar deplasării de la un magazin la altul, realizaţi un program care să determine şi să afişeze timpul necesar clientului pentru a trece pe la cele p magazine.

Indicaţie:

Cele n magazine sunt cele n vârfuri ale unui graf orientat, iar cele m străzi sunt arcele din graf (sensul arcului este de la magazinul de la care se pleacă spre magazinul la care se ajunge), care se vor citi de la tastatură. Pentru fiecare arc se va reţine timpul de deplasare. Tot de la tastatură se va citi şirul de p magazine pe la care va trebui să meargă clientul, adică un vector cu p valori mai mici sau egale cu n. Se cere să se determine suma valorilor corespunzătoare arcelor care leagă cele p vârfuri. Graful va fi reprezentat cu ajutorul vectorului de arce.

Anunțuri