Question

Между населёнными пунктами А, В, С, D, Е, F построены дороги, протяжённость которых приведена в таблице. Определите длину кратчайшего пути между пунктами А и F. Передвигаться можно только по дорогам, протяжённость которых указана в таблице
на фотографии варианты ответов

Answer 1

Ответ:

6

Объяснение:

#include <iostream>

using namespace std;

signed main()

{

   int a,b,c;

   cin >> a >> b >> c;

   b--;

   c--;

   int A[a][a];

   for(int i = 0; i < a; i++)

       for(int j = 0; j < a; j++)

           cin >> A[i][j];

   int d[a];

   bool used[a];

   for(int i = 0; i < a; i++)

   {

       d[i] = 1000000001;

       used[i] = false;

   }

   d[b] = 0;

   int cnt = 0;

   while(cnt != a)

   {

       int w,d_min=1000000001;

       for(int i = 0; i < a; i++)

           if(!used[i] && d[i] < d_min)

           {

               d_min = d[i];

               w = i;

           }

       for(int i = 0; i < a; i++)

           if(A[w][i] != -1 && !used[i] && d[w] + A[w][i] < d[i])

               d[i] =  d[w] + A[w][i];

       used[w] = true;

       cnt++;

   }

   if(d[c] == 1000000001)

       d[c] = -1;

   cout << d[c];

}