Недочет программы

[dimon_snake]

Здравствуйте. Нужна помощь, отредактировать, улучшить программу.
Даны города, дороги, которые их связывают и нужный город.
Мы появляемся в первом городе, и должны достичь нужного города.
Во входном файле :
В первой строке три цифры
n, m, k
n - кол-во городов
m - кол-во пар дорог
k - нужный город
вторая строка содержит n чисел - налоги в каждом городе.
третья строка содержит m пар чисел - дороги, которые связывают города
(например, m = 2, тогда в третьей строке будет 1 2 3 2, значит, есть дорога между 1 и 2 городом, и между 3 и 2)
Нужно пройти самым дешевым путем к нужному городу
Если нельзя добраться туда, то вывести -1.

type road=record  \\для чтения третьей строки, два соединенных города
g1:integer;
g2:integer;
end;
var
n,m,k,x,i,l,nal,gor,v,j,u,h,b,prg:integer;
a,otv:array[1..100] of integer; \\массив a для налогов городов, и otv для возможных ответов
roads:array[1..100] of road; \\массив дорог
fi,fo:text;
bh:boolean;
begin
Assign(fi,'andrew.in');\\вход файл
Assign(fo,'andrew.out');\\выход файл
Reset(fi);
Rewrite(fo);
Read(fi,n,m,k);\\читаем кол-во городов, кол-во пар дорог, нужный город
REadln(fi);
for i:=1 to n do
Read(fi,a[i]); \\считываем в массив налоги городов
Readln(fi);
for i:=1 to m do
begin
  Read(fi,roads[i].g1);
  Read(fi,roads[i].g2);\\записываем в массив соединённые города
