注意:この記事は未完成です。
ABC254 E - Small d and k
問題について
グラフとクエリが与えられます。
各クエリ 頂点$x$からの距離が$k$以下の頂点の番号の総和を求める に答えてください。
特殊な制約
- 各頂点の次数は3以下
- クエリの$k$は3以下
解説
よくよく考えるとクエリで使う頂点は最大でも$3^3=27$頂点である。これは全部調べればいい！
BFSをするとして、各クエリで頂点$x$からの距離を全頂点について管理するとメモリが足りない。
さあどうする…
連想配列を使えば必要な頂点だけ距離を求められる！
コード
from collections import defaultdict, deque
n, m = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(m):
a, b = map(int, input().split())
a -= 1
b -= 1
g[a].append(b)
g[b].append(a)
for _ in range(int(input())):
x, k = map(int, input().split())
x -= 1
di = defaultdict(lambda: -1)
di[x] = 0
q = deque([x])
while q:
p = q.popleft()
for i in g[p]:
if di[i] == -1:
if di[p] < k:
di[i] = di[p] + 1
q.append(i)
s = 0
for i in list(di.items()):
if i[1] != -1:
s += i[0] + 1
print(s)