Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 15.11.2006, 22:00
Ajdyn

 
Сообщений: n/a

задача "путь к пьяной берлоге" с гранпри сибири.
условия здесь должны быть: http://www.opencup.ru/files/oc3/gp3/oc3gp3.doc
Решал алгоритмом дейкстры. Не проходит 6ой тест, хрен знает почему вроде все правильно. вот код

может поможет кто подскажет в чем ошибка. Спасибо.

{$apptype console}
uses
SysUtils, Math;
const
infile = 'input.txt';
outfile = 'output.txt';
maxn = 2000;
inf = 100000000;
type
tarr = array[0..maxn] of integer;
t2darr = array[0..maxn,0..maxn] of integer;
var
s,v,n: integer;
c: t2darr;
f,d: tarr;
m: integer;
si: tarr;
procedure init;
var
i,j: integer;
ts,tc: integer;
nd: integer;
tmp: extended;
begin
readln(s,tmp,v,n);
m := trunc(tmp * 100);
v := v * 100;

for i := 0 to s do
for j := 0 to s do
c[i,j] := inf;
for i := 0 to s-1 do
si[i] := inf;
si[s] := 0;

for i := 1 to n do begin
readln(ts,tc);
si[ts] := min(si[ts],tc);
end;

for i := 0 to s-1 do
for j := i+1 to s do
if (si[i] <> inf) and (si[j] <> inf) then begin
nd := (j-i)*m;
if nd <= v then begin
c[i,j] := si[i] * nd;
end;
end;
end;

procedure dij(var c:t2darr; var d,f: tarr; start,finish: integer);
var
i,j,k: integer;
min: integer;
begin
for i := 0 to s do begin
d[i] := c[start,i];
f[i] := 0;
end;
d[start] := 0;
f[start] := 1;
k := start;
for i := 0 to s-1 do begin
min := inf;
for j := 0 to s do
if (f[j] = 0) and (min > d[j]) then begin
min := d[j];
k := j;
end;
f[k] := 1;
for j := 0 to s do
if (f[j]=0) and (d[j] > d[k]+c[k,j]) then
d[j] := d[k]+c[k,j];
end;
end;

procedure run;
begin
dij(c,d,f,0,s);
end;

procedure writedata;
begin
write(d[s] div 100);
if d[s] mod 100 = 0 then
exit;
if (d[s] mod 100 < 10) then
write('.0')
else
write('.');
writeln(d[s] mod 100);
end;

begin
assign(input, infile);
assign(output, outfile);
reset(input);
rewrite(output);
init;
run;
writedata;
close(input);
close(output);
end.
  #2  
Старый 16.11.2006, 07:47
Пользователь

Отправить личное сообщение для AndreySUrSU Посмотреть профиль Найти все сообщения от AndreySUrSU
 
Регистрация: 06.10.2006
Адрес: Челябинск
Сообщений: 66

Какая тут идея дейкстры? Почему он должен вообще проходить?
До каждой остановки доходим жадно, с минимальными затратами?
Тут точно проходит динамика, без жадностей таких.
Тут объем небольшой, поэтому можно постоить матрицу N*M.
a[i][j] - i - остановка, j - кол-во бензина(сена).
ну и
a[i][j] = min(a[i-1][j+1], a[i][j-1]+c)
Типа вот такого, те либо пришли с предыдущей станции потратив бензин, либо пришли в тек состояние с текущей станции, просто купив минимально возможный бензин.
  #3  
Старый 17.11.2006, 16:30
незарегистрированный

 
Сообщений: n/a

Сообщение от AndreySUrSU Посмотреть сообщение
Какая тут идея дейкстры? Почему он должен вообще проходить?
Идея дейкстры была следующая: т.к. максимальное расстояние может быть 2000, а городов может быть до 10^7 то оставляем для каждого расстояния от 0 до 2000 только те города стоимость корма в которых минимальна. Если города нет на каком то расстоянии то считаем что стоимость корма равна бесконечности. Далее по полученному массиву
si[0..2000] строим граф, следующим образом:
пусть надо выяснить должно ли быть ребро между i ым и j ым городом (j > i), стоимость проезда между i,j будет равна (j-i)*m*c[i], где c[i] стоимость килограмма корма, m сколько нужно корма на один километр. Если (j-i)*m*c[i] > v то ребра i->j нет т.к. столько корма с собой всадник взять не может. Иначе создаем ребро i->j, вес которого равен (j-i)*m*c[i]. После того как граф построен, и т.к. мы знаем сколько стоит поехать из любого города в другой, то находим дейкстрой минимальный путь.

Я просто немного не разбираюсь в жадных алгоритмах, но это тоже кажется жадный. Но если подумать то он должен работать.
  #4  
Старый 18.11.2006, 10:16
Пользователь

Отправить личное сообщение для AndreySUrSU Посмотреть профиль Найти все сообщения от AndreySUrSU
 
Регистрация: 06.10.2006
Адрес: Челябинск
Сообщений: 66

ну это неправильно.
можно ведь запасать корм. тут это никак не учитывается.
динамикой нужно решать. как я и писал. рассматриваем состояние, в него можно прийти, либо купив мин кол-во корма(если это можно сделать), либо из предыдущего города. (в нек городах может и не быть заправок)
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
задача "быки и коровы" незарегистрированный Оффтопик 3 07.06.2008 16:59
игра "ним" Guest Задачи 2 23.04.2007 13:59
максимальный поток\ "задача о ресурсах" ExPerT Реализация, исходники, языки 0 27.03.2007 14:08
"очень" простые циклы cmd Графы 0 10.12.2006 00:38
просьба создать раздел форума с названием "графы" CD_Eater Замечания о работе сайта 1 22.09.2006 10:56