思路
這是嚴(yán)格次短路。(題目數(shù)據(jù)有點水暇唾。促脉。辰斋。。瘸味。)
到某個頂點v的次短路要么是其他某個頂點u的最短路再加上e(u,v)宫仗，要么是到u的次短路再加上e(u,v)的邊。因此對于每個頂點旁仿，我們記錄的不僅僅的最短距離藕夫，還有次短距離。
考慮在什么情況下會更新最短路枯冈。（可重復(fù)走同一條邊）
1毅贮、由父親節(jié)點過來的距離小于最短路，那么當(dāng)前最短路變成次短路尘奏，更新最短路
2滩褥、若當(dāng)前距離不能更新最短路，但比次短路小炫加，更新次短路
3瑰煎、若從父親節(jié)點過來的次短路能更新當(dāng)前次短路，更新次短路
所以俗孝，求次短路只需要在更新最短路的時候順便更新次短路就好了
模擬酒甸，可幫助理解上述黑體加粗
送上一個案例
4 6
1 2 1
1 2 5
1 3 2
2 3 2
2 4 1
2 4 6
解法一：dij變形
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> iip;
typedef pair<ll, ll> llp;
const int MAXN = 100005;
const int MAXM = 100005;
const int INF = 0x3f3f3f3f;
const int MOD = 998244353;
int i, j, n, m, a, b, d, cnt, dis[MAXN], dis2[MAXN], head[MAXN];
struct edge{
int u;
int v;
int w;
int next;
edge(){};
edge(int _u, int _v, int _w, int _next) : u(_u), v(_v), w(_w), next(_next) {};
}e[2*MAXM];
void init() {
cnt = 0;
for(i = 0; i <= n; i++) {
dis[i] = INF;
dis2[i] = INF;
head[i] = -1;
}
}
void addEdge(int u, int v, int w) {
e[cnt] = edge(u, v, w, head[u]);
head[u] = cnt++;
}
void dij(int s) {
dis[s] = 0;
priority_queue<iip, vector<iip>, greater<iip> > pq;
pq.push({dis[s], s});
while(!pq.empty()) {
iip now = pq.top();
pq.pop();
int u = now.second;
int d = now.first;
if(dis2[u] < d) continue;
for(i = head[u]; i != -1; i = e[i].next) {
int d2 = d + e[i].w;//注意此處與最短路的區(qū)別，取出的當(dāng)前最小距離不一定是離起始點的最短距離驹针，還可以是次小距離烘挫！所以不能用 d2 = dis[u] + e[i].w;
int v = e[i].v;
if(dis[v] > d2) {//如果父親結(jié)點過來的距離小于最短路
swap(dis[v], d2);//那么當(dāng)前最短路變成次短路，更新最短路
pq.push({dis[v], v});
}
if(dis2[v] > d2 && dis[v] < d2) {//若當(dāng)前距離不能更新最短路柬甥，但比當(dāng)前次短路幸；或者從父親結(jié)點過來的次短路比當(dāng)前次短路小
dis2[v] = d2;//更新次短路
pq.push({dis2[v], v});
}
}
}
}
int main()
{
scanf("%d%d", &n, &m);
init();
while(m--) {
scanf("%d%d%d", &a, &b, &d);
addEdge(a, b, d);
addEdge(b, a, d);
}
dij(1);
printf("%d\n", dis2[n]);
return 0;
}
解法二：利用第k短路算法
這題數(shù)據(jù)還是很弱的苛蒲，以下第 k 短路算法并沒有遵守題意中的嚴(yán)格次短路還是AC了卤橄，讀者可自行測試數(shù)據(jù)：
4 4
1 2 1
1 3 1
2 4 1
3 4 1
解法一：ans = 4;
解法二：ans = 2;
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> llp;
typedef pair<int, int> iip;
const int MAXN = 200005;
const int MAXM = 200005;
const int INF = 0x3f3f3f3f;
const int MOD = 998244353;
int i, j, n, m, cnt, a, b, d, head[MAXN], dis[MAXN], num = 0;
struct edge{
int u, v, w, next;
edge(){};
edge(int _u, int _v, int _w, int _next) : u(_u), v(_v), w(_w), next(_next) {};
}e[MAXM];
struct node{
int g, v;//g(n)起點到頂點v的實際距離
node(){};
node(int _g, int _v) : g(_g), v(_v) {};
bool operator < (const node &x) const{
return g + dis[v] > x.g + dis[x.v];//f(n) = g(n) + h(n)
}
};
void init() {
cnt = 0;
for(i = 0; i <= n; i++) {
dis[i] = INF;
head[i] = -1;
}
}
void addEdge(int u, int v, int w) {
e[cnt] = edge(u, v, w, head[u]);
head[u] = cnt++;
}
void dij(int s) {
priority_queue<iip, vector<iip>, greater<iip> > pq;
dis[s] = 0;
pq.push({dis[s], s});
while(!pq.empty()) {
iip now = pq.top();
pq.pop();
int u = now.second;
if(dis[u] < now.first) continue;
for(i = head[u]; i != -1; i = e[i].next) {
int v = e[i].v;
if(dis[u] != INF && dis[u] + e[i].w < dis[v]) {
dis[v] = dis[u] + e[i].w;
pq.push({dis[v], v});
}
}
}
}
int Astar(int s, int t, int k) {
if(dis[s] == INF) return -1;//不存在第k短路
priority_queue<node> pq;//根據(jù)估值函數(shù)搜索
if(s == t) k++;//起點和終點相同時，需繞一圈再回來
pq.push(node(0, s));
while(!pq.empty()) {
node now = pq.top();
pq.pop();
if(now.v == t) num++;//若為嚴(yán)格第k短路臂外，可用set存每次到達終點的距離窟扑，根據(jù)set的大小來判斷是否到達嚴(yán)格第k短路
if(num == k) return now.g;//走到第k短路時，返回實際距離
for(i = head[now.v]; i != -1; i = e[i].next) {
pq.push(node(now.g + e[i].w, e[i].v));//g(n) = 父親結(jié)點的 g + 這條邊的距離
}
}
}
int main()
{
scanf("%d%d", &n, &m);
init();
while(m--) {
scanf("%d%d%d", &a, &b, &d);
addEdge(a, b, d);
addEdge(b, a, d);
}
dij(n);//h(n)漏健，各個頂點到終點n的估計距離（最短距離）嚎货，有向圖需反向
int ans = Astar(1, n, 2);
printf("%d\n", ans);
return 0;
}
