ac1098.pas

同济大学 Online在线题库 AC源代码合集 程序设计竞赛必看资料

program tju1098;
const
  maxn=100;
  maxm=1000;
var
  v1,v2:array[1..maxm]of byte;
  len:array[1..maxm]of cardinal;
  dist:array[0..maxn]of cardinal;
  v:array[1..maxn]of boolean;
  n,m,i,j,t,x:cardinal;
  b:boolean;
procedure iterate;
  begin
    b:=false;
    for j:=1 to m do
      if v[v1[j]] then begin
        t:=dist[v1[j]]+len[j];
        if t>dist[v2[j]] then begin
          dist[v2[j]]:=t;v[v2[j]]:=true;b:=true;
        end;
      end;
  end;
begin
  dist[0]:=maxlongint;
  repeat
    read(n,m);
    for i:=1 to m do
      read(v1[i],v2[i],len[i]);

    {Shortest path}
    dist[1]:=0;for i:=2 to n do dist[i]:=maxlongint;j:=1;
    fillchar(v,sizeof(v),0);
    while (j<>n) and (j>0) do begin
      v[j]:=true;
      for i:=1 to m do
        if v1[i]=j then begin
          t:=dist[j]+len[i];
          if t<dist[v2[i]] then dist[v2[i]]:=t;
        end;
      j:=0;
      for i:=1 to n do
        if not v[i] and (dist[i]<dist[j]) then j:=i;
    end;
    if j=0 then begin
      writeln('Never');
      writeln('Never');
    end
    else begin
      writeln(dist[n]);
      {Longest path}
      for i:=1 to n do dist[i]:=0;
      fillchar(v,sizeof(v),0);v[1]:=true;
      for i:=1 to n-1 do begin
        iterate;
        if not b then break;
      end;
      if not b then
        writeln(dist[n])
      else begin
        x:=dist[n];
        for i:=1 to n do begin
          iterate;
          if not b then break;
        end;
        if dist[n]>x then writeln('Never') else writeln(x);
      end;
    end;
  until seekeof;
end.