思路
这是严格次短路。(题目数据有点水。。。。。)
到某个顶点v的次短路要么是其他某个顶点u的最短路再加上e(u,v)，要么是到u的次短路再加上e(u,v)的边。因此对于每个顶点，我们记录的不仅仅的最短距离，还有次短距离。
考虑在什么情况下会更新最短路。（可重复走同一条边）
1、由父亲节点过来的距离小于最短路，那么当前最短路变成次短路，更新最短路
2、若当前距离不能更新最短路，但比次短路小，更新次短路
3、若从父亲节点过来的次短路能更新当前次短路，更新次短路
所以，求次短路只需要在更新最短路的时候顺便更新次短路就好了
模拟，可帮助理解上述黑体加粗
送上一个案例
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;//注意此处与最短路的区别，取出的当前最小距离不一定是离起始点的最短距离，还可以是次小距离！所以不能用 d2 = dis[u] + e[i].w;
int v = e[i].v;
if(dis[v] > d2) {//如果父亲结点过来的距离小于最短路
swap(dis[v], d2);//那么当前最短路变成次短路，更新最短路
pq.push({dis[v], v});
}
if(dis2[v] > d2 && dis[v] < d2) {//若当前距离不能更新最短路，但比当前次短路小；或者从父亲结点过来的次短路比当前次短路小
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短路算法
这题数据还是很弱的，以下第 k 短路算法并没有遵守题意中的严格次短路还是AC了，读者可自行测试数据：
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;//根据估值函数搜索
if(s == t) k++;//起点和终点相同时，需绕一圈再回来
pq.push(node(0, s));
while(!pq.empty()) {
node now = pq.top();
pq.pop();
if(now.v == t) num++;//若为严格第k短路，可用set存每次到达终点的距离，根据set的大小来判断是否到达严格第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) = 父亲结点的 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;
}