end;
x:=1;
for v:=1 to n do
begin
  gor:=1; \\текущий город - 1
  nal:=a[1]; \\ налог из 1 города 
  for i:=1 to n do
  begin
    bh := false;
    if ((roads[i].g1 <> gor) and (roads[i].g2 <> gor)) then\\если в i-том элементе массива нет города, который соединяется с текущим
    begin
      for j:=1 to n do\\начнем проверку, есть ли таковой вообще 
      begin
        if (roads[j].g1 = gor) then \\если мы нашли совпадение 
        begin
          u := j;
          for b:=1 to n do \\ тогда проверяем, есть ли у соседа нужного нам города еще соединения (например, пары дорог 1 2 3 1 4 2 3 4, смотрим на дороги с текущим городом, а потом проверяем, есть ли у него соседа  еще соединения 
          begin
            if (roads[b].g1 = roads[u].g2) and (b <> u) and (roads[u].g2 <> prg) then
            begin
              bh:=true;\\вспомогательная переменная
              break;
            end;
            if (roads[b].g2 = roads[u].g2) and (b <> u) and (roads[u].g2 <> prg) \\prg - предыдущий город, что бы мы не вернулись назадthen
            begin
              bh:=true;
              break;
            end;
            if (b = n) then \\ если мы так и не нашли соединений у соседа текущего города, уничтожаем эту дорогу
            begin
              roads[u].g1 := 0;
              roads[u].g2 := 0;
              bh := true;
            end;
          end;
        end;
        if bh = true then break;
        if (roads[j].g2 = gor) then \\ то же, что и в предыдущем цикле, только теперь текущий город будет в roads[j].g2, а не в g1
        begin
          u := j;
          for b:=1 to n do
          begin
            if (roads[b].g1 = roads[u].g1) and (b <> u) and (roads[u].g1 <> prg) then
            begin
              bh:=true;
              break;
            end;
            if (roads[b].g2 = roads[u].g1) and (b <> u) and (roads[u].g1 <> prg) then
            begin
              bh:=true;
              break;
            end;
            if (b = n) then
            begin
              roads[u].g1 := 0;
              roads[u].g2 := 0;
            end;
          end;
        end;
        if bh = true then break; \\ если у города таки нашлись соединения, выходим из цикла
      end;
    end;
    if ((roads[i].g1 = gor) and (roads[i].g2 = k)) or ((roads[i].g2 = gor) and (roads[i].g1 = k)) then \\ если текущий город имеет соединения с нужным
    begin
      nal := nal + a[k]; \\ добавляем налог нужного города
      roads[i].g1 := 0;\\уничтожаем дороги, что бы опять не ходит по ним
      roads[i].g2 := 0;
      break;
    end;
    if (roads[i].g1 = gor) then \\ если находим дорогу с нашего городу
    begin
      prg := gor; \\записываем предыдущий город
      gor := roads[i].g2; \\ переезжаем в след. город
      nal := nal + a[gor]; \\добавляем его налог
    end
    else if (roads[i].g2 = gor) then \\так само, если  наш город в g2
    begin
      prg := gor;
      gor := roads[i].g1;
      nal := nal + a[gor];
    end;
    if (i = n) and (gor <> k) \\если за все время так и не дошли до нужного города
    then nal := -1; \\кидаем -1
  end;
  otv[x] := nal;\\записываем в массив налог
  Inc(x);
end;
nal := otv[1];
for i:=1 to n do
if (otv[i] < nal) and (otv[i] > 0)\\находим самый дешевый способ
then nal := otv[i];
Write(fo, nal); \\выводим
Close(fo);
end.

Программа работает лишь на 30 б. из 100, не знаю, почему

[FPaul]

Алгоритм Дейкстры.

[dimon_snake]

Нашел, изменил под свою программу:

const
max = 2000;
type
trebro = record
adrs,ves:word;
end;
tarrreb = array[1..100]of trebro;
tver = record
name,metka,numr:word;
visit:boolean;
reb:tarrreb;
end;
road = record
g1,g2:integer;
end;
var
graf:array[1..100] of tver;
a,nums:array[1..100] of integer;
roads : array [1..100]of road;
z,j,n,m,k,x:integer;
fi,fo:text;
function searchminver(var imin:word):boolean;
var i:word;
begin
  searchminver:=false;
  imin:=0;
  i:=1;
  while graf[i].visit and (i<=n) do inc(i);
  if i>n then exit 
  else imin := i;
  for i:=1 to n do 
  begin
    if not graf[i].visit and(graf[i].metka < graf[imin].metka)
    then imin := i;
  end;
  searchminver:=true;
end;
procedure posesenie(a:word);
var i,v:word;
begin
  for i:=1 to graf[a].numr do 
  begin
    v:=graf[a].metka + graf[a].reb[i].ves;
    if not graf[graf[a].reb[i].adrs].visit and (v< graf[graf[a].reb[i].adrs].metka) then
    graf[graf[a].reb[i].adrs].metka:=v;
    graf[a].visit:=true;
  end;
end;
var c:word;
begin
Assign(fi,'andrew.in');
Reset(fi);
Read(fi,n,m,k);
Readln(fi);
for z:=1 to n do Read(fi,a[z]);
Readln(fi);
for z:=1 to n do 
begin
  Read(fi,roads[z].g1);
  Read(fi,roads[z].g2);
end;
for z:=1 to n do 
begin
  x:=0;
  for j:=1 to n do 
  begin
    if (roads[j].g1= z) or (roads[j].g2 = z)
    then  inc(x);
    if j=n then nums[z]:=x;
  end;
end;
for z:=1 to n do
begin
  x:=1;
  graf[z].name := z;
  graf[z].metka :=max;
  graf[z].numr := nums[z];
  graf[z].visit := false;
  for j:=1 to n do
    begin
      if roads[j].g1 = z then 
      begin
        graf[z].reb[x].adrs := roads[j].g2;
        graf[z].reb[x].ves := a[roads[j].g2];
        Inc(x);
      end;
      if roads[j].g2 = z then 
      begin
        graf[z].reb[x].adrs := roads[j].g1;
        graf[z].reb[x].ves := a[roads[j].g1];
        Inc(x);
      end;
    end;
end;
Assign(fo,'andrew.out');
Rewrite(fo);
graf[1].metka := 0;
while searchminver(c) do posesenie(c);
Write(fo,graf[k].metka+a[1]);
close(fo);
end.

Но у меня опять неполное решение с неё, и где-то идет зацикливание программы.

[FPaul]

Алгоритм Дейкстры детерминированный и выполняется пропорционально V^2, где V - количество вершин (городов). Он не может зацикливаться в принципе.
Но раз зацикливается - приводите и исходные данные.
А кроме того - пройдитесь пошаговым отладчиком.

[dimon_snake]

Он у меня зацикливается, пока не выключу программу.
Например:
4 2 4
1 5 3 1
1 2 3 1

[FPaul]

Выбрасывайте этот код. Оставьте только ввод.

Задача похожа на ту, что решается алгоритмом Дейкстры, но всё же не она. Тут я погорячился.

Решением будет модификация алгоритма Дейкстры, т.к. здесь стоимость не дороги, а посещения города. Результат - как в алгоритме Дейкстры - массив D[i] минимальной итоговой стоимости пути из 1 города в i, и массив P[i] массив предков для восстановления пути.

В вашем коде не видно ни D ни P. Отсюда и невозможность решения - нет реализации алгоритма.

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

[Poma][a]

Ну вот почему везде Дейкстра?
Для невзвешенного графа прекраснор работает bfs.

А по коду ТС все же Дейкстра. А по условию ТС bfs. Кому верить?

[FPaul]

Думаю, что нужен всё-таки Дейкстра, вернее вариация на тему. Т.к. получается что взвешенное прохождение через города, а не по дорогам. Чисто теоретически, возможен случай, когда пройти через 10 промежуточных городов дешевле чем через 1 промежуточный. Хотя, если есть прямой путь от 1 к k - то это сразу решение.

А чистый BFS в результате даст лишь невзвешенное отдаление от 1-го города.
Тем более, что Дейкстра - это и есть развитие BFS.
---------------------------------
А в коде ТС почему-то не разглядел Дейкстру... Особенно, потому, что ожидаемый результат - массив стоимостей путей и массив восстановления пути.

[Poma][a]

Утром не увидел строчку с налогами. Каюсь. Грешен. Дейкстру в массы

У ТС вообще нечто. Если это Дейкстра. То он ужасен. Если Форд - то тем более

[dimon_snake]

Изменил, сделал алгоритмом Дейкстры. Сделал так:
если есть дорога из второго города в третий, то есть 2 3, то вес её будет равен налогу третьего города, а вес с 3 2 - весу второго города.
Программа почти полностью работает. однако что-то она еще не выполняет, пишет, что неверный ответ.
Помогите найти ошибку:

const
max = 2000;\\бесконечность
type
road = record
g1,g2:integer;\\дороги, связанные между собой города
end;
vektor = array[1..100] of integer;
vek = array[1..100,1..100] of integer;\\матрица
var
a:array[1..100] of integer;
roads : array [1..100]of road;
gr:array[1..100,1..100] of integer;
z,j,n,m,k,x,results:integer;
fi,fo:text;
c:word;
procedure Dik(gr:vek;st:integer);
var count,index,i,u,m,min:integer;
distance:vektor;
visited:array[1..100] of boolean;
begin
  m:=st;
  for i:=1 to n do
  begin
    distance[i]:=max;
    visited[i]:=false;
  end;
  distance[st]:=0;
  for count:=1 to n-1 do
  begin
    min:=max;
    for i:=1 to n do
    if(not visited[i]) and(distance[i]<=min) then
    begin
      min:=distance[i];
      index:=i;
    end;
    u:=index;
    visited[u]:=true;
    for i:=1 to n do
    if(not visited[i]) and (gr[u,i] <>0) and (distance[u]<>max) and(distance[u]+gr[u,i] < distance[i]) then
    distance[i]:=distance[u]+gr[u,i];
  end;
  if distance[i]<>max then
  results := distance[k]
  else results:=-1;
end;
begin
Assign(fi,'andrew.in');
Reset(fi);
Read(fi,n,m,k);\\читаем из файла кол-во городов, пар дорог, и нужный город
Readln(fi);
for z:=1 to n do Read(fi,a[z]); \\ налоги городов
Readln(fi);
for z:=1 to m do \\ связи между городами
begin
  Read(fi,roads[z].g1);
  Read(fi,roads[z].g2);
end;
for z:=1 to n do
  for j:=1 to n do
    gr[z,j]:=0;\\заполняем матрицу нулями 
for z:=1 to n do
  for j:=1 to m do\\заполняем матрицу числами, весами дорог
  begin
    if (roads[j].g1 = z) then
    gr[z,roads[j].g2]:=a[roads[j].g2]
    else if (roads[j].g2 = z) then
    gr[z,roads[j].g1]:=a[roads[j].g1]
  end;
Assign(fo,'andrew.out');
Rewrite(fo);
Dik(gr,1);\\процедура алгоритма дейкстры
if results = -1 then Write(fo,-1) \\если -1, то вывести -1
else
Write(fo,results+a[1]); \\ иначе вывести результат + налог первого города, т.к. он изначально не считался
Close(fo);
end.

80 из 100, не знаю, из-за чего.