题目链接:传送门
题目大意:给你一幅图（单向边），找出从起点到终点有多少条不同路径（最短路或者比最短路长度大1）
题目思路:二维dijkstra，真的是要对dijkstra理解非常透彻才行,距离数组d开成二维表示最短路与次短路，同时需要一个cnt数组，记录有多少条路径
对于当前点有四种更新情况:
1.if(距离<最短路) 更新最短路与次短路（包括路径数）
2.if(距离==最短路) 更新最短路路径数
3.if(距离<次小) 更新次短路（包括路径数）
4.if(距离==距离) 更新次短路路径数
#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <algorithm> #include <cstring> #include <stack> #include <cctype> #include <queue> #include <string> #include <vector> #include <set> #include <map> #include <climits> #define lson root<<1,l,mid #define rson root<<1|1,mid+1,r #define fi first #define se second #define seg int root,int l,int r #define ping(x,y) ((x-y)*(x-y)) #define mst(x,y) memset(x,y,sizeof(x)) #define mcp(x,y) memcpy(x,y,sizeof(y)) #define Min(x,y) (x<y?x:y) #define Max(x,y) (x>y?x:y) using namespace std; #define gamma 0.5772156649015328606065120 #define MOD 100000007 #define inf 0x3f3f3f3f #define N 1005 #define maxn 10001000 typedef long long LL; typedef pair<int,int> PII; int n,x,y; int vis[N][2],d[N][2]; int cnt[N][2]; int head[N]; struct Node{ int to,next,v; Node(int a=0,int b=0,int c=0){ to=a; next=b; v=c; } }node[N*10]; int ncnt; struct Edge{ int x,v,fl; Edge(int a=0,int b=0,int c=0):x(a),v(b),fl(c){} bool operator<(const Edge &a)const{ return v>a.v; } }temp,edge; inline void add(int x,int y,int v){ node[ncnt]=Node(y,head[x],v); head[x]=ncnt++; } void dijkstra(){ mst(vis,0); mst(d,inf); mst(cnt,0); cnt[x][0]=1; d[x][0]=0; priority_queue<Edge>q; q.push(Edge(x,0,0)); while(!q.empty()){ edge=q.top();q.pop(); if(vis[edge.x][edge.fl]) continue; int s=edge.x; int flag=edge.fl; vis[s][flag]=1; for(int i=head[s];~i;i=node[i].next){ int e=node[i].to; if(d[e][0]>node[i].v+d[s][flag]){ ///更新最短路与次短路 if(d[e][1]>d[e][0]){ d[e][1]=d[e][0]; cnt[e][1]=cnt[e][0]; q.push(Edge(e,d[e][1],1)); } d[e][0]=node[i].v+d[s][flag]; cnt[e][0]=cnt[s][flag]; q.push(Edge(e,d[e][0],0)); } else if(d[e][0]==node[i].v+d[s][flag]){ ///更新最短路路径数 cnt[e][0]+=cnt[s][flag]; } else if(d[e][1]>node[i].v+d[s][flag]){ ///更新次短路 d[e][1]=node[i].v+d[s][flag]; cnt[e][1]=cnt[s][flag]; q.push(Edge(e,d[e][1],1)); } else if(d[e][1]==node[i].v+d[s][flag]){ ///更新次短路路径数 cnt[e][1]+=cnt[s][flag]; } } } } int main(){ int i,j,group,k,m,v; scanf("%d",&group); while(group--){ mst(head,-1); ncnt=0; scanf("%d%d",&n,&m); while(m--){ scanf("%d%d%d",&x,&y,&v); add(x,y,v); } scanf("%d%d",&x,&y); dijkstra(); int ans=cnt[y][0]; if(d[y][0]+1==d[y][1]) ans+=cnt[y][1]; printf("%d ",ans); } return 0; }