luogu1608 路径统计 (spfa)

题意：给一个有向图（无零边），要求找出最短路的数量（重边只计算一次）
做spfa的时候，记一个cnt
对于u-w->v如果dis[u]+w=dis[v],cnt[v]+=cnt[u]
如果dis[u]+w<dis[v],cnt[v]=cnt[u]
要注意的是，不论是大于还是等于，都需要把v加到队列里继续去更新
（如果等于时不加，那么有可能v这个点在增加u->v之前更新过后面的点，这个后面的点就不会加从u来的路径）
那既然等于时也要加入队列，那么有可能一个点就会给后面的更新两次，那么在更新过一次后直接把cnt[u]给成0即可
然而不能让N这个点被给成0，其实N这个点根本就没必要被加入队列，发现有N的时候跳过即可
最后答案就是cnt[N]

 

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=2020;
int rd(){
int x=0;char c=getchar();
while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
return x;
}
struct Edge{
int a,b,l,ne;
}eg[maxn*maxn];
int N,M,egh[maxn],ect;
int eg2[maxn][maxn];
int ans[maxn];
int dis[maxn];bool flag[maxn];
queue<int> q;
void adeg(int a,int b,int l){
eg[ect].a=a;eg[ect].b=b;eg[ect].l=l;eg[ect].ne=egh[a];
eg2[a][b]=l;egh[a]=ect++;
}
void spfa(){
memset(dis,127,sizeof(dis));
dis[1]=0;ans[1]=1;q.push(1);
while(!q.empty()){
int p=q.front();q.pop();flag[p]=0;
if(p==N) continue;
for(int i=egh[p];i!=-1;i=eg[i].ne){
int j=eg[i].b;
if(dis[j]==dis[p]+eg[i].l){
ans[j]+=ans[p];
if(!flag[j]) q.push(j);flag[j]=1;
}
if(dis[j]>dis[p]+eg[i].l){
dis[j]=dis[p]+eg[i].l;
ans[j]=ans[p];
if(!flag[j]) q.push(j);flag[j]=1;
}
}ans[p]=0;
}
}
int main(){
int i,j,k;
N=rd();M=rd();
memset(egh,-1,sizeof(egh));memset(eg2,127,sizeof(eg2));
for(i=1;i<=M;i++){
int a=rd(),b=rd(),c=rd();
if(eg2[a][b]>c) adeg(a,b,c);
}
spfa();
if(dis[N]>10*N) printf("No answern");
else printf("%d %dn",dis[N],ans[N]);
}