Форум программистов
 
О проблемах, например, с регистрацией пишите сюда - alarforum@yandex.ru, проверяйте папку спам! Обязательно пройдите активизацию e-mail, а тут можно восстановить пароль.

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Здесь нужно купить рекламу за 20 тыс руб в месяц! ) пишите сюда - alarforum@yandex.ru
Без учёта ботов - 20000 человек в день, 350000 в месяц.

Ответ
 
Опции темы
Старый 06.01.2010, 20:14   #1
pum-pum-pum
Новичок
Джуниор
 
Регистрация: 06.01.2010
Сообщений: 2
По умолчанию кратчайшие расстояния между вершинами

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

вот моя программа...

const
maxn = 200000;

const
queue_size = maxn;

type
item = integer;

queue = record
a: array [0..queue_size] of item;
head, tail: integer;
end;

var
p,head,next,too: array [1..maxn] of integer;
q: queue;
visited: array [1..maxn] of boolean;
i,n,o,po: integer;
nn,u,v: integer;

procedure init_queue(var q: queue);
begin
q.head := 0;
q.tail := 0;
end;

procedure push_to_queue(var q: queue; x: item);
begin
with q do
begin
a[tail] := x;
tail := (tail + 1) mod queue_size;
end;
end;

function pop_from_queue(var q: queue): item;
begin
with q do
begin
pop_from_queue := a[head];
head := (head + 1) mod queue_size;
end;
end;

function is_queue_empty(const q: queue): boolean;
begin
is_queue_empty := q.head = q.tail;
end;

function get_queue_top(const q: queue): item;
begin
get_queue_top := q.a[q.head];
end;



procedure bfs(v: longint);
begin
init_queue(q);
push_to_queue(q, v);
p[v] := 0;
visited[v] := true;

while not is_queue_empty(q) do
begin
v := pop_from_queue(q);
po:=head[v];
while po>0 do
begin
o:=too[po];
if not visited[o] then
begin
p[o] := v;
visited[o] := true;
push_to_queue(q, o);
end;
po:=next[po];
end;
end;
end;


procedure print_path(x, y: longint);
begin
if x <> y then
print_path(x, p[y]);
write(y, ' ');
end;



begin
fillchar(p, sizeof(p), 0);
fillchar(visited, sizeof(visited), false);
reset(input, '1.txt'); rewrite(output,'2.txt');

read(n);
read(nn);

fillchar(head, sizeof(head), 0);
i:=1;
while i <= 2*nn do
begin
read(u, v);
next[i] := head[u];
too[i] := v;
head[u]:= i;
inc(i);

next[i] := head[v];
too[i] := u;
head[v]:= i;
inc(i);
end;

for i := 1 to n do
if not visited[i] then bfs(i);

writeln('breath-first search (shortest path)');

for i := 1 to n do
begin
write('[', 1, '->', i, '] ');
print_path(1, i);
writeln;
end;
end.
pum-pum-pum вне форума Ответить с цитированием
Старый 07.01.2010, 12:30   #2
pum-pum-pum
Новичок
Джуниор
 
Регистрация: 06.01.2010
Сообщений: 2
По умолчанию

неужели мне никто не может помочь?((((
pum-pum-pum вне форума Ответить с цитированием
Ответ

Здесь нужно купить рекламу за 20 тыс руб в месяц! ) пишите сюда - alarforum@yandex.ru
Без учёта ботов - 20000 человек в день, 350000 в месяц.

Опции темы


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Задача в Exel (стоимость билета в зависимости от расстояния) Phill Помощь студентам 9 30.11.2010 01:20
Кратчайшее расстояние между всеми вершинами ooooch Помощь студентам 5 15.11.2009 16:36
Поиск минимального расстояния от точки до ломанной на сфере. Язык Си silent_1991 Помощь студентам 3 09.11.2009 14:50
C++ количество бинарных деревьев с n ( 1 n 1000) вершинами. fedia Помощь студентам 0 08.10.2009 18:14
Уменьшение расстояния между элементами в CSS CoDaJJe HTML и CSS 0 28.08.2009 00:12


Проекты отопления, пеллетные котлы, бойлеры, радиаторы
интернет магазин respective.ru
Пеллетный котёл Emtas
котлы EMTAS