题意： 已知一个有 N 个节点 M 条边的无向图，问最短路和比最短路长度大1 的次短路共有多少条。
分析： 在原来的dijkstra()上加一点变动，d[i][0]记录最短路的长度，d[i][1]记录次短路的长度，dp[i][0] 到达当前点最短路的条数，dp[i][1]到达当前点次短路的条数。
View Code /************************************************************************************ 采用dijstra算法的思想，每次从dis[N][2]中选择一个未被标记且值最小的点dis[v][p] (可能这个值是这个点的最短路，也可能是次短路，只有当此点的最短路被标记了次才可能选中 此点的次短路).再用这个值val去更新此点的邻接点u.更新的方法如下: ①如果val小于dis[u][0] dis[u][1]=dis[u][0] waynum[u][1]=waynum[u][0] dis[u][0]=val waynum[u][0]=waynum[v][p] 否则转② ②如果val=dis[u][0] waynum[u][0]+=waynum[v][p] 否则转③ ③如果val小于dis[u][1], dis[u][1]=val waynum[u][1]=waynum[v][p] 否则转④ ④如果val等于dis[u][1] waynum[u][1]+=waynum[v][p]************************************************************************************/#include#include #define INF 999999999#define clr(x)memset(x,0,sizeof(x))const int maxn=1005;struct node{ int to,next,w;}e[100005];int tot;int head[maxn];void add(int s,int u,int wi){ e[tot].w=wi; e[tot].to=u; e[tot].next=head[s]; head[s]=tot++;}int n,m,st,en;int d[maxn][2];int dp[maxn][2];int v[maxn][2];int dijkstra(){ int i,j,u,tmp,p,k,dis; clr(v); clr(dp); memset(dp,0,sizeof(dp)); for(i=1;i<=n;i++) d[i][0]=d[i][1]=INF; d[st][0]=0; dp[st][0]=1; for(i=1;i