#include <stdio.h>

struct node {
    unsigned dist[20];
    unsigned from[20];
} rt[10];

int main() {
    int costmat[20][20];
    int nodes, i, j, k, count;

    printf("Enter the number of nodes: ");
    scanf("%d", &nodes);

    printf("Enter the cost matrix:\n");
    for (i = 0; i < nodes; i++) {
        for (j = 0; j < nodes; j++) {
            scanf("%d", &costmat[i][j]);
            rt[i].dist[j] = costmat[i][j]; // Initialize distance
            rt[i].from[j] = (costmat[i][j] != 0 && costmat[i][j] != 1000) ? j : -1; // Set 'from' based on cost
        }
    }

    // Set diagonal to 0
    for (i = 0; i < nodes; i++) {
        rt[i].dist[i] = 0;
        rt[i].from[i] = i;
    }

    // Floyd-Warshall Algorithm
    do {
        count = 0;
        for (i = 0; i < nodes; i++) {
            for (j = 0; j < nodes; j++) {
                for (k = 0; k < nodes; k++) {
                    if (rt[i].dist[j] > rt[i].dist[k] + rt[k].dist[j]) {
                        rt[i].dist[j] = rt[i].dist[k] + rt[k].dist[j];
                        rt[i].from[j] = k;
                        count++;
                    }
                }
            }
        }
    } while (count != 0);

    // Output the final routing table
    printf("\nUpdated routing table\n");
    for (i = 0; i < nodes; i++) {
        for (j = 0; j < nodes; j++) {
            if (rt[i].from[j] != -1) {
                printf("%d ", rt[i].dist[j]);
            } else {
                printf("inf ");  // Use "inf" to indicate no path
            }
        }
        printf("\n");
    }

    return 0;
}