結果

問題 No.1480 Many Complete Graphs
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 16:12:07
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,867 bytes
コンパイル時間 231 ms
コンパイル使用メモリ 82,636 KB
実行使用メモリ 106,676 KB
最終ジャッジ日時 2025-06-12 16:12:31
合計ジャッジ時間 13,288 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 42 WA * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq
from collections import defaultdict

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    ptr = 0
    N = int(data[ptr])
    ptr += 1
    M = int(data[ptr])
    ptr += 1

    s1_list = [[] for _ in range(N + 1)]  # s1_list[u] contains (s1, c_i) for each subset including u
    s1_map = defaultdict(list)  # s1_map[s1] contains (c_i, others) for each subset where s1 is the smallest

    for _ in range(M):
        k_i = int(data[ptr])
        ptr += 1
        c_i = int(data[ptr])
        ptr += 1
        s_list = list(map(int, data[ptr:ptr + k_i]))
        ptr += k_i
        s_1 = s_list[0]
        others = s_list[1:]
        s1_map[s_1].append((c_i, others))
        for u in s_list:
            s1_list[u].append((s_1, c_i))

    # Dijkstra's algorithm setup
    INF = float('inf')
    distance = [INF] * (N + 1)
    distance[1] = 0
    heap = []
    heapq.heappush(heap, (0, 1))

    visited = [False] * (N + 1)

    while heap:
        dist_u, u = heapq.heappop(heap)
        if visited[u]:
            continue
        visited[u] = True

        if u == N:
            print(dist_u)
            return

        # Process all subsets where u is the smallest (s_1)
        for c_i, others in s1_map.get(u, []):
            for v in others:
                w = (u + v + 1) // 2 + c_i
                if distance[v] > dist_u + w:
                    distance[v] = dist_u + w
                    heapq.heappush(heap, (distance[v], v))

        # Process all (s1, c_i) in s1_list[u]
        for s1, c_i in s1_list[u]:
            if s1 != u:
                w = (u + s1 + 1) // 2 + c_i
                if distance[s1] > dist_u + w:
                    distance[s1] = dist_u + w
                    heapq.heappush(heap, (distance[s1], s1))

    # If N was not reached
    print(-1)

if __name__ == "__main__":
    main()
0