信息学奥赛一本通 1498：Roadblocks | 洛谷 P2865 [USACO06NOV] Roadblocks G

【题目链接】

ybt 1498：Roadblocks
洛谷 P2865 [USACO06NOV] Roadblocks G

【题目考点】

1. 图论：严格次短路径

严格次短路的路径长度必须大于最短路的路径长度。
非严格次短路的路径长度大于等于最短路的路径长度。

【解题思路】

每个交叉路口是一个顶点，每条路是无向边，求从顶点1到顶点n的严格次短路。
使用Dijkstra堆优化算法。
设Path类，包含属性u和d，表示存在一条从源点出发到达顶点u，长度为d的路径。
设优先队列pq，优先队列中保存的元素为Path类型对象，路径长度d更小的Path对象更优先。
设dis1，dis2数组，dis1[i]表示从源点到顶点i的最短路径长度，dis2[i]表示从源点到顶点i的次短路径长度。
首先将dis1和dis2数组每个元素都设为无穷大。
已知源点1到顶点1自己的最短路径长度为0，设dis1[1]=0，那么存在一条从源点到顶点1，长为0的路径，将对象Path{1, 0}入队到优先队列pq。
每次循环从优先队列出队长度最短的路径，取出该路径为从源点到达顶点u，路径长度为d。
访问顶点u的每个邻接点，顶点u到其邻接点v的边权为w。那么就存在一条从源点到顶点v的长为d+w的路径。

• 如果该到达顶点v的长为d+w的路径比从源点到顶点v的最短路径长度dis1[v]更小，那么原来的最短路径长度变为次短路径长度，即dis2[v] = dis1[v]，当前的最短路径长度是d+w，设dis1[v] = d+w。
  现在存在一条新的到达顶点v长为dis1[v]的路径，将对象Path{v, dis1[v]}入队。
• 如果该到达顶点v的长为d+w的路径比从源点到顶点v的最短路径长度dis1[v]更大（注意不能等于dis1[v]），d+w比次短路径长度dis2[v]更小，那么当前的次短路径长度应该为d+w，设dis2[v] = d+w。
  现在存在一条新的到达顶点v长为dis2[v]的路径，将对象Path{v, dis2[v]}入队。

最后结果为源点1到顶点n的严格次短路长度，即dis2[n]。

关于使用Dijkstra堆优化算法求次短路时，不能设vis数组进行优化

如果使用Dijkstra堆优化算法求最短路径，每个顶点只出队1次即可，第2次出队时没有必要继续扩展。可以设vis数组记录顶点是否已出队。而在求次短路过程中不能使用该方法进行优化。

已知从优先队列中出队的各个Path对象的路径长度d属性的单调递增的。

如果出队的Path对象为到达顶点u路径长度为d1。根据优先队列的比较规则，此时d1小于等于优先队列中所有Path对象的d属性。
通过顶点u扩展出的新的路径的长度为d1+w（w为顶点u到其某个邻接点的边权），因为Dijkstra的前提是图中没有负权边，所以d1+w一定大于d1，因此新入队的Path对象的d属性也大于d1。
因此接下来出队的Path对象的d属性一定大于等于d1，即按出队顺序看，Path对象的d属性是单调递增的。

顶点u第一次出队时，出队的Path对象为到达顶点u有长为d1的路径。顶点u第二次出队，出队的Path对象为到达顶点u有长为d2的路径。那么根据上述原理，一定有$d2\ge d1$。认为到顶点u有长为d1的路径，接下来扩展得到到其它顶点的最短路径长度，一定小于等于认为到顶点u有长为d2的路径，接下来扩展得到到其它顶点的最短路径长度。因此如果一个顶点第二次出队，就没有必要再继续进行扩展了。
vis[u]表示顶点u是否已经出队。如果顶点u已经出队过了，则不再访问更新其邻接点。否则设vis[u]为真，标记顶点u已出队，接下来访问更新其邻接点。

而求次短路时不应设vis数组记录顶点是否出队，因为当顶点u第二次出队时，如果是到顶点u有长为d2的路径，基于该存在的路径虽然不可能再更新各顶点的最短路径dis1的长度，但可能更新各顶点的次短路径dis2的长度。因此求次短路时不能进行该优化过程。

【题解代码】

解法1：Dijkstra堆优化算法

#include<bits/stdc++.h>
using namespace std;
#define N 5005
struct Edge
{int v, w;
};
struct Pair
{int u, d;//u：顶点 d：sv到u有一条长为d的路径 bool operator < (const Pair &b) const{return b.d < d;}
};
vector<Edge> edge[N];
int n, m, dis1[N], dis2[N];//dis1[i]:源点到i的最短路径长度 dis2[i]：源点到i的严格次短路长度 
void dijkstra(int sv)
{priority_queue<Pair> pq;memset(dis1, 0x3f, sizeof(dis1));memset(dis2, 0x3f, sizeof(dis2));dis1[sv] = 0;pq.push(Pair{sv, dis1[sv]});while(!pq.empty()){int u = pq.top().u, d = pq.top().d;pq.pop();for(Edge e : edge[u]){int v = e.v, w = e.w;if(dis1[v] > d+w){dis2[v] = dis1[v];dis1[v] = d+w;pq.push(Pair{v, dis1[v]});}else if(dis1[v] < d+w && d+w < dis2[v]){dis2[v] = d+w;pq.push(Pair{v, dis2[v]});}}}
}
int main()
{int f, t, w;cin >> n >> m;for(int i = 1; i <= m; ++i){cin >> f >> t >> w;edge[f].push_back(Edge{t, w});edge[t].push_back(Edge{f, w});}dijkstra(1);cout << dis2[n];return 0;
}