【題目鏈接】

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;
}