传送门
哎。。。心累。。。这道题改了好久
做法很好理解，就是运用dp的思想，设cnt[i]为到第i个点的最短路数量。
那么对于i的每条出边，如果zdl[i]+val=zdl[vis]，说明还有另外若干条可以从i到达vis的路径，因此cnt[vis]+=cnt[i]
大概是下图这样的一个意思
当然，如果zdl[i]+val<zdl[vis]的话，直接cnt[vis]=cnt[i]即可。
写代码的时候需要注意的几点：
memset(63)才不会炸，如果是(127)这样的极值的话，会出现奇奇怪怪的错误!!!因为这样加起来会爆int...
spfa入队的地方也要改变，必须放在第二个if的外面，因为有可能第一个if会push一些点进去。
cnt数组的值一旦把贡献全部算好就清空，比如如下这个反例，可以手推一下。
#include<bits/stdc++.h> #define N 2005 using namespace std; int n,m,dis[N][N],zdl[N],cnt[N]; bool inque[N]; queue <int> q; void spfa(int s) { memset(zdl,63,sizeof(zdl)); q.push(s); zdl[s]=0; cnt[s]=1; inque[s]=true; while(!q.empty()) { int now=q.front(); q.pop(); inque[now]=false; if(now==n) continue; for(int i=1;i<=n;i++) { if(zdl[now]+dis[now][i]==zdl[i]) { cnt[i]+=cnt[now]; } if(zdl[now]+dis[now][i]<zdl[i]) { zdl[i]=zdl[now]+dis[now][i]; cnt[i]=cnt[now]; } if(!inque[i]&&cnt[i]) { inque[i]=true; q.push(i); } } cnt[now]=0; } } int main() { ios::sync_with_stdio(false); cin.tie(NULL),cout.tie(NULL); cin>>n>>m; memset(dis,63,sizeof(dis)); for(int i=1;i<=m;i++) { int x,y,z; cin>>x>>y>>z; dis[x][y]=min(dis[x][y],z); } spfa(1); if(zdl[n]==dis[0][0]) cout<<"No answer"; else cout<<zdl[n]<<" "<<cnt[n]; return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9490609.html
