最短路计数 最短路径有几条

最短路路径数 T3 最短路计数 - 洛谷 P1144 - Virtual Judge (csgrandeur.cn)

题目描述

给出一个 $N$ 个顶点 $M$ 条边的无向无权图，顶点编号为 $1\sim N$。问从顶点 $1$ 开始，到其他每个点的最短路有几条。

输入格式

第一行包含 $2$ 个正整数 $N,M$，为图的顶点数与边数。

接下来 $M$ 行，每行 $2$ 个正整数 $x,y$，表示有一条由顶点 $x$ 连向顶点 $y$ 的边，请注意可能有自环与重边。

输出格式

共 $N$ 行，每行一个非负整数，第 $i$ 行输出从顶点 $1$ 到顶点 $i$ 有多少条不同的最短路，由于答案有可能会很大，你只需要输出 $ans\mathrm{mod}100003$ 后的结果即可。如果无法到达顶点 $i$ 则输出 $0$。

样例 #1

样例输入 #1

5 7
1 2
1 3
2 4
3 4
2 3
4 5
4 5

样例输出 #1

1
1
1
2
4

提示

$1$ 到 $5$ 的最短路有 $4$ 条，分别为 $2$ 条 $1\to 2\to 4\to 5$ 和 $2$ 条 $1\to 3\to 4\to 5$（由于 $4\to 5$ 的边有 $2$ 条）。

对于 $20\%$ 的数据，$1\le N\le 100$；
对于 $60\%$ 的数据，$1\le N\le 10^3$；
对于 $100\%$ 的数据，$1\le N\le 10^6$，$1\le M\le 2\times 10^6$。

思路

类似于DP求最大值的方案数, 定义一个数组g记录方案数。 当更新时f[i] == f[j]最小值不变, 则相加g[i] += g[j]；若更新时f[j] < f[i], 则更新 g[j] = g[i]。

代码

#define S second
#define F first
#define pb push_back
#define pf push_front
#define lson l, mid, u << 1
#define rson mid + 1, r, u << 1 | 1
#define MID l + r >> 1
#define mem(x, n) memset(x, n, sizeof x)
#define setPrec(n) cout << fixed << setpricision(n)
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
using i64 = long long;
// #define debug
const int N = 1e6 + 10, M = 4e6 + 10, MOD = 1e5 + 3;
int h[N], e[M], ne[M], idx;
int dist[N], g[N];
bool st[N];
int n, m;
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
 
void solve()
{
    mem(dist, 0x3f);
    mem(g, 0);
    mem(st, 0);
    priority_queue<PII, vector<PII>, greater<PII>> q;
    q.push({0, 1});
    dist[1] = 0;
    g[1] = 1;
    while (q.size())
    {
        auto t = q.top();
        q.pop();
 
        int ver = t.S, d = t.F;
        if (st[ver])
            continue;
        st[ver] = true;
 
        for (int i = h[ver]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > d + 1)
            {
                dist[j] = d + 1;
                g[j] = g[ver];
                q.push({dist[j], j});
            }
            else if (dist[j] == d + 1)
                g[j] = (g[ver] + g[j]) % MOD;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        if (dist[i] == 0x3f3f3f3f3f)
            cout << 0 << endl;
        else
            cout << g[i] << endl;
    }
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    while (cin >> n >> m)
    {
        mem(h, -1);
        for (int i = 0; i < m; i++)
        {
            int a, b;
            cin >> a >> b;
            add(a, b), add(b, a);
        }
        solve();
    }
    return 0;
}