题意：给一个有向图（无零边），要求找出最短路的数量（重边只计算一次）
做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=; int rd(){
int x=;char c=getchar();
while(c<''||c>'') c=getchar();
while(c>=''&&c<='') x=x*+c-'',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,,sizeof(dis));
dis[]=;ans[]=;q.push();
while(!q.empty()){
int p=q.front();q.pop();flag[p]=;
if(p==N) continue;
for(int i=egh[p];i!=-;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]=;
}
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]=;
}
}ans[p]=;
}
} int main(){
int i,j,k;
N=rd();M=rd();
memset(egh,-,sizeof(egh));memset(eg2,,sizeof(eg2));
for(i=;i<=M;i++){
int a=rd(),b=rd(),c=rd();
if(eg2[a][b]>c) adeg(a,b,c);
}
spfa();
if(dis[N]>*N) printf("No answer\n");
else printf("%d %d\n",dis[N],ans[N]);
}