0 / 0 / 1
Регистрация: 12.06.2013
Сообщений: 6
1

Найти маршрут с минимальной стоимостью проезда

12.06.2013, 15:45. Показов 2638. Ответов 1
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Имеется N населённых пунктов, пронумерованных от 1 до N. Некоторые пары населенных пунктов соединены дорогами. Известны стоимости проездов по этим дорогам. Определить, можно ли попасть по этим дорогам из первого пункта в N-ный. Если да, то найти маршрут с минимальной стоимостью проезда.
P.S. решается вроде через матрицу
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
12.06.2013, 15:45
Ответы с готовыми решениями:

Можно ли за A рублей купить B книг, стоимостью C и D журналов, стоимостью E?
1. Некто располагает суммой в А руб. Он хочет купить В книг по С руб. и D журналов по Е руб....

Найти вероятность проезда определённой машины по дороге
Здравствуйте.В голове возникла задачка и захотелось узнать ее решение. Суть такова.Есть 1000 машин...

В киоске продается газета стоимостью 3 коп. и журнал стоимостью 20 коп.
В киоске продается газета стоимостью 3 коп. и журнал стоимостью 20 коп. Составить программу, ...

Еж в саду - Найти маршрут
Лес разбит на квадраты и в каждом квадрате находятся яблоки. Еж находится в верхнем левом квадрате...

1
0 / 0 / 1
Регистрация: 12.06.2013
Сообщений: 6
18.06.2013, 18:03  [ТС] 2
Лучший ответ Сообщение было отмечено ritmix93 как решение

Решение

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
program proezd;
 
const
  Max = 5;
 
var
  A: Array[1..Max, 1..Max] Of Integer;
  { *Матрица расстояний между городами. *}
  f: text;
  N: integer;
  B: Array[1..Max, 1..Max] Of Byte;{^Вспомогательный
  массив, элементы каждой строки матрицы
  сортируются в порядке возрастания, но сами
  элементы не переставляются, а изменяются
  в матрице В номера столбцов матрицы А.*}
  Way, BestWay: Array[1..Max] Of Byte;{*Хранится
  текущее решение и лучшее решение. *}
  Nnew: Array[1..Max] Of Boolean;{*3начение
  элемента массива False говорит о том,
  что в соответствующем городе коммивояжер
  уже побывал. *}
  BestCost: Integer;{*Стоимость лучшего решения. *}
 
 
procedure Solve(v, Count: Byte; Cost: Integer);
{*v - номер текущего города; Count - счетчик числа
пройденных городов; Cost - стоимость текущего
решения. *}
var
  i: Integer;
begin
  if Cost > BestCost Then Exit;{*Стоимость текущего
  решения превышает стоимость лучшего из
  ранее полученных. *}
  if Count = N Then begin
    Cost := Cost + A[v, 1];
    Way[N] := v;{*Последний город
    пути. Добавляем к решению стоимость
    перемещения в первый город и сравниваем
    его с лучшим из ранее полученных. *}
    if Cost < BestCost Then begin
      BestCost := Cost;
      BestWay := Way; end;
    Exit;{*Оператор нарушает структурный стиль
    программирования ~ "любой фрагмент логики
    должен иметь одну точку входа и одну точку
    выхода. Следует убрать его" . *}
  end;
  
  Nnew[v] := False;
  Way[Count] := v;{*Город с номером v
  пройден, записываем его номер в путь
  коммивояжера. *}
  for i := 1 To N do
    if Nnew[B[v, i]] Then Solve(B[v, i],
    Count + 1, Cost + A[v, B[v, i]]); {*Поиск города, в который
  коммивояжер может пойти из города,
  с номером v.*}
  Nnew[v] := True; {^Возвращаем город с номером v
  в число непройденных. *}
end;
 
var
  i, j: integer;
 
begin
  assign(f, 'f:\1.txt');
  reset(f);
  i := 1; 
  j := 1;
  while not eof(f) do
  begin
    while not eoln(f) do
    begin
      read(f, a[i, j]);
      inc(j);
    end;
    readln(f);
    inc(i);
  end;
  solve();
  writeln('лучшая цена-', BestCost);
end.
может кто доделать?
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
18.06.2013, 18:03
Помогаю со студенческими работами здесь

Найти кратчайший маршрут
Пожалуйста, помогите!!! Имеется несколько городов, связанных в виде графа. Каждое ребро графа...

Найти оптимальный маршрут
ребят,помогите, в функциях полный ноль,но для универа надо В каждой клетке прямоугольной таблицы...

Найти кратчайший маршрут
Пожалуйста, помогите!!! Имеется несколько городов, связанных в виде графа. Каждое ребро графа...

Найти кратчайший маршрут
Найти кратчайший маршрут, который начинается и завершается в заданной вершине ориентированному...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2023, CyberForum.ru