Readme

3123.Find-Edges-in-Shortest-Paths

本题需要去除图中不在起点与终点最短路径上的边。

首先，我最容易想到的是“去除图中不在起点与终点最短路径上的点”。这个只需要跑两遍Dijkstra，求出所有点到起点的最短距离d1，和到终点的最短距离d2.如果d1[i]+d2[i]!=d1[n-1]，那么点i一定不在起讫点的最短路径上，称作“冗余点”；反之叫“关键点”。

那么如果判定“冗余边”和“关键边”呢？关键边的两个端点a和b必须都是关键点，并且自身的边一定要在最短路径上，显然我们可以通过如下判定即可。

d1[a] + w + d2[b] == d1[n-1]