题意

最短路计数

数据范围：$1 \le n \le 2000,0 \le m \le n(n-1)$

题解

在跑最短路的同时维护一个$cnt[i]$即可

• 若能够更新$dis[v]$，则$cnt[v]=cnt[u]$
• 若相等，则$cnt[v]+=cnt[u]$

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
#define mp make_pair
typedef pair<int,int> pii;
const int N=2000+10;
const int INF=0x3f3f3f3f;
int n,m,u,v,w;
int cnt;
int G[N][N],dis[N],ans[N];
inline void Dijkstra(){
    priority_queue<pii,vector<pii>,greater<pii> > pq;
    memset(dis,0x3f,sizeof(dis));
    pq.push(mp(0,1));
    dis[1]=0;
    ans[1]=1;
    for(;!pq.empty();){
        int d=pq.top().first,u=pq.top().second;
        pq.pop();
        if(dis[u]!=d)
            continue;
        for(int v=1;v<=n;v++){
            if(G[u][v]==INF)
                continue;
            if(dis[v]>d+G[u][v]){
                dis[v]=d+G[u][v];
                ans[v]=ans[u];
                pq.push(mp(dis[v],v));
            }
            else if(dis[v]==d+G[u][v])
                ans[v]+=ans[u];
        }
    }
}
int main(){
    memset(G,0x3f,sizeof(G));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&u,&v,&w);
        G[u][v]=min(G[u][v],w);
    }
    Dijkstra();
    if(dis[n]!=INF)
        printf("%d %d",dis[n],ans[n]);
    else puts("No answer");
    return 0;
}