luogu 1608 路径统计--最短路计数
https://www.luogu.org/problemnew/show/P1608
题意https://www.cnblogs.com/rmy020718/p/9440588.html相似，建议还没做的先去做一下。
当你看完上一题，就已经对最短路计数大体有一个思想了，但是本题中没有说不保证没有重边和自环，那么开一个map数组记录一下就好了，自环的话我使用spfa解决的，那么我们就可以按部就班的写最短路计数了。
不过有个bug源自于spfa算法，见下图。
当你按spfa的手动模拟的时候你会发现到达5号点的路径有3条，但是其真实路径只有两条，我们应该在处理完每一个点后将这个点的路径数量清零(在其更新完其他点以后)，避免二次计算的时候再次累加。
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<queue> 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<int>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]<dis[i]) { dis[i]=dis[x]+a[x][i]; t[i]=t[x]; } if(t[i]&&!us[i]) us[i]=1,q.push(i); } t[x]=0; } } int main() { n=r(),m=r(); int x,y,z; memset(a,63,sizeof(a)); memset(dis,63,sizeof(dis)); for(i=1;i<=m;i++) { x=r(),y=r(),z=r(); if(a[x][y])a[x][y]=min(z,a[x][y]); else a[x][y]=z; } spfa(1); if(dis[n]!=a[0][0])cout<<dis[n]<<" "<<t[n]<<endl; else cout<<"No answer"<<endl; return 0; }