题目链接：https://www.luogu.org/problemnew/show/P1608

补上一发最短路计数！

感谢王强qwqqqq @Lance1ot

#include <queue>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int maxn = 200010;

int dis[maxn], ans[maxn], n, m, k, used[2010][2010];

bool vis[maxn];

struct edge{

    int next, to, len;

}e[maxn<<2];

int head[maxn], cnt;

queue<int> q;

void add(int u, int v, int w)

{

    e[++cnt].len = w;

    e[cnt].next = head[u];

    e[cnt].to = v;

    head[u] = cnt;

}

void SPFA()

{

    while(!q.empty())

    {

        int now = q.front(); q.pop();

        vis[now] = 0;

        if(now == n) continue;

        for(int i = head[now]; i != -1; i = e[i].next)

        {

            if(dis[e[i].to] == dis[now] + e[i].len)

            {

                ans[e[i].to] = (ans[e[i].to] + ans[now]);

                if(!vis[e[i].to])

                {

                    q.push(e[i].to);

                    vis[e[i].to] = 1;

                }

            }

            if(dis[e[i].to] > dis[now] + e[i].len)

            {

                dis[e[i].to] = dis[now] + e[i].len;

                ans[e[i].to] = ans[now];

                if(!vis[e[i].to])

                {

                    q.push(e[i].to);

                    vis[e[i].to] = 1;

                }

            }

        }

        ans[now]=0;

    }

}

int main()

{

        memset(head, -1, sizeof(head));

        memset(dis, 127, sizeof(dis));

        memset(used, 127, sizeof(used));

        while(!q.empty()) q.pop();

        scanf("%d%d",&n,&m);

        for(int i = 1; i <= m; i++)

        {

            int u, v, w;

            scanf("%d%d%d",&u,&v,&w);

            if(used[u][v] > w)

            {

                add(u, v, w);

                used[u][v] = w;

            }

        }

        dis[1] = 0;

        vis[1] = 1;

        ans[1] = 1;

        q.push(1);

        SPFA();

        if(dis[n] >= 2139062143) {printf("No answer\n"); return 0;}

        printf("%d %d\n",dis[n], ans[n]);

}