风灵无畏OI

【题目描述】

https://codevs.cn/problem/1021/

【题目分析】：

    题目意思是指玛丽卡要从城市A到麦克所在的城市B，在去城市B的道路中，可能会有一条路在堵车（这条路是任意的，不管那条路会堵，题目都保证有一条道路可以从城市A到城市B）那么她将不能走这条路，只能走其他的路。求一个时间，不论那条路受阻，所得到的最短路中所需的时间都会小或于等于这个所求时间。

     这道题目一看就是一道单源最短路的题目，在这里我们可以用两种方法求解，一种是SPFA，一种是Dijkstra算法。在这里，我采用spfa算法。我们可以先用SPFA找出一条最短路出来，然后再依次将这条最短路上的每一条边给删掉，每删一条边之后跑一次SPFA，这样会得到一条次短路。经过多次操作后，会得到多条次最短路，只要将这些次短路中最长的那条的时间输出即可。不过这道题因为要做一个操作，就是删边，那么我们就要将从城市A到城市B的路径给记录下来。

      记录路径:开一个pre数组，在每次松弛边的时候（就是在执行if d[j]+cost[k]<d[i] then d[i]:=d[j]+cost[k]的时候），这时如果d[i]被更新了，就将pre[i]:=j,表示当前到i点的最短路径中，j是i的前驱结点。在做完spfa时，对于结点i,不断地i:=pre[i]直到i=源点，这途中的点即为路径。

【程序代码】：

type  arr=record

       co,nd,nx:longint;

      end;

var a,b,v,tot,x,n,m,i,j,ans,u,t,w:longint;

    hash:array[1..10000000]of longint;

    dist,p,pre:array[1..1000000]of longint;

    f:array[1..1000000]of boolean;

    bot:array[1..1000000]of arr;

procedure add(a,b,c:longint);

begin

  inc(tot);

  bot[tot].nd:=b;

  bot[tot].nx:=hash[a];

  bot[tot].co:=c;

  hash[a]:=tot;

end;//这里用到了邻接链表，自己可以上网查查

       //这里提供在网上找到的SPFA（用邻接链表存储边）讲解很好的文章：

https://www.360doc.com/content/13/1208/22/14357424_335569176.shtml

//https://blog.csdn.net/morgan_xww/article/details/6279596

procedure scanf;

begin

  readln(n,m);

  for i:=1 to m do

   begin

     readln(a,b,v);

     add(a,b,v);

     add(b,a,v);

   end;//读入操作，存双向边

end;

procedure spfa(s:longint);

var l,h:longint;

begin

  fillchar(f,sizeof(f),true);

  filldword(dist,sizeof(dist)div 4,214748364);

  dist[s]:=0; l:=1; h:=0; f[s]:=false; p[l]:=s;

  while h<>l do

   begin

     h:=h+1;

     x:=p[h];

     v:=hash[x];

     while v<>0 do

      begin

        if dist[bot[v].nd]>dist[x]+bot[v].co then

           //这里相当于if d[j]+cost[k]<d[i] then d[i]:=d[j]+cost[k]，只是因为我是用邻接链表存的，所以要这样做，（你也可以不用邻接链表，不过下面的某些代码，可能就要你自己码了）

        begin

          dist[bot[v].nd]:=dist[x]+bot[v].co;//这里是更新值

          pre[bot[v].nd]:=x;//这里是题目分析中提到的存路径的方法

          if f[bot[v].nd] then

           begin

             l:=l+1;

             f[bot[v].nd]:=false;

             p[l]:=bot[v].nd;

           end;

        end;

        v:=bot[v].nx;

      end;

     f[x]:=true;

   end;

end;

begin

  scanf;

  spfa(1);

  i:=n; j:=pre[i];

   repeat

      j:=pre[i];//这里和后面的i:=j，则是为了去找路径（因为路径存下来了所以直接找就是的啦）

      u:=hash[i];

      while bot[u].nd<>j do u:=bot[u].nx;

      t:=bot[u].co; bot[u].co:=214748364;//t是存原来这条边的值，在删边之后恢复时有用处

      w:=hash[j];

      while bot[w].nd<>i do w:=bot[w].nx;

      bot[w].co:=214748364;//这一段程序是用来找边的，因为在pre数组里的下标和数组里的值是指某一条个点连着另一个点，所以用while循环来查找这条边，并将他删掉。

      spfa(1);

      if ans<dist[n] then ans:=dist[n];//这里则是比较下在这些找到的次短路中，找到一条最大的

      bot[u].co:=t; bot[w].co:=t;//因为之前将这条边删掉了，所以现在将它复原，因为题目中所说这些路中，只会有一条会堵

      i:=j;

   until i=1;

  writeln(ans);

end.