题意相似，建议还没做的先去做一下。

当你看完上一题，就已经对最短路计数大体有一个思想了，但是本题中没有说不保证没有重边和自环，那么开一个map数组记录一下就好了，自环的话我使用spfa解决的，那么我们就可以按部就班的写最短路计数了。

不过有个bug源自于spfa算法，见下图。

当你按spfa的手动模拟的时候你会发现到达5号点的路径有3条，但是其真实路径只有两条，我们应该在处理完每一个点后将这个点的路径数量清零(在其更新完其他点以后)，避免二次计算的时候再次累加。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;int i,j,m,n;int head[2001];int us[2001];int t[2001];int dis[2001];int a[2001][2001];queue
          
           q;int r(){ int aans=0; char ch=getchar(); while(ch<'0'||ch>'9') ch=getchar(); while(ch>='0'&&ch<='9') { aans*=10; aans+=ch-'0'; ch=getchar(); } return aans;}int spfa(int x){ q.push(x);dis[x]=0;t[x]=1; while(!q.empty()) { int x=q.front(); q.pop(); us[x]=0; if(x==n) continue; for(i=1;i<=n;i++) { if(dis[x]+a[x][i]==dis[i]) t[i]+=t[x]; if(dis[x]+a[x][i]