严格次短路定义
按路径长度从小到大排序，去重后排名第 \(2\) 的路径就是次短路。
显然，链式不存在次短路的，连单向边的树也不存在（想一想，为什么）
严格次短路求法
这里使用的是SPFA，Dijkstra类似。
显然，我们需要在松弛时做手脚。
下面令 \(dis[u][0]\) 是最短路，\(dis[u][1]\) 是次短路，\(w\) 表示当前松弛的边 \(u \to v\) 的权。
情况 \(1\)
最短路三角形不等式：
\[dis[v][0]>dis[u][0]+w \]那么我们将最短路更新，然后将用原来的最短路覆盖上次短路。
情况 \(2\)
用最短路松弛次短路
\[dis[v][1]>dis[u][0]+w \operatorname{ And }dis[u][0]+w>dis[v][0] \]这种情况我们用最短路松弛式更新次短路。
情况 \(3\)
次短路三角形不等式：
\[dis[v][1]>dis[u][1]+w \]直接更新此段路。
实战演练：P2865 [USACO06NOV]Roadblocks G | LibreOJ10076. 「一本通 3.2 练习 2」Roadblocks
给出一张无向图 \(G(N,R)\)，求从 \(N\) 到 \(1\) 的次短路。
\(1 \le N \le 5000,1 \le R \le 100000\)
代码如下：
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct edge{
int nxt,to,w;
} g[5000005];
int head[5005],ec;
void add(int u,int v,int w){
g[++ec].nxt=head[u];
g[ec].to=v;
g[ec].w=w;
head[u]=ec;
}
queue<int> q;
bool vis[5005];
int dis[5005][5];
void spfa(int s){ // 关于SPFA，它还没有死
#define pushq if(!vis[v])vis[v]=1,q.push(v);
memset(dis,0x7f,sizeof(dis));
q.push(s);
dis[s][0]=0;
vis[s]=1;
while(!q.empty()){
int u=q.front();
q.pop();
vis[u]=0;
for(int i=head[u];i;i=g[i].nxt){
int v=g[i].to,w=g[i].w;
// 接下来是大力分类讨论
if(dis[v][0]>dis[u][0]+w){
dis[v][1]=dis[v][0];
dis[v][0]=dis[u][0]+w;
pushq;
}
if(dis[v][1]>dis[u][0]+w&&dis[u][0]+w>dis[v][0]){
dis[v][1]=dis[u][0]+w;
pushq;
}
if(dis[v][1]>dis[u][1]+w){
dis[v][1]=dis[u][1]+w;
pushq;
}
}
}
}
signed main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;
add(u,v,w);
add(v,u,w);
}
spfa(n);
cout<<dis[1][1]<<'\n';
return 0;
}