设 f(i) 表示警方可以封锁一条道路，i\to n 的最短路。分两种转移，一种是警方封锁 i 的邻边，一种是警方没有封锁 i 的邻边，两种情况取较大值即为 f(i)。
对于第二种情况，设 j 为 i 的邻边，则 f(i)\gets\min\{f(j)+1\}。
设 G(i, e) 表示删除边 e 后 i\to n 的最短路。设 e 为 i 的邻边，令 g(i)=\max\{G(i,e)\}。则对于第一种情况 f(i)\gets g(i)。所以设 j 为 i 的邻边，那么 f(i)=\max\{g(i),\min\{f(j)+1\}\}。假设现在求出了 g，那么 f 可以直接用堆来求出。这部分时间复杂度为 O(n\log n+m)。
考虑怎么求 g，先将最短路树建出来，设 p(i) 为 i 最短树上的父亲，那么删除 (i,p(i)) 一定是最优的。设 x 为 i 子树内的点，y 为 i 子树外的点，E 为边集，那么 g(i)=\min_{(x,y)\in E}\{dis(x)+dis(y)+1-dis(i)\}，其中 dis(i) 表示 i\to n 的最短路。
有很多种方式求 g，这里只讲其中一种，定义边 (x,y) 的权值为 dis(x)+dis(y)+1，按边的权值从小到大枚举。假设当前枚举到了边 (x,y)，那么它能贡献到点 i 当且仅当 i 之前没有被更新且 i 不是 \text{LCA}(x,y) 的祖先（包括 \text{LCA}(x,y)），用并查集维护 i 的第一个没有被更新的祖先即可。时间复杂度：O(n\alpha(n))。