Question

Dijkstra求最短路我已经明白了，但是次短路……

次短路网上有多种做法：第一种枚举点u，找dist[u]+w(u,v)来查找到点v的次短路
第二种：枚举点u,v找dist[u]+dist2[u2]+w(u,u2)查找次短路dist2指从终点到各个点的最短路，dist是起点。
第三种：做一遍dijkstra的时候同时记录最短路和次短路。
那么这三种里面哪些是对的，哪些是错的？求给出证明和详细解释。

Answer 1

/*
*题目大意：
*在一个有向图中,求从s到t两个点之间的最短路和比最短路长1的次短路的条数之和;
*
*算法思想：
*用A*求第K短路,目测会超时,直接在dijkstra算法上求次短路;
*将dist数组开成二维的,即dist[v][2],第二维分别用于记录最短路和次短路;
*再用一个cnt二维数组分别记录最短路和次短路的条数;
*每次更新路径的条数时,不能直接加1,,应该加上cnt[u][k],k为次短路径或者最短路径的标记;
*图有重边,不能用邻接矩阵存储;
*不知道为什么,题目上说的是N and M, separated by a single space, with 2≤N≤1000 and 1 ≤ M ≤ 10000;
*而我的代码硬是把N开成1W了才过,求解释,RE了无数次,擦;
**/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;

const int N=11111;
const int M=111111;
const int INF=0xffffff;

struct node
{
int to;
int w;
int next;
};

node edge[N];
int head[N];

int dist[N][2],cnt[N][2];
bool vis[N][2];
int n,m,s,t,edges;

void addedge(int u,int v,int w)
{
edge[edges].w=w;
edge[edges].to=v;
edge[edges].next=head[u];
head[u]=edges++;
}

int dijkstra()
{
int k;
for(int i=0; i<=n; i++)
{
dist[i][0]=dist[i][1]=INF;
vis[i][0]=vis[i][1]=0;
cnt[i][0]=cnt[i][1]=0;
}
cnt[s][0]=1,dist[s][0]=0;

for(int i=1; i<=n*2; i++)
{
int u=-1;
int min_dist=INF;
for(int j=1; j<=n; j++)
for(int flag=0; flag<2; flag++)
if(!vis[j][flag]&&dist[j][flag]<min_dist)
{
min_dist=dist[j][flag];
u=j;
k=flag;
}
if(u==-1)
break;
vis[u][k]=true;
for(int e=head[u]; e!=-1; e=edge[e].next)
{
int j=edge[e].to;
int tmp=dist[u][k]+edge[e].w;

if(tmp<dist[j][0])//tmp小于最短路径长:
{
dist[j][1]=dist[j][0];//次短路径长
cnt[j][1]=cnt[j][0];//次短路径计数
dist[j][0]=tmp;//最短路径长
cnt[j][0]=cnt[u][k];//最短路径计数
}

else if(tmp==dist[j][0])//tmp等于最短路径长：
{
cnt[j][0]+=cnt[u][k];//最短路径计数
}

else if(tmp<dist[j][1])//tmp大于最短路径长且小于次短路径长：
{
dist[j][1]=tmp;//次短路径长
cnt[j][1]=cnt[u][k];//次短路径计数
}

else if(tmp==dist[j][1])//tmp等于次短路径长：
{
cnt[j][1]+=cnt[u][k];//次短路径计数
}
}
}

int res=cnt[t][0];
if(dist[t][0]+1==dist[t][1])//判断最短路和次短路是否相差1
res+=cnt[t][1];
return res;
}

int main()
{
//freopen("C:\\Users\\Administrator\\Desktop\\kd.txt","r",stdin);
int tcase;
scanf("%d",&tcase);
while(tcase--)
{
edges=0;
scanf("%d%d",&n,&m);
memset(head,-1,sizeof(head));
int u,v,w;
for(int i=0; i<m; i++)
{
scanf("%d%d%d",&u,&v,&w);
addedge(u,v,w);
}
scanf("%d%d",&s,&t);
printf("%d\n",dijkstra());
}
return 0;
}