最短路(route)

先套路的正反求两次最短路,然后容易发现如果反向能更新最短路直接输出1

然后如果不变或者如果这条边压根不在最短路上则输出0,

如果均不是,接下来就是判断这条路是否在最短路上必须经过.

(评讲的时候大佬们给了很多做法,我谈谈我的(可能有点复杂

首先以1为根求出最短路树,(父亲就是更新过来的那个点.

那么2的所有祖先就是最短路上的点,

现在考虑2的祖先边上的这些边是否一定经过,

容易发现,树边是没有影响的,那么加入非树边考虑.

显然非树边要满足经过它一定不影响接下来的最短路.

简单观察,可以得到结论,这条非树边的起点与终点的lca与终点之间的这一段,一定不是必须经过的,

因为可以在lca处走起点的祖先这一段,同样能到达终点.

那么差分一下,最后一边dfs统计一下答案就可以解决这题了.

那么接下来就是简单(个屁的代码实现了...

c++代码如下:

 

回复

  1. 回复 皮皮虾

    xD大佬

  2. 回复 daxi

    学无止境,认真拜读!

  3. 回复 xing

    来看看,因为,总能学到东西!

6 + 5 =