提出 #6258354

---

ソースコード 拡げる

import sys
input = sys.stdin.readline
from heapq import heappop, heappush

"""
Bをなるべく使わない行き方を考える
そこから比べてBを増やす利点が少ない
使うBを増やしても距離がNまでしか改善しない
x*(x+1)//2 < N
sqrt(2N) くらいまでしか無駄なBを増やさないようにする
"""

N,M = map(int,input().split())
edge_A = [[] for _ in range(N)]
edge_B = [[] for _ in range(N)]
for _ in range(M):
    c,a,b = map(int,input().split())
    if c == 0:
        edge_A[a].append(b)
        edge_A[b].append(a)
    else:
        edge_B[a].append(b)
        edge_B[b].append(a)

INF = 10 ** 9

# まず、Bの最小回数を求める
min_B = [INF] * N
q = [(0,0)] # Bの回数、場所
min_B[0] = 0
while q:
    bx,x = heappop(q)
    if min_B[x] < bx:
        continue
    for y in edge_A[x]:
        by = bx
        if min_B[y] <= by:
            continue
        min_B[y] = by
        heappush(q, (by,y))
    for y in edge_B[x]:
        by = bx + 1
        if min_B[y] <= by:
            continue
        min_B[y] = by
        heappush(q, (by,y))  

B_plus = int((2*N) ** .5 + 10)

INF = 10 ** 9
dist = [[INF] * B_plus for _ in range(N)]
q = [(0,0)] # 場所、Bの回数
dist[0][0] = 0
d = 0
while q:
    d += 1
    qq = []
    for x,bx in q:
        for y in edge_A[x]:
            my = min_B[y]
            by = bx
            if by >= my + B_plus or dist[y][by-my] != INF:
                continue
            dist[y][by-my] = d
            qq.append((y,by))
        for y in edge_B[x]:
            my = min_B[y]
            by = bx + 1
            if by >= my + B_plus or dist[y][by-my] != INF:
                continue
            dist[y][by-my] = d
            qq.append((y,by))
    q = qq

answer = [min((ab-b) + b*(b+1)//2 for b,ab in zip(range(mb,mb+B_plus), d)) for mb, d in zip(min_B, dist)]

print('\n'.join(map(str,answer)))

提出情報

ジャッジ結果