【BZOJ3575】【HNOI2014】道路堵塞

好玄学的题。。

首先从\(1~n\)的最短路应该是\(1\)沿着最短路径走到某个点然后xjb走一圈走到最短路上的另一个点再沿着最短路走到\(n\)。

那么我们先考虑前两个部分,每一次维护最短路径上前\(i\)条边可以走,到每一个不在最短路径上的点的最短路。

那么再用这些点去更新最短路径上的点的答案。

由于更新的是一段区间(没有经过的边可能不止一条),随便用数据结构维护一下。

说点什么

您将是第一位评论人!

提醒
wpDiscuz