思路：先跑一遍 spfa 求最短路，再用一次 bfs 算方案数。

#include <queue>
#include <cstdio>
#include <cstring>
#include <utility>
#include <algorithm>
using namespace std;
typedef pair<int,int> node;
typedef long long LL;
template<int N,int M,class T=int> struct graph{
    struct edge{
        int u,v;T w;
        edge(int u=0,int v=0,T w=0):
            u(u),v(v),w(w){}
    };
    edge e[M*2+10];
    int head[N+10],nxt[M*2+10],cnt;
    graph(){clear();}
    edge operator[](int i){return e[i];}
    void clear(){cnt=0,memset(head,0,sizeof head);}
    void add(int u,int v,T w=0){
        e[++cnt]=edge(u,v,w);
        nxt[cnt]=head[u];
        head[u]=cnt;
    }
    void link(int u,int v,T w=0){
        add(u,v,w);
        add(v,u,w);
    }
};
int n,m,s;
graph<10010,200010> g;
int dis[10010],f[10010];
bool vis[10010];
queue<int> q;
void spfa(int s){
    memset(dis,0x7f,sizeof dis);
    dis[s]=0;
    q.push(s);
    while(!q.empty()){
        int u=q.front();q.pop();
        vis[u]=0;
        for(int i=g.head[u];i;i=g.nxt[i]){
            int v=g[i].v,w=g[i].w;
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                if(!vis[v]) vis[v]=1,q.push(v);
            }
        }
    }
}
void bfs(int s){
    q=queue<int>();
    memset(vis,0,sizeof vis);
    f[s]=1;
    q.push(s);
    while(!q.empty()){
        int u=q.front();q.pop();
        vis[u]=0;
        for(int i=g.head[u];i;i=g.nxt[i]){
            int v=g[i].v,w=g[i].w;
            if(dis[u]+w==dis[v]){
                f[v]+=f[u];
                if(!vis[v]) vis[v]=1,q.push(v);
            }
        }
    }
}
int minw[2010][2010];
int main(){
    memset(minw,0x3f,sizeof minw);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        minw[u][v]=min(minw[u][v],w);
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(minw[i][j]!=minw[0][0]) g.add(i,j,minw[i][j]);
        }
    }
    spfa(1);
    bfs(1);
    if(dis[n]==dis[0]) printf("No answer\n");
    else printf("%d %d\n",dis[n],f[n]);
    return 0;
}

这样写为什么会 WA 呢？