黑猫派对

【问题描述】

黑猫搬家到了狂气之城---千叶，在凶介的鼓励下，她交到了很多很多好朋友，这天，大家决定聚到一起，到某个人家里去玩，黑猫的朋友（包括她自己）有 N 个人，他们决定一起到被编号为 X 的朋友家里去，大家都住在不同的地方，被很多条单向道路连接着，大家都会选择最短路径到达目的地和回家，现在黑猫手上拿着一份地图，标记着所有人的位置以及道路长度，她想知道前去聚会的人中，到达目的地之后又回家要走的距离最长的那个人要走多长的距离？

【输入】

第一行有三个整数 N，M，X。

第2~m+1 行：a,b,c，表示有一条从 a到b的路，长度为c(<=1000000)。

【输出】

一个数ans，距离X最长的那个人要走多长的距离。

【输入输出样例】

party.in

party.out

4 8 2

1 2 4

1 3 2

1 4 7

2 1 1

2 3 5

3 1 2

3 4 4

4 2 3

【数据范围限制】

30%的数据，满足 N<=1000，M<=100000

100%的数据，满足 N<=10000，M<=1000000，1<=X<=N 。

有可能有通往自己家的单向道路（自环），和多条通往一个地方的单向道路（重边）

题目解析：

从题目可以看出需要做两次单源最短路径，一次正向，一次反向（即将所有的边反过来即可）。

dij,O(N2)明显超时。

spfa,O(Ke)，在平均情况下K是常数，应该没问题。

此题注意数组的大小，要开足够大。

//注意数组空间一定要开的足够大，这是spfa错误的主要原因。
const
  maxn=210000;
  maxm=2100000;
  fin='party.in'; fout='party.out';
var
   n,m,tot,tot2,i,start:longint;
   q,list,list2,d,d2:array[1..maxn] of longint; //list存储当前边的指针,d存储各点到源点的最短路
   next,next2,toit,toit2,cost2,cost:array[1..maxm] of longint;//next存储当前边指向前一条边的位置，toit表示当前边的出点，cost表示当前边的边权
   f:array[1..maxn] of boolean;
   head,tail:longint;
   procedure makelist(x,y,w:longint);////数组模拟链表的添边的方法
   begin
     inc(tot);////边的数目
     toit[tot]:=y;//当前边的出点顶点标号
     cost[tot]:=w;//当前边的权值?
     next[tot]:=list[x];////当前边指向前一条边的位置，如果当前边是顶点x的读入的第一条边，则它指向前面第0条边，表示next[tot]:=0
     list[x]:=tot;//从入点x引出的边的编号存储给lsit[x]
   end;
   procedure makelist2(x,y,w:longint);////数组模拟链表的添边的方法
   begin
     inc(tot2);////边的数目
     toit2[tot2]:=y;//当前边的出点顶点标号
     cost2[tot2]:=w;//当前边的权值?
     next2[tot2]:=list2[x];////当前边指向前一条边的位置，如果当前边是顶点x的读入的第一条边，则它指向前面第0条边，表示next[tot]:=0
     list2[x]:=tot2;//从入点x引出的边的编号存储给lsit[x]
   end;
   procedure init;
   var i,j,x,y,w:longint;
   begin
     assign(input,fin);reset(input);
     tot:=0; tot2:=0;
     fillchar(f,sizeof(f),true);
     fillchar(next,sizeof(next),0);
     fillchar(cost,sizeof(cost),0);
     fillchar(toit,sizeof(toit),0);
     readln(n,m,start);
     for i:=1 to m do
       begin
         readln(x,y,w);
         makelist(x,y,w);
         makelist2(y,x,w)
       end;
   end;
   procedure spfa(start:longint);
   var i,x,y,t:longint;
   begin
     for i:=1 to n do d[i]:=maxint;
     d[start]:=0;
     head:=0;tail:=1;
    q[1]:=start;f[start]:=false; //源点start入队
     while head<tail do
       begin
         inc(head);      //队首元素出队，t存储当前x顶点的边的编号
         x:=q[head];
         t:=list[x];    //t存储当前x顶点的边的编号
         f[x]:=true;
         while t<>0 do  //处理x的所有边
           begin
             y:=toit[t];  //y存储第t条边的另一个顶点
             if d[x]+cost[t]<d[y]  then //松驰操作
               begin
                 d[y]:=d[x]+cost[t];
                 if f[y] then begin inc(tail);q[tail]:=y;f[y]:=false;end;//入队
               end;
             t:=next[t];//处理顶点x的下一条边
           end;
       end;
   end;
   procedure spfa2(start:longint);
   var i,x,y,t:longint;
   begin
     fillchar(f,sizeof(f),true);
     for i:=1 to n do d2[i]:=maxint;
     d2[start]:=0;
     head:=0;tail:=1;
    q[1]:=start;f[start]:=false; //源点start入队
     while head<tail do
       begin
         inc(head);      //队首元素出队，t存储当前x顶点的边的编号
         x:=q[head];
         t:=list2[x];    //t存储当前x顶点的边的编号
         f[x]:=true;
         while t<>0 do  //处理x的所有边
           begin
             y:=toit2[t];  //y存储第t条边的另一个顶点
             if d2[x]+cost2[t]<d2[y]  then //松驰操作
               begin
                 d2[y]:=d2[x]+cost2[t];
                 if f[y] then begin inc(tail);q[tail]:=y;f[y]:=false;end;//入队
               end;
             t:=next2[t];//处理顶点x的下一条边
           end;
       end;
   end;
   procedure print;
   var i,max:longint;
   begin
      assign(output,fout);rewrite(output);
      max:=-1;
      for i:=1 to n do if max<d[i]+d2[i] then max:=d[i]+d2[i];
      writeln(max);
      close(output);
   end;
begin
  init;
  spfa(start);
  spfa2(start);
  print;
end.

View Code