shortestpath2.cpp

#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 5;
const int mod = 1e9 + 7;
vector<pair<int, int>> g[maxn], r[maxn];
long long d[2][maxn];
int u[maxn], v[maxn], w[maxn], way[2][maxn], dfn[maxn], low[maxn];

template <typename T>
using heap = priority_queue<T, vector<T>, greater<T>>;

void dijk(int s, vector<pair<int, int>> *g, int n) {
    static bool used[maxn];
    for (int i = 0; i < n; ++i) {
        used[i] = false;
        d[s][i] = 1e18;
    }

    heap<pair<long long, int>> pq;
    pq.emplace(0, s);
    d[s][s] = 0;
    way[s][s] = 1;

    while (!pq.empty()) {
        int x = pq.top().second;
        pq.pop();
        if (used[x]) continue;

        used[x] = true;
        for (int i = 0; i < (int)g[x].size(); ++i) {
            int u = g[x][i].first;
            int w = g[x][i].second;
            if (d[s][u] > d[s][x] + w) {
                d[s][u] = d[s][x] + w;
                way[s][u] = way[s][x];
                pq.emplace(d[s][u], u);
            } else if (d[s][u] == d[s][x] + w) {
                (way[s][u] += way[s][x]) %= mod;
            }
        }
    }
}

int dfs2(int x, int p) {
    static int tk = 0;
    dfn[x] = low[x] = tk++;
    int res = 0;

    for (int i = 0; i < (int)g[x].size(); ++i) {
        int u = g[x][i].first;
        if (u == p) continue;

        if (dfn[u] == -1) {
            res += dfs2(u, x);
            low[x] = min(low[x], low[u]);
        } else {
            low[x] = min(low[x], dfn[u]);
        }
    }

    if (low[x] == dfn[x] && p != -1) ++res;
    return res;
}

int main() {
    int n, m; scanf("%d%d", &n, &m);
    for (int i = 0; i < m; ++i) {
        scanf("%d%d%d", &u[i], &v[i], &w[i]);
        --u[i], --v[i];
        g[u[i]].emplace_back(v[i], w[i]);
        r[v[i]].emplace_back(u[i], w[i]);
    }

    dijk(0, g, n);
    dijk(1, r, n);

    printf("%lld\n", d[0][1]);
    printf("%d\n", way[0][1]);

    for (int i = 0; i < n; ++i) g[i].clear();
    for (int i = 0; i < m; ++i) {
        if (d[0][u[i]] + w[i] + d[1][v[i]] == d[0][1]) {
            g[u[i]].emplace_back(v[i], w[i]);
            g[v[i]].emplace_back(u[i], w[i]);
        }
    }

    for (int i = 0; i < n; ++i) dfn[i] = -1;
    printf("%d\n", dfs2(0, -1));
}