Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > Delphi программирование > Паскаль, Turbo Pascal, PascalABC.NET
Регистрация

Восстановить пароль

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 19.12.2011, 22:33   #1
Katrina*
Пользователь
 
Регистрация: 19.12.2011
Сообщений: 29
Вопрос Задача про города

В государстве N городов. Курьер должен добраться из города А в город В. Вам известно, между какими городами есть дороги. Найдите такой путь из А в В, который проходит через наименьшее количество городов. Гарантируется, что путь существует.

Последний раз редактировалось Katrina*; 20.12.2011 в 07:24.
Katrina* вне форума Ответить с цитированием
Старый 20.12.2011, 01:25   #2
val_nnm
Форумчанин
 
Регистрация: 18.10.2009
Сообщений: 185
По умолчанию

Держите написал (хотя не исключено что такая задача уже решалась на этом форуме, просто лень искать)

Код:
const MaxM = 50;
Type Citys = set of byte;
Type Way = record
             fromC:byte;
             toC:byte;
           end;
var N:integer;
    M:integer;
    A:byte;
    B:byte;
    input:text;
    output:text;
    i:integer;
    Ways:array[1..MaxM] of Way;
    C:Citys;
    C2:Citys;
    C3:Citys;
    l:integer;
    
Begin
  assign(input,'input.txt');
  reset(input);
  readln(input,N,M,A,B);
  for i := 1 to M do
    readln(input,Ways[i].fromC,Ways[i].toC);
  close(input);
  l := -1;
  C := [A];
  C2 := [A];
  while not(B in C2) and (C2 <> []) do Begin
    C3 := [];
    for i := 1 to M do Begin
      if (Ways[i].fromC in C2) then
        include(C3,Ways[i].toC);

      if (Ways[i].toC in C2) then { второе условие. т.к. по дороге можно перемещяться в обоих направлениях }
        include(C3,Ways[i].fromC);
    end;
    C2 := C3 - C;
    C := C + C3;
    l := l+1;
    if (C2 = []) then l := -2; { ответа нет }
  end;
  assign(output,'output.txt');
  rewrite(output);
  writeln(output,l);
  close(output);  
end.
p.s. Погоняйте хорошенько на разных данных, потому что могут быть ошибки.
На С# пишу лучше чем на русском.
"У меня правильнописание хромает. Оно хорошее, но почему-то хромает."

Последний раз редактировалось val_nnm; 20.12.2011 в 01:44.
val_nnm вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц



Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Задача: Города m1st Общие вопросы по Java, Java SE, Kotlin 4 27.09.2010 15:30
Задача про массивы Max_Grinyuk Помощь студентам 22 21.05.2009 23:05
Задача про 3 прямые meds Паскаль, Turbo Pascal, PascalABC.NET 5 17.11.2008 12:24
Задача про треугольник YO$YA Помощь студентам 10 15.11.2008 20:29