mengbierr

一个蒟蒻的博客

4月30

Codeforces 925D Aztec Catacombs

题目大意

给你n个点,m条边的无向图,要求从s=1走到t=n,每次从u走到v后,与u相连的边都会消失,而原本没有的边会出现,问走到n的最短距离或判断无法走到。

题解

我们把路径分成两类,一种是只走原有的边就能到达终点,一种是需要在走原本没有的边才能到达。
第一种路径的最小值直接bfs就能求出。
另每个点到1的距离为 dis_i
对于第二种路径,可以发现,它的长度至少为4:从s出发先走到v_1,再走到v_2(要求dis_{v_2}=2)(因为无法返回s),这时就可以返回s,这样st的路径也出现了,这样答案就是4.
所以,只要有一个dis=2的点,答案就至多为4,只要和第一种路径取min.
如果只有dis1的点且t1不在一个联通块怎么办?将所有点与1相连的边删除,并将不与1相连的点删去,这样原图就变成了若干小联通块,如果这些联通块都是团(任意两点之间都有边)的话,则无法到达,否则就可以这样走:
设联通块大小为C,找到一个度数不为C的点v_1,和一个联通块内与它没有边相连的点v_3,找到一个与这两个点都相连的点v_2,就有s->v_1->v_2->v_3->v_1->t,答案为5.(证明同第二种路径的证明)

发表评论

电子邮件地址不会被公开。 必填项已用*标注