Sol
1
F11 Competition Iași · 1 Martie 2011 – 31 Mai 2011 razboi soluție Timp: O(N 3 ) | Spațiu: O(N 2 ) citește_graf Citesc matricea grafului orientat drumuri_min Generează matricea D a drumurilor minime. D[i][j] va conţine timpul drumului minim de la i la j sau 0 daca nu există drum de la i la j. verifică_se_poate Generează şirul S. S[i] va conţine timpul pentru a ajunge în oraşul i sau 0 dacă nu se poate ajunge în oraşul i. Pentru oraşul i se caută drumurile de la toate celelate oraşe la el. Se reţine în S[i] maximul timpilor acestora. Afişează_timp_minim Afișează S[x]. determină_optim Afişează i, S[i] > 0, minim. Prof. Marinel Șerban Colegiul Național Emil Racoviță Iași [email protected]
-
Upload
andrei-grigoras -
Category
Documents
-
view
212 -
download
0
description
sol
Transcript of Sol
F11 Competition
Iași · 1 Martie 2011 – 31 Mai 2011
razboi soluție
Timp: O(N3) | Spațiu: O(N2) citește_graf
Citesc matricea grafului orientat
drumuri_min
Generează matricea D a drumurilor minime.
D[i][j] va conţine timpul drumului minim de la i la j sau 0 daca nu există drum de la i la j.
verifică_se_poate
Generează şirul S.
S[i] va conţine timpul pentru a ajunge în oraşul i sau 0 dacă nu se poate ajunge în oraşul i.
Pentru oraşul i se caută drumurile de la toate celelate oraşe la el. Se reţine în S[i] maximul timpilor acestora.
Afişează_timp_minim
Afișează S[x].
determină_optim
Afişează i, S[i] > 0, minim.
Prof. Marinel Șerban
Colegiul Național Emil Racoviță Iași
