最短路计数

C++(g++ 7.5.0) 解法, 执行用时: 327ms, 内存消耗: 8168K, 提交时间: 2023-03-17 17:06:53

#include<iostream>
#include<vector>
#include<queue>

int ans[1000005], len[1000005];
bool vis[1000005];

const int mod = 1e5 + 3;

int main() {
    int n, m;
    std::cin >> n >> m;
    ans[1] = 1;
    std::vector<std::vector<int>> edge(n + 1);
    for (int i = 1; i <= m; i++) {
        int u, v;
        std::cin >> u >> v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    std::queue<int> q;
    q.push(1);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (auto to: edge[u]) {
            if (!vis[to]) {
                vis[to] = 1;
                len[to] = len[u] + 1;
                q.push(to);
            }
            if (len[to] == len[u] + 1) {
                ans[to] = (ans[to] + ans[u]) % mod;
            }
        }
    }
    ans[1] = 1;
    for (int i = 1; i <= n; i++)
        std::cout << ans[i] << std::endl;
    return 0;
}

C++14(g++5.4) 解法, 执行用时: 371ms, 内存消耗: 8416K, 提交时间: 2019-12-28 20:42:43

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;

const int MAXN = 1e5+1;
const int MOD = 1e5+3;
vector<int> G[MAXN];
int dis[MAXN];
int ways[MAXN];

int main() {
  int N, M; cin >> N >> M;
  while (M--) {
    int u, v; cin >> u >> v;
    G[u].push_back(v);
    G[v].push_back(u);
  }
  memset(dis, 0x3f, sizeof(dis));
  priority_queue<pii, vector<pii>, greater<pii> > Q;
  Q.push({0, 1});
  dis[1] = 0;
  ways[1] = 1;
  while (!Q.empty()) {
    auto s = Q.top().second;
    auto d = Q.top().first;
    Q.pop();
    if (dis[s] > d) continue;
    for (auto t: G[s]) {
      if (dis[t] > dis[s] + 1) {
        dis[t] = dis[s] + 1;
        ways[t] = ways[s];
        Q.push({dis[t], t});
      } else if (dis[t] == dis[s] + 1) {
        ways[t] += ways[s];
        ways[t] %= MOD;
      }
    }
  }
  for (int i = 1; i <= N; i++) {
    cout << ways[i] << endl;
  }
}

C++ 解法, 执行用时: 294ms, 内存消耗: 29176K, 提交时间: 2021-11-29 19:48:01

#include<iostream>
#include<vector>
#include<bitset>
#include<queue>
using namespace std;
vector<int>g[1000001];
int d[1000001], cnt[1000001];
bitset<1000001>vis;
int n, m;
void bfs() {
	queue<int>q;
	d[1] = 0;
	vis[1] = cnt[1] = 1;
	q.push(1);
	while (q.size()) {
		int x = q.front(); q.pop();
		for (int i = 0; i < g[x].size(); i++) {
			int t = g[x][i];
			if (!vis[t]) { 
				q.push(t);
				vis[t] = 1; 
				d[t] = d[x] + 1;
			}
			if (d[t] == d[x] + 1)
				cnt[t] = (cnt[t] + cnt[x]) % 100003;
		}
	}
}
int main() {
	cin >> n >> m;
	while (m--) {
		int u, v; cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	bfs();
	for (int i = 1; i <= n; i++)
		cout << cnt[i] << endl;
	return 0;
}

详情