# Floyd-Warshall algorithm

user_3763047219
c_cpp
2 years ago
1.8 kB
5
Indexable
Never
```#include <iostream>

int main()
{
int n = 0, m = 0, s = 0;
scanf("%d %d", &n, &m);
int weight[201][3] = {};
int key[201] = {};
for (int i = 1; i <= m; i++) {
scanf("%d %d %d", &weight[i][0], &weight[i][1], &weight[i][2]);
}
int c[50][50] = { 0 };
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j) {
c[i][j] = 0;
}
else {
c[i][j] = 10001;
}
}
}
int count = 1;
while (count <= m) {
c[weight[count][0]][weight[count][1]] = weight[count][2];
count++;
}
for (int i = 1; i <= n; i++) {
key[i] = 10001;
}
for (int k = 1; k <= n; k++) {
for (int j = 1; j <= n; j++) {
for (int i = 1; i <= n; i++) {
if (i != j) {
if (c[i][j] > c[i][k] + c[k][j]) {
c[i][j] = c[i][k] + c[k][j];
}
}
}
}
}
for (int i = 1; i < n; i++) {
for (int j = 1; j < n; j++) {
if (c[i][j] == 10001) {
printf("N ");
}
else {
printf("%d ", c[i][j]);
}
}
if (c[i][n] == 10001) {
printf("N");
}
else {
printf("%d", c[i][n]);
}
printf("\n");
}

for (int j = 1; j < n; j++) {
if (c[n][j] == 10001) {
printf("N ");
}
else {
printf("%d ", c[n][j]);
}
}
if (c[n][n] == 10001) {
printf("N");
}
else {
printf("%d", c[n][n]);
}
}
```