ABC252E - Road Reduction

考え方

ある頂点から他の頂点への最短経路を求めると，最短経路からなる集合は木になる（最短経路木）．
よって，最短経路で通る辺を列挙すれば良い．

回答例

import heapq

N, M = map(int, input().split())
G = [[] for _ in range(N)]
E = {}
for i in range(M):
    A, B, C = map(int, input().split())
    A -= 1
    B -= 1
    G[A].append((B, C))
    G[B].append((A, C))
    E[(A, B)] = i + 1
    E[(B, A)] = i + 1


dist = [1 << 60] * N
dist[0] = 0
q = [(0, 0)]
prev = [-1] * N
while q:
    d, cur = heapq.heappop(q)
    if dist[cur] < d: continue
    for chi, cost in G[cur]:
        if dist[cur] + cost < dist[chi]:
            dist[chi] = dist[cur] + cost
            prev[chi] = cur
            heapq.heappush(q, (dist[chi], chi))

ans = set()
for i in range(1, N):
    ans.add(E[(prev[i], i)])

print(*ans)