Bacalaureat · Grafuri și arbori · clasa a 12-a
Toate distanțele (Roy–Floyd)
Cerință
Se dă un graf orientat cu costuri pozitive. Afișează matricea costurilor minime între oricare două noduri (-1 dacă nu există drum).
Problemă originală de antrenament, nu este subiect oficial.
Date de intrare
Pe prima linie n și m, apoi m linii x y c (arc de la x la y de cost c).
Date de ieșire
n linii a câte n numere. Nu afișa mesaje suplimentare.
Restricții
- 1 ≤ n ≤ 100, 1 ≤ c ≤ 1000
- Sunt 20 de teste, fiecare valorează 5 puncte.
3 6 1 2 14 2 1 76 3 1 79 2 3 16 3 2 99 1 3 22
0 14 22 76 0 16 79 93 0
Datele exemplului respectă formatul de intrare. Aplicăm ideea: Roy–Floyd: pentru fiecare k, d[i][j] = min(d[i][j], d[i][k] + d[k][j]). Rezultatul corect pentru acest exemplu este: 0 14 22 76 0 16 79 93 0.
4 5 2 4 3 1 2 79 4 3 10 3 1 91 4 1 29
0 79 92 82 32 0 13 3 91 170 0 173 29 108 10 0
Datele exemplului respectă formatul de intrare. Aplicăm ideea: Roy–Floyd: pentru fiecare k, d[i][j] = min(d[i][j], d[i][k] + d[k][j]). Rezultatul corect pentru acest exemplu este: 0 79 92 82 32 0 13 3 91 170 0 173 29 108 10 0.
6 15 2 1 21 6 5 61 1 5 44 3 1 91 4 6 100 5 1 88 4 2 97 1 4 48 6 4 33 2 3 27 5 6 97 5 3 89 1 6 65 2 5 92 4 1 52
0 145 133 48 44 65 21 0 27 69 65 86 91 236 0 139 135 156 52 97 124 0 96 100 88 227 89 130 0 97 85 130 150 33 61 0
Datele exemplului respectă formatul de intrare. Aplicăm ideea: Roy–Floyd: pentru fiecare k, d[i][j] = min(d[i][j], d[i][k] + d[k][j]). Rezultatul corect pentru acest exemplu este: 6 linii, începând cu „0 145 133 48 44 65”.