1.次短路问题
次短路问题和最短路问题类似，我们可以想到次短路由什么转移而来？对于当前一个点，其次短路只可能由两种情况转移而来：
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=1e5+10;
typedef pair<int,int> pii;
struct Edge
{
int nex,to,val;
}edge[maxn<<1];
int dis[maxn],dis2[maxn],head[maxn],tot=0; //dis2[]保存次短路
int n,m;
void init()
{
tot=0;
memset(head,-1,sizeof(head));
}
void add(int from,int to,int val)
{
edge[++tot].to=to;
edge[tot].val=val;
edge[tot].nex=head[from];
head[from]=tot;
}
void solve(int s)
{
priority_queue<pii, vector<pii>, greater<pii> > q; //压入最短或次短距离
memset(dis,inf,sizeof(dis));
memset(dis2,inf,sizeof(dis2));
dis[s]=0;
q.push(make_pair(0,s)); //first是权值second是点
while(!q.empty())
{
int v=q.top().second;
int d=q.top().first;
q.pop();
if(dis2[v]<d) continue; //取出的不是次短距离，抛弃
for(int i=head[v];i!=-1;i=edge[i].nex)
{
int d2=d+edge[i].val; //d为原点到i的最短距离或次短距离
if(dis[edge[i].to]>d2) //更新最短距离
{
swap(dis[edge[i].to],d2);
q.push(make_pair(dis[edge[i].to],edge[i].to));
}
if(dis2[edge[i].to]>d2&&dis[edge[i].to]<d2) //更新次短距离
{
dis2[edge[i].to]=d2;
q.push(make_pair(dis2[edge[i].to],edge[i].to));
}
}
/*
if(dis[edge[i].to]>d2) //更新最短距离
{
dis2[edge[i].to]=dis[edge[i].to];
dis[edge[i].to]=d2;
q.push(make_pair(dis2[edge[i].to],edge[i].to));
q.push(make_pair(d2,edge[i].to));
}
if(dis2[edge[i].to]>d2&&dis[edge[i].to]<d2) //更新次短距离
{
dis2[edge[i].to]=d2;
q.push(make_pair(dis2[edge[i].to],edge[i].to));
}
*/
}
}
int main()
{
init();
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i){
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
add(a,b,c);
add(b,a,c);
}
solve(1);
printf("%d
",dis2[n]);
}
【题意】：求最短路以及次短路的条数（次短路必须只比最短路大一个单位）
#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=1e5+10;
int dist[maxn][2],cnt[maxn][2],head[maxn]; //数组0表示最短，1表示次短
bool vis[maxn][2];
int n,m,tot;
struct Edge
{
int nex,to,val;
} edge[maxn<<4];
void addedge(int from,int to,int val)
{
edge[++tot].to=to;
edge[tot].val=val;
edge[tot].nex=head[from];
head[from]=tot;
}
void dijkstra(int s)
{
int pos,minn,k;
for(int i=1; i<=n; i++)
dist[i][0]=dist[i][1]=inf;
memset(vis,false,sizeof(vis));
memset(cnt,0,sizeof(cnt));
cnt[s][0]=1;
dist[s][0]=0;
for(int i=1;i<=tot;i++)
{
pos=-1;
minn=inf;
for(int j=1; j<=n; j++)
if(!vis[j][0]&&minn>dist[j][0]) //找最短路,每个节点先更新最短，然后次短
{
k=0;
minn=dist[j][0];
pos=j;
}
else if(!vis[j][1]&&minn>dist[j][1]) //找次短路
{
k=1;
minn=dist[j][1];
pos=j;
}
if(pos==-1) break;//如果找不到最短或者次短就结束
vis[pos][k]=1;
for(int j=head[pos];j!=-1;j=edge[j].nex)
{
int v=edge[j].to;
int d=dist[pos][k]+edge[j].val;
if(d<dist[v][0]) //更新最短路长度及条数
{
dist[v][1]=dist[v][0];
cnt[v][1]=cnt[v][0];
dist[v][0]=d;
cnt[v][0]=cnt[pos][k];
}
else if(d==dist[v][0])
cnt[v][0]+=cnt[pos][k];
else if(d<dist[v][1]) //更新次短路
{
dist[v][1]=d;
cnt[v][1]=cnt[pos][k];
}
else if(d==dist[v][1])
cnt[v][1]+=cnt[pos][k];
}
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
tot=0;
memset(head,-1,sizeof(head));
scanf("%d%d",&n,&m);
int a,b,c,s,t;
for(int i=1; i<=m; i++)
{
scanf("%d%d%d",&a,&b,&c);
addedge(a,b,c);
}
scanf("%d%d",&s,&t);
dijkstra(s);
int ans=cnt[t][0];
if(dist[t][1]==dist[t][0]+1)
ans+=cnt[t][1];
printf("%d
",ans);
}
}
次短路问题也可以k短路用算法来解决。