題目描述

給出一個 $N$ 個頂點 $M$ 條邊的無向無權(quán)圖。

問從頂點 $1$ 開始，到其他每個點的最短路有幾條。

輸入格式

第 $1$ 行包含兩個正整數(shù) $N$，$M$。

接下來 $M$ 行，每行兩個正整數(shù) $x,y$表示存在一條由頂點 $x$ 到頂點 $y$ 的邊。（可能存在重邊和自環(huán)）

輸出格式

輸出 $N$ 行，每行一個非負(fù)整數(shù)。

第 $i$ 行輸出從頂點 $1$ 到頂點 $i$ 的不同最短路個數(shù)。

由于數(shù)據(jù)可能很大，你只需要輸出 $ansmod100003$ 的結(jié)果。

若頂點 $1$ 不能到達頂點 $i$，請輸出 $0$。

樣例輸入

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

樣例輸出

1
1
1
2
4

數(shù)據(jù)范圍

$1\le N\le 10^6$，$1\le M\le 2\times 10^6$

提示

由于數(shù)據(jù)量較大，請使用較為快速的輸入/輸出方式。

解題思路

根據(jù)數(shù)據(jù)范圍，我們估計算法的復(fù)雜度至多是$O(N)$，因此想到了動態(tài)規(guī)劃：

對于節(jié)點$i$，有若干個節(jié)點與之相連，在與之相連的節(jié)點當(dāng)中從$1$到$k_1,k_2,...,k_n$節(jié)點的路徑長度相同且最短，那么我們計算得出，從$1$到節(jié)點$i$的最短路徑數(shù)為$num[k_1]+num[k_2]+...+num[k_n]$。

以上是思路的主體部分，接下來實現(xiàn)代碼：

數(shù)據(jù)量龐大，同時也是因為存在重邊，故不能采用二維數(shù)組存圖，因此采用鏈?zhǔn)角跋蛐恰?/p>

對于代碼主體部分，維護一個隊列與一個路徑長度的數(shù)組。

初始化將$1$節(jié)點加入隊列，然后不斷嘗試到達新的節(jié)點。

void solve() {
	q.push(1);
	while (!q.empty()) {
		int node = q.front(); q.pop();
		
		for (int i = head[node]; i != -1; i = edges[i].next) {
			int v = edges[i].v;
			q.push(v);
		}
	}
}

利用隊列元素先進先出的特點，我們可以保證，隊首的節(jié)點永遠是距離$1$最近的節(jié)點。

進而我們可以保證，用隊首去更新路徑長度，得到的一定是最短路徑長度。

void solve() {
	q.push(1);
	path[1] = 0;

	while (!q.empty()) {
		int node = q.front(); q.pop();
		int path_len = path[node] + 1;
		
		for (int i = head[node]; i != -1; i = edges[i].next) {
			int v = edges[i].v;
			if (path_len > path[v]) continue;
			if (path[v] == NaN) {//NaN代表無窮大，即為未到達的節(jié)點
				path[v] = path_len;
				q.push(v);
			}
		}
	}
}

以此為基礎(chǔ)，很容易實現(xiàn)最初的思想：

void solve() {
	q.push(1);
	path[1] = 0;
	sum[1] = 1LL;

	while (!q.empty()) {
		int node = q.front(); q.pop();

		int path_len = path[node] + 1;
		
		for (int i = head[node]; i != -1; i = edges[i].next) {
			int v = edges[i].v;
			if (path_len > path[v]) continue;
			sum[v] = (sum[v] + sum[node]) % mod_num;
			if (path[v] == NaN) {
				path[v] = path_len;
				q.push(v);
			}
		}
	}
}

最后，AC代碼如下：文章來源地址http://www.zghlxwxcb.cn/news/detail-421576.html

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <queue>
#include <string.h>
using namespace std;
const int max_n = 1e6;
const int max_m = 2e6;
const int NaN = 0x3F3F3F3F;
const long long mod_num = 100003;

struct edge { int v, next; }edges[2 * max_m];
int tot = -1, head[max_n + 1], path[max_n + 1];
queue<int>q;
long long sum[max_n + 1];

void add_edge(int u, int v) {
	edges[++tot] = { v, head[u] }; head[u] = tot;
	edges[++tot] = { u, head[v] }; head[v] = tot;
}

void solve() {
	q.push(1);
	path[1] = 0;
	sum[1] = 1LL;

	while (!q.empty()) {
		int node = q.front(); q.pop();

		int path_len = path[node] + 1;
		
		for (int i = head[node]; i != -1; i = edges[i].next) {
			int v = edges[i].v;
			if (path_len > path[v]) continue;
			sum[v] = (sum[v] + sum[node]) % mod_num;
			if (path[v] == NaN) {
				path[v] = path_len;
				q.push(v);
			}
		}
	}
}

int main() {
	memset(head, -1, sizeof(int) * (max_n + 1));
	memset(path, 0x3F, sizeof(int) * (max_n + 1));
	int n, m;
	scanf("%d%d", &n, &m);
	//cin >> n >> m;
	int u, v;
	for (int i = 0; i < m; i++) {
		scanf("%d%d", &u, &v);
		//cin >> u >> v;
		add_edge(u, v);
	}

	solve();
	for (int i = 1; i <= n; i++) {
		printf("%lld\n", sum[i]);
	}
	return 0;
}

到了這里，關(guān)于[Daimayuan] 最短路計數(shù)（C++，DP，圖論）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！