【ACWing】3488. 最短路径

题目地址：

https://www.acwing.com/problem/content/description/3491/

$N$个城市，标号从$0$到$N-1$，$M$条道路，第$K$条道路（$K$从$0$开始）的长度为$2K$，求编号为$0$的城市到其他城市的最短距离。

输入格式：
第一行两个正整数$N,M$，表示有$N$个城市，$M$条道路。
接下来$M$行两个整数，表示相连的两个城市的编号。

输出格式：
$N-1$行，表示$0$号城市到其他城市的最短路，如果无法到达，输出$-1$，数值太大的以$\mathrm{mod}100000$的结果输出。

数据范围：
$2\le N\le 100$
$1\le M\le 500$

由${\sum }_{i=0}^k{2}^i<2^{k+1}$，所以在建图的时候，如果当前加的边是$(a,b)$，并且在未加当前边的时候，$a$和$b$已经连通了，那么当前边是不可能出现在$0$到某个顶点的最短路上的（因为走$(a,b)$这条边不如绕路）。由此可知，不加这些非必要边的情况下，整个图实际上是一棵树，这样$0$到任意点路径唯一，从而可以直接DFS来做。代码如下：

#include 
#include 
using namespace std;

const int N = 110, M = 1010, MOD = 1e5;
int n, m;
int h[N], e[M], ne[M], w[M], idx;
int p[N];
int dist[N];

int find(int x) {
  if (p[x] != x) p[x] = find(p[x]);
  return p[x];
}

void add(int a, int b, int c) {
  e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

void dfs(int u, int from, int d) {
  dist[u] = d;
  for (int i = h[u]; ~i; i = ne[i]) {
    int v = e[i];
    if (v == from) continue;
    dfs(v, u, (d + w[i]) % MOD);
  }
}

int main() {
  memset(h, -1, sizeof h);
  memset(dist, -1, sizeof dist);
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++) p[i] = i;
  for (int i = 1, len = 1; i <= m; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    int pa = find(a), pb = find(b);
    if (pa != pb) {
      add(a, b, len), add(b, a, len);
      p[pa] = pb;
    }
    len = len * 2 % MOD;
  }

  dfs(0, -1, 0);
  for (int i = 1; i < n; i++) printf("%d\n", dist[i]);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

时间复杂度$O(m{\log }^{\ast }n+n)$，空间$O(n)$。