图上的严格次路径
狄杰特斯拉定理不仅可以用来求最短路，同时也可以在同样的复杂度里完成次短路的计算。
核心在于开两个数组，分别记录最短路和次短路，当一个点转移到另一个点时，可以通过比较其值和当前点的最短路和次短路值的大小，来进行更新。
另外的功能是，可以统计有起点和终点之间，存在多少条最短路径，以及多少条此短路径。
模板代码如下：
#include <bits/stdc++.h>
using namespace std;
const int maxn=1005,H=10005,INF=0x3f3f3f3f;
typedef pair<int,int> P;
int N,M;
int Head[maxn],Next[H],ver[H],edge[H],tot=0;
inline void add(int x,int y,int z)
{
ver[++tot]=y,edge[tot]=z;
Next[tot]=Head[x];
Head[x]=tot;
}
priority_queue<P,vector<P>,greater<P> >Q;
int d[3][maxn],sum[3][maxn];
void pre(int sit)
{
fill(d[0],d[0]+maxn,INF);
fill(d[1],d[1]+maxn,INF);
memset(sum,0,sizeof(sum));
d[0][sit]=0;
sum[0][sit]=1;
Q.push(make_pair(0,sit));
while(!Q.empty())
{
P tmp=Q.top();
Q.pop();
int x=tmp.second,v=tmp.first;
int k=-1;
if(d[0][x]==v)k=0;
if(d[1][x]==v)k=1;
if(k==-1)continue;
for(int i=Head[x];i;i=Next[i])
{
int y=ver[i],z=edge[i];
if(d[0][y]>v+z)
{
d[1][y]=d[0][y];
sum[1][y]=sum[0][y];
d[0][y]=v+z;
sum[0][y]=sum[k][x];
//由于在上一次最短路被更新时，已经被push过一次了，所以不需要再push一次刚刚更新的次短路，避免重复
Q.push(make_pair(d[0][y],y));
}
else if(d[0][y]==v+z)
{
sum[0][y]+=sum[k][x];
}
else if(d[1][y]>v+z)
{
d[1][y]=v+z;
sum[1][y]=sum[k][x];
Q.push(make_pair(d[1][y],y));
}
else if(d[1][y]==v+z)
{
sum[1][y]+=sum[k][x];
}
}
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
tot=0;
memset(Head,0,sizeof(Head));
memset(Next,0,sizeof(Next));
scanf("%d %d",&N,&M);
int a,b,c;
for(int i=1;i<=M;i++)
{
scanf("%d %d %d",&a,&b,&c);
add(a,b,c);
}
int S,F;
scanf("%d %d",&S,&F);
pre(S);
int ans=sum[0][F];
if(d[0][F]+1==d[1][F])ans+=sum[1][F];
printf("%d\n",ans);
}
}如果只是求最短路和此短路，我们可以用贪心优化，将上述代码进行优化，可以更快的得到答案。
#include <bits/stdc++.h>
using namespace std;
inline int read() {
char ch = getchar(); int x = 0, f = 1;
while(ch < '0' || ch > '9')
{
if(ch == '-') f = -1;
ch = getchar();
}
while('0' <= ch && ch <= '9')
{
x = x * 10 + ch - '0';
ch = getchar();
} return x * f;
}
const int maxn=5005,H=100005,INF=0x3f3f3f3f;
struct imf{
int x,y,type;
bool operator < (const imf &W) const{
return x > W.x;
}
};
int N,M;
int Head[maxn],Next[2*H],ver[2*H],edge[2*H],tot=0;
inline void add(int x,int y,int z)
{
ver[++tot]=y,edge[tot]=z;
Next[tot]=Head[x];
Head[x]=tot;
}
bool vis[maxn][3];
priority_queue<imf>Q;
int d[3][maxn];
void pre(int sit)
{
fill(d[0],d[0]+maxn,INF);
fill(d[1],d[1]+maxn,INF);
d[0][sit]=0;
Q.push((imf){0,1,0});
while(!Q.empty())
{
imf tmp=Q.top();
Q.pop();
int x=tmp.y,v=tmp.x;
if(vis[x][tmp.type])continue;
vis[x][tmp.type]=true;
for(int i=Head[x];i;i=Next[i])
{
int y=ver[i],z=edge[i];
if(d[0][y]>v+z)
{
d[1][y]=d[0][y];
d[0][y]=v+z;
Q.push((imf){d[0][y],y,0});
Q.push((imf){d[1][y],y,1});
}
else if(d[1][y]>v+z&&v+z>d[0][y])
{
d[1][y]=v+z;
Q.push((imf){d[1][y],y,1});
}
}
}
}
int main()
{
scanf("%d %d",&N,&M);
int a,b,c;
for(int i=1;i<=M;i++)
{
a=read(),b=read(),c=read();
add(a,b,c);
add(b,a,c);
}
pre(1);
printf("%d",d[1][N]);
}注意到两段代码有所不同，其主要原因是，前者需要求路径，所以必须保证不重不漏，那么就不能利用贪心快速求解，主体上差别不大，第一段代码虽然速度略慢，但功能相对更强。
再附加次小生成树的模板代码，主要用到了树上倍增的思想
#include <bits/stdc++.h>
#define maxn 100005
using namespace std;
typedef long long ll;
struct edge
{
int x,y,z;
}T[3*maxn];
int N,M;
int f[maxn],Head[maxn],ver[2*maxn],Next[2*maxn],Edge[2*maxn],tot=0,t,fa[maxn][20],d[maxn],G[maxn][20][3],re[3*maxn];
int td[maxn],cnt=0;
queue<int>Q;
void add(int x,int y,int z)
{
ver[++tot]=y,Edge[tot]=z;
Next[tot]=Head[x];
Head[x]=tot;
}
int get(int x)
{
if(x==f[x])return x;
return f[x]=get(f[x]);
}
int cmp(edge a,edge b)
{
return a.z<b.z;
}
void dsf()
{
d[1]=1,Q.push(1);
while(!Q.empty())
{
int x=Q.front();
Q.pop();
for(int i=Head[x];i;i=Next[i])
{
int y=ver[i];
if(d[y])continue;
d[y]=d[x]+1;
fa[y][0]=x;
G[y][0][0]=Edge[i];
G[y][0][1]=-1000000000;
for(int j=1;j<=t;j++)
{
fa[y][j]=fa[fa[y][j-1]][j-1];
G[y][j][0]=max(G[y][j-1][0],G[fa[y][j-1]][j-1][0]);
if(G[y][j-1][0]==G[fa[y][j-1]][j-1][0])
{
G[y][j][1]=max(G[y][j-1][1],G[fa[y][j-1]][j-1][1]);
}
else if(G[y][j-1][0]<G[fa[y][j-1]][j-1][0])
{
G[y][j][1]=max(G[y][j-1][0],G[fa[y][j-1]][j-1][1]);
}
else if(G[y][j-1][0]>G[fa[y][j-1]][j-1][0])
{
G[y][j][1]=max(G[y][j-1][1],G[fa[y][j-1]][j-1][0]);
}
}
Q.push(y);
}
}
}
int solve(int x,int y,int z)
{
if(d[x]>d[y])swap(x,y);
int s1=-1000000000,s2=-1000000000;
cnt=0;
for(int i=t;i>=0;i--)
{
if(d[fa[y][i]]>=d[x])
{
td[++cnt] = G[y][i][0];
td[++cnt] = G[y][i][1];
y = fa[y][i];
}
}
if(x!=y)
{
for(int i=t;i>=0;i--)
{
if(fa[x][i]!=fa[y][i])
{
td[++cnt] = G[x][i][0];
td[++cnt] = G[x][i][1];
td[++cnt] = G[y][i][0];
td[++cnt] = G[y][i][1];
x=fa[x][i],y=fa[y][i];
}
}
td[++cnt] = G[x][0][0]; td[++cnt] = G[x][0][1];
td[++cnt] = G[y][0][0]; td[++cnt] = G[y][0][1];
}
for (int i = 1; i <= cnt; i++) {
if (td[i] > s1) {
s2 = s1; s1 = td[i];
} else if (td[i] != s1 && td[i] > s2) s2 = td[i];
}
if (z > s1) return s1;
return s2;
}
int main()
{
scanf("%d %d",&N,&M);
for(int i=1;i<=M;i++)scanf("%d %d %d",&T[i].x,&T[i].y,&T[i].z);
sort(T+1,T+M+1,cmp);
for(int i=1;i<=N;i++)f[i]=i;
ll sum=0;
for(int i=1;i<=M;i++)
{
int x=get(T[i].x),y=get(T[i].y);
if(x==y)continue;
f[x]=y;
re[i]=1;
sum+=T[i].z;
add(T[i].x,T[i].y,T[i].z);
add(T[i].y,T[i].x,T[i].z);
}
t=(int)(log(N)/log(2))+1;
dsf();
ll ans=100000000000000000;
for(int i=1;i<=M;i++)
{
if(re[i])continue;
ans=min(ans,sum+T[i].z-solve(T[i].x,T[i].y,T[i].z));
}
printf("%lld",ans);
}
