Решение задачи на вычисление количества бензина для проезда между несколькими городами, страница 4

          i-ый j-ый элемент массива А это стоимость проезда из города i в город j.

          Если сумма меньше (т.е. цена меньше), то j-ому элементу массива D присваиваем сумму.*/

          do

          {

               for(i=1;i<N;i++)

               {

                    for(j=1;j<N;j++)

                    {

                         if (C[i][j]!=10000)

                         {

                              if(C[i][j]+D[i]<D[j])

                                   D[j]=C[i][j]+D[i];

                         }

                    }

               }

               e++;

          }

          while (e<N);

          return D[N-1];

     }

}

7. Набор тестов

Примечание: в вершинах графа задана стоимость бензина в этом городе.

Тест 1

Назначение: Система дорог пуста

Входные данные:

1

Результат:

-1

Примечание: Так как в условии сказано что нет дорог, ведущих из города в себя, то выдаем ответ -1, то есть добраться не возможно.

Тест 2

Назначение: тривиальный вариант непустой системы дорог и первый с последним городом соеденены прямой дорогой.

Входные данные:

5

2 4 1 3 5                                                            1

6                                                                                                    

1 3                                                                                                  3

1 4

1 5

4 2                                                          2

4 5                                                                                                 4

4 3

                                                                                 5

Результат:

2

Тест 3

Назначение:  тривиальный вариант непустой системы дороги и первый с последним городом не соединены прямой дорогой. Существует более одного пути.

Входные данные:                                           1

5

2 7 5 4 3                                                                                     2

5                                                   3

1 2

1 4

2 3

3 5                                               5                                4

4 5                                                       

Результат:

6

Тест 4

Назначение: непустая система дорог, существует более одного самого дешового пути до последнего города.

Входные данные:

4                                                                                       1

0 2 2 4

4                                                                   3

1 2

1 3                                                                                                   2

4 2

4 3

                                                                                    4

Тест 5

Назначение: непустая система дорог, доехать до последнего города невозможно.

Входные данные:                                                             1

6

2 1 0 9 4 3                                      6                                                                       2

4

1 2                                                                            3

1 4

3 2                                                                                                         4

6 5

                                                                    5      

Результат:

-1

8. Результаты работы программы

Программа работает правильно, что подтверждается результатами тестов.

9. Литература

1) В.П. Хиценко, Т.А. Шапошникова «Структуры данных и алгоритмы. Методические указания» - Новосибирск 2008

2) В.П. Хиценко, Т.А. Шапошникова «Практикум на ЭВМ. Алгоритмы» - Новосибирск 2004

3) Т.А. Павловская «C/C++.  Программирование на языке высокого уровня»