#include <stdio.h>
#include <conio.h>
void main()
{
    int n, a[100][100], b[100][100], c[100][100], max=0, v1=0, v2=0;
    //Nhap mang 2 chieu mo ta do thi, -1 la ko co duong noi truc tiep, 0 la i==j, >0 khi co duong noi truc tiep giua i va j
    printf("n=");
    scanf_s("%d", &n);
    for (int i=0; i<n; i++)
        for (int j = 0; j < n; j++)
        {
            printf("a[%d][%d]=", i, j);
            scanf_s("%d", &a[i][j]);
        }
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            c[i][j] = b[i][j] = a[i][j];
    for (int k = 0; k < n; k++)
    {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (i!=j)
                {
                    if (b[i][k]+b[k][j]>b[i][j] && b[i][k]>0 && b[k][j]>0)
                    {

                        c[i][j] = b[i][k] + b[k][j];
                    }
                    else
                        c[i][j] = b[i][j];



                }
                else
                    c[i][j] = b[i][j];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                b[i][j] = c[i][j];



    }

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (c[i][j] > max)
            {
                max = c[i][j];
                v1 = i;
                v2 = j;
            }




    printf("Quang duong dai nhat noi 2 diem %d va %d la %d\n", v1, v2, max);


    _getch();
}