Day 159-Q1 — 2026-09-24 — Pruned Landmark Labeling（枝刈りランドマークラベリング・2-hop ラベルによる最短距離クエリ）

📋 コピーimport sys
from collections import deque


def main():
    data = sys.stdin.buffer.read().split()
    n, m, q = int(data[0]), int(data[1]), int(data[2])
    adj = [[] for _ in range(n)]
    pos = 3
    for _ in range(m):
        a = int(data[pos]) - 1; b = int(data[pos + 1]) - 1; pos += 2
        adj[a].append(b); adj[b].append(a)

    # 1. ランドマーク順序: 次数降順（原論文の既定）
    order = sorted(range(n), key=lambda v: -len(adj[v]))

    # 2. 枝刈り BFS でラベル構築
    labels = [dict() for _ in range(n)]   # labels[u] = {landmark_rank: dist}
    INF = 1 << 30
    dist = [INF] * n
    for k, s in enumerate(order):
        ls = labels[s]
        dist[s] = 0
        dq = deque([s]); visited = [s]
        while dq:
            u = dq.popleft(); d = dist[u]
            lu = labels[u]
            best = INF                      # query(s, u) を既存ラベルだけで計算
            for w, dw in lu.items():
                dv = ls.get(w)
                if dv is not None and dv + dw < best:
                    best = dv + dw
            if best <= d:
                continue                    # 枝刈り
            lu[k] = d
            for v in adj[u]:
                if dist[v] == INF:
                    dist[v] = d + 1; dq.append(v); visited.append(v)
        for v in visited:                   # dist を O(訪問数) で初期化し直す
            dist[v] = INF

    # 3. クエリ: 共通ランドマーク上の最小値
    out = []
    for _ in range(q):
        u = int(data[pos]) - 1; v = int(data[pos + 1]) - 1; pos += 2
        lu, lv = labels[u], labels[v]
        if len(lu) > len(lv):
            lu, lv = lv, lu
        best = -1
        for w, du in lu.items():
            dv = lv.get(w)
            if dv is not None:
                d = du + dv
                if best < 0 or d < best:
                    best = d
        out.append(best)
    sys.stdout.write("\n".join(map(str, out)) + "\n")


main()