题解 P1807 【最长路_NOI导刊2010提高（07）】

· · 题解

Pascal的SPFA竟然没有？！我来补一发

其实这题是个很裸很裸的比最短路模板还要裸的“最长路”啦！我用了SPFA算法，把松弛操作的符号改一下就行了，然后把极大值改成极小值，就这样AC了！本来以为需要考虑很多东西......

然而楼下的大佬们都用的是那种非指针伪链表的形式存的边，我这个蒟蒻只会用数组模拟邻接表......也是一种方法嘛，为我这种蒟蒻准备的。

献上我那丑陋的代码：

var
  n,m,i,j,h,t,x,y,z,oo:longint;
  a,c:array[0..2000,0..5000]of longint;
  dis:array[0..2000]of longint;
  b:array[0..2000]of boolean;
  q:array[0..5000000]of longint;
procedure spfa();
var
  i:longint;
begin
  for i:=1 to n do
    begin dis[i]:=oo; b[i]:=false; end;
  h:=0; t:=1; q[t]:=1; dis[1]:=0; b[1]:=true; //起点入队列
  while h<t do 
    begin
      inc(h); x:=q[h]; b[x]:=false;
      for i:=1 to a[x,0] do 
        begin
          y:=a[x,i];
          if dis[x]+c[x,i]<dis[y] then continue; //求的是最长路，那么如果小于，就不用更新，直接continue
          dis[y]:=c[x,i]+dis[x]; //更新
          if b[y] then continue; //已经在队列中了就continue
          inc(t); q[t]:=y; b[y]:=true; //加入队列
        end;
    end;
end;
begin
  oo:=maxlongint shr 2*(-1); //极小值
  readln(n,m);
  for i:=1 to n do 
    for j:=1 to n do 
      c[i,j]:=oo; //c数组对应a数组，存储权值，数组模拟邻接表
  for i:=1 to m do 
    begin
      readln(x,y,z);
      inc(a[x,0]); a[x,a[x,0]]:=y; c[x,a[x,0]]:=z; //a[x,0]存储出度
    end;
  spfa();
  if dis[n]=oo then write(-1) else write(dis[n]); //走不到输出-1
end.