Fork me on GitHub

[SDOI2019]Elaxia的路线

传送门

首先我们可以知道如果把所有最短路上的边挑出来,再按照最短路中$dis$数组的递推关系给它加上方向的话这就是一个有向无环图。
而如果把所有两个最短路的公共边挑出来的话,这个有向无环图中的最长链就是答案。
并且判断一条边在最短路上的方式就是$dis[s→u]+w(u,v)+dis[u→t]=dis[s→t]dis[s→u]+w(u,v)+dis[u→t]=dis[s→t]$。
并且因为这是无向图,所以求任意一个点到终点的距离只需要以终点为起点再跑一遍最短路就可以了。
需要注意的问题就是公共路径从不同的方向经过也是可以的,所以需要把一对起点和终点倒过来再做一遍。

因为知道了自己是多么的菜,所以才要更加努力去追求那个永远也不可能实现的梦想

本文标题:[SDOI2019]Elaxia的路线

文章作者:KRrrrrrrrr

发布时间:2019年11月01日 - 16:11

最后更新:2019年11月01日 - 16:11

原始链接:http://krrrr.xyz/2019/11/01/SDOI2019-Elaxia的路线/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。