Поиск кратчайшего пути с условием

@Андрей1992 · Регистрация: 13.06.2012

Author24 — интернет-сервис помощи студентам

Дан ориентированный граф, задаётся количеством вершин - m и рёбер- n, списком рёбер.
Необходимо найти кратчайший путь из вершины t в s, с условием: если их несколько вывести тот путь в котором максимальное ребро минимально. Вывести максимальное ребро входящее в путь.
Например:
3 3
1 2 1
2 3 2
1 3 3
1 3
Вывод: 1 2 3
2
Пояснение: в пути 1-2-3 максимальное ребро -2, а в пути 1-3 - максимальное ребро 3.
Как ни пробовал для всех случаев не получается написать правильное решение.
м.б. поможет - обычный алгоритм Дейкстры.

Pascal

const
  maxn = 100;
  infinity = maxlongint;
var
  i,j,u,v,n,m,c,min,s,t:longint;
  e,w:array[1..maxn,1..maxn]of longint;
  ne,use,p,d:array[1..maxn]of longint;
begin
  read(n,m,t,s);
  for i:=1 to m do begin
    read(u,v,c);
    inc(ne[v]); e[v,ne[v]]:=u;
    w[v,u]:=c;
  end;
  for i:=1 to n do d[i]:=infinity;
  d[s]:=0;
  for i:=1 to n do begin
    min:=infinity;
    for j:=1 to n do if (use[j]=0)and(d[j]<min) then begin
      min:=d[j]; u:=j;
    end;
    use[u]:=1;
    for j:=1 to ne[u] do begin
      v:=e[u,j];
      if d[v]>d[u]+w[u,v] then begin
        d[v]:=d[u]+w[u,v]; p[v]:=u;
      end;
    end;
  end;
  writeln(d[t]);
  u:=t; write(u);
  while u<>s do begin
    u:=p[u]; write(' ',u);
  end;
end.

	29.01.2013, 23:59

Опции темы