По заданной системе односторонних дорог определить, есть ли город, куда можно попасть из любого другого - C (СИ)

Формулировка задачи:

Доброго времени суток! Такая задача: По заданной системе односторонних дорог определить, есть ли в ней город, куда можно попасть из любого другого города, проезжая не более 100 км. (Необходимо применить алгоритм флойда) Никак не могу сделать программу и разобраться с алгоритмом Флойда.... и как указывать расстояние для ребер? Буду благодарен за любую помощь в решении!

Решение задачи: «По заданной системе односторонних дорог определить, есть ли город, куда можно попасть из любого другого»

Листинг программы

    #include "stdafx.h"
    #include "stdio.h"
    #include "conio.h"
    #include "iostream"
    #define  NMAX  10   
   
     
    void  vvod_grafa (int G [NMAX][NMAX], int n)
    {      
          int  i,j,km;  
          puts("\nРебра вводить по типу: '№' <Пробел> '№' <Пробел> <Тире> <Пробел> 'Расстояние'");
          puts("\nНапример: 1 2 - 30");
          printf ("Введите ребра:\n\n");
          while (scanf_s("%d %d - %d",&i,&j,&km) == 3)
          {
              G[i][j]=km; 
          }
          putchar ('\n');
    }
 
     
   
void  way( int G[NMAX][NMAX], int n, int D[NMAX][NMAX]) {
    int i, j, k;
    for  (i = 0; i < n; i++)     
        for (j = 0;j < n; j++) 
            D[i][j] = 999;
    for  (i = 0; i < n; i++) {       
         for (j = 0;j < n; j++) {
               if(G[i][j] != 0)
                   D[i][j] = G[i][j];
        }
    }
    for (i = 0; i < n; i++) {
        D[i][i] = 0; 
    }
for (k = 0; k < n; k++) {
    for (i = 0; i < n; i++) {
        if (D[i][k] != 999) {
            for (j = 0; j < n; j++) {                         
                if (D[i][k] + D[k][j] < D[i][j]) {   
                    D[i][j] = D[i][k] + D[k][j];  
                }
            }       
        }
    }
}
}
 
 
 
 
void vivod_grafa ( int g1[NMAX][NMAX], int n) 
{
   putchar ('\n');
   for (int i = 0; i < n; i++) 
   {
   printf("\n");
   for (int j = 0; j < n; j++) 
     {
      printf("%4d", g1[i][j]);
     }
   }
   putchar('\n');
}
  
 
 
void obrabotka(int D[NMAX][NMAX], int n)
{ 
int f = 1;
 
for (int j = 0; j < n; j++)
  {
   for (int i = 0; i < n; i++)
    {
     if( D[i][j] != 999)
      {
       if (j!=i && D[i][j] > 100)
        { 
          f = 0; 
        }
      }
    }
if (f == 1) printf("В город № %d можно попасть из любого другого города, проезжая не более 100 км \n", j);
f = 1;
  }
if (f == 0) printf("Такого города нет в данной системе дорог.");
}
 
 
 int main()
 { 
         setlocale(LC_ALL,"Russian");
         int G[NMAX][NMAX]={0};    
         int D[NMAX][NMAX] ;         
         int n ;                     
         puts("\n***");    
         puts("\nДобро пожаловать!!!");
         puts("\nДанная программа определяет наличие города, в которую можно попасть из любого друого города, проезжая при этом не более 100 км.");
         puts("\n***");
         putchar('\n');
         puts("\nВведите количество городов:");
         scanf_s("%d", &n);
         vvod_grafa (G,n);     
         puts("\nМатрица смежности:");
         vivod_grafa (G,n);
         putchar('\n');
         way(G, n, D);
         puts("\nРасстояние между городами:");
         vivod_grafa(D, n);
         putchar('\n');
         putchar('\n');
         obrabotka(D, n);
         printf ("\n\nДля завершения нажмите любую клавишу\n");
         _getch();
         return 0;
 }

Объяснение кода листинга программы

Ввод и вывод матрицы смежности:
- Ввод матрицы смежности осуществляется с помощью функции vvod_grafa, которая принимает в качестве аргументов матрицу смежности G и количество городов n.
- Вывод матрицы смежности осуществляется с помощью функции vivod_grafa, которая принимает в качестве аргументов матрицу смежности g1 и количество городов n.
Поиск кратчайшего пути:
- Для поиска кратчайшего пути используется алгоритм Дейкстры, реализованный в функции way.
- Алгоритм Дейкстры работает следующим образом:
  1. Инициализация матрицы расстояний D значением 999 для всех городов, кроме диагонали.
  2. Начальное значение расстояния между текущим городом и всеми остальными городами устанавливается равным бесконечности, за исключением диагонали, для которой оно равно 0.
  3. На каждом шаге алгоритма, для каждого города i, выбирается соседний город k, для которого значение D[i][k] минимально.
  4. Если D[i][k] меньше текущего значения D[i][j], то обновляется значение D[i][j].
  5. Если D[i][k] равно текущему значению D[i][j], то перебираются все соседние города j для города k и проверяется, является ли D[i][j] меньше текущего значения D[i][k].
  6. Если условие выполняется, то обновляется значение D[i][j].
  7. После завершения алгоритма, для каждого города выводится кратчайшее расстояние до него.
Проверка наличия города:
- Функция obrabotka проверяет, есть ли в системе дорог город, в который можно попасть из любого другого города, проезжая не более 100 км.
- Если такой город есть, выводится сообщение В город № x можно попасть из любого другого города, проезжая не более 100 км, где x - номер города.
- Если такого города нет, выводится сообщение Такого города нет в данной системе дорог..
Ввод данных и вывод результатов:
- Количество городов вводится с помощью функции scanf_s.
- Ввод матрицы смежности и вывод результатов работы программы осуществляется с помощью функций vvod_grafa, vivod_grafa, way, obrabotka и printf.