题意：找出最短路和比最短路大一个单位的路的条数
分析：使用K短路算法会超内存，因此看完题解，要使dij变形解决问题
记录最短路和次短路，和最短路的条数和次短路的条数。
dij松弛的条件改变下，有四种情况
1.比最短路短2.等于最短路3.长与最短路但短于次短路4.等于次短路
View Code #include#include #include #include using namespace std;#define MAXN 1005#define MAXM 10050#define INF 1000000000struct eee{ int v,w,next; eee(){}; eee(int v,int w):v(v),w(w){};}edge[MAXM];struct node{ int v,c; int kind;//0最短路，1次短路 node(){}; node(int v,int c,int kind):v(v),c(c),kind(kind){}; bool operator <(const node a)const{ return c>a.c; }};int m_d[MAXN],s_d[MAXN],m_ans[MAXN],s_ans[MAXN];int first[MAXN];bool vis[MAXN][2];int n,m,e,st,en;priority_queue q;void init(int n){ memset(first,-1,sizeof(first)); for(int i=0;i<=n;i++){ m_d[i]=s_d[i]=INF; m_ans[i]=s_ans[i]=0; vis[i][0]=vis[i][1]=0; } e=0;}void add(int u,int v,int w){ edge[e]=eee(v,w); edge[e].next=first[u]; first[u]=e++;}void dij(int st){ while(!q.empty())q.pop(); m_d[st]=0; m_ans[st]=1; node a=node(st,0,0); q.push(a); while(!q.empty()){ node cur=q.top(); q.pop(); if(vis[cur.v][cur.kind])continue; vis[cur.v][cur.kind]=1; int u=cur.v; for(int i=first[u];i!=-1;i=edge[i].next){ int temp_len=cur.c+edge[i].w; int v=edge[i].v; if(temp_len