Responsive image
Meniu
Toate soluțiile
Soluţii trimise de tine
Compilator online
Ajutor

Algoritmul Bellman-Ford

Adăugată de :
sorynsoo
Sursă :
IronCoders
Autor :
sorynsoo
Grupă :
Mare
Punctaj :
0 pc

Restricţii

Citire / Scriere :
stdin, stdout
Limită timp :
130 ms
Limită memorie :
3528 kbytes

Algoritmul Bellman-Ford

Este folosit pentru a gasi un drum de cost minim dintr-un nod al grafului in toate celelalte noduri .


 

Cerinta

Se dă un graf orientat orientat cu N noduri și M muchii cu costuri.  Sa se găsească toate drumurile de cost minim care pornesc din nodul S și ajung în restul nodurilor din graf.  


 

Date de intrare

Pe prima linie se afla N, M si S .

Pe următoarele M linii se afla cate 3 numere:  X,  Y,  Z reprezentand  ca intre nodul X și nodul Y exista o muchie de cost Z .

 

Date de iesire

Pe prima linie se afla N numere.  Al i-lea număr reprezinta costul minim al drumului de la nodul X la nodul i.

 

Restrictii

N <= 30000

M <=  40000

 

Rezolvare: Click

 

Exemplu

  Date intrare  Date iesire
  7 9 1
  1 3 2
  1 4 10
  3 2 -1
  2 6 5
  4 7 17
  6 7 -1
  5 6 3
  3 6 4
  1 5 3
  0 1 2 10 3 6 5 

 


Trimite o solutie

Format: cpp şi c

Selectează runda

Trebuie să fii logat pentru a trimite surse


Indicații rezolvare

Grafuri


Comentarii

Adauga un comentariu: Click !