题目：

　　

　　

　　

题意：

　　找到从s到t与最短路长度相差少于1的路径总数。

分析：

　　首先，搞明白题意之后，我们来考虑一下怎么处理这个1，怎样找相差为1的路径呢？我们这样想，如果有相差为1的路径，那么它将会是严格的次短路，所以我们可以再跑最短路的时候顺带着跑了次短路（严格的），然后判断一下和最短路是不是相差一然后就计算一下就好了，当然，这个的时间复杂度其实就是常数大了的E*logE的，所以时间复杂度是没问题的，然后就是代码：

#include
#include
#include
using namespace std;
const int maxn=(1e3)*+;
const int maxm=1e5+;
struct E{
int to;
int next;
int val;
}ed[maxm];
int tot;
int head[maxn];
void J(int a,int b,int c){
tot++;
ed[tot].to=b;
ed[tot].val=c;
ed[tot].next=head[a];
head[a]=tot;
}
struct Node{
int dis;
int x;
int ci;
friend bool operator < (Node a,Node b){ return a.dis>b.dis;
}
Node(int a,int b,int c){
x=a;
dis=b;
ci=c;
}
};
priority_queue qu;
bool vis[maxn][];
int cot[maxn][];
int dis[maxn][];
int main(){
int t;
scanf("%d",&t);
for(int jsjs=;jsjs<=t;jsjs++){ memset(head,,sizeof(head)); tot=; memset(vis,,sizeof(vis)); memset(cot,,sizeof(cot)); memset(dis,0x3f,sizeof(dis)); int n,m; scanf("%d%d",&n,&m); int js1,js2,js3; for(int i=;i<=m;i++){ scanf("%d%d%d",&js1,&js2,&js3); J(js1,js2,js3); } int s,q; scanf("%d%d",&s,&q); dis[s][]=; cot[s][]=; qu.push(Node(s,,)); while(!qu.empty()){ Node js=qu.top(); qu.pop(); if(vis[js.x][js.ci]) continue; vis[js.x][js.ci]=; for(int i=head[js.x];i;i=ed[i].next){ int to=ed[i].to; int di=js.dis+ed[i].val; if(dis[to][]>di){
dis[to][]=dis[to][];
dis[to][]=di;
cot[to][]=cot[to][];
cot[to][]=cot[js.x][js.ci];
qu.push(Node(to,dis[to][],));
qu.push(Node(to,dis[to][],));
continue;
}
if(dis[to][]==di){
cot[to][]+=cot[js.x][js.ci];
continue;
}
if(dis[to][]>di){
dis[to][]=di;
cot[to][]=cot[js.x][js.ci];
qu.push(Node(to,dis[to][],));
continue;
}
if(dis[to][]==di){
cot[to][]+=cot[js.x][js.ci];
continue;
}
}
}
printf("%d\n",cot[q][]+(dis[q][]==dis[q][]+?cot[q][]:));
}
return ;
}