Floyd-Warshall algorithm

 avatar
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]);
    }
}