floyd

#include <iostream>
using namespace std;

#define INF 1000000
#define MAX 100

int G[MAX][MAX];

int maxDist = 0;

int N,M,x,y;

void floyd() {

    for (int k = 1; k <= N; k++) {
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {

                if (G[i][j] > G[i][k] + G[k][j]) {

                    G[i][j] = G[i][k] + G[k][j];

                    if (G[i][j] > maxDist) {

                        maxDist = G[i][j];
                    }
                }
            }
        }
    }
}

int main() {

    for (int i = 0; i < MAX; i++) {
        for (int j = 0; j < MAX; j++) {
            G[i][j] = INF;
        }
        G[i][i] = 0;
    }

    cin >> N >> M;

    while (M--) {
        cin >> x >> y;
        G[x][y] = G[y][x] = 1;
    }

    floyd();

    cout << maxDist - 1 << endl;

    return EXIT_SUCCESS;
}

/*
Задача 2. АВИОЛИНИИ

Авиокомпания решила да направи анализ за удобствата на услугите, които предлага. Един
от критериите за удобство на пътуването бил броят на прекачванията от един самолет на
друг. За да изготвят оценката по този критерий, служителите на авиокомпанията
направили списък на всички директни полети, които обслужва авиокомпанията, като
номерирали всички летища с поредните цели числа от 1 до N. Директните полети на
авиокомпанията се осъществявали и в двете посоки. Ясно е, че от едно летище до друго
винаги може да се достигне, при това винаги може да се избере такъв вариант за пътуване,
при който броят на прекачванията е най-малък. Ето защо от компанията решили винаги да
предлагат на пътниците си маршрути с най-малък брой прекачвания. Въпреки всичко се
оказало, че дори и след тази оптимизация има такива полети, за които прекачванията са
твърде много. В компанията искали да си отговорят на въпроса: колко е най-големият брой
прекачвания между две летища. Напишете програма aviolinii да отговори на този
въпрос.

На първия ред на стандартния вход са зададени броят N (2≤ N≤ 1000) на обслужваните от
авиокомпанията летища и броят М (2≤ М≤ 1000000) на директните полети между някои от
тях. На всеки от следващите М реда са зададени номерата на две летища свързани с
директен полет.

На един ред на стандартния изход програмата трябва да изведе максималния брой
прекачвания по някой от оптималните маршрути (по отношение на броя прекачвания) за
всеки две летища.

Примерен вход: Примерен изход:
10 11           4
1 2
1 3
1 5
1 7
1 8
4 6
5 7
5 9
5 10
6 8
9 10
/*