結果

問題 No.1814 Uribo Road (Easy)
ユーザー lam6er
提出日時 2025-03-20 21:04:37
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 219 ms / 2,000 ms
コード長 1,563 bytes
コンパイル時間 211 ms
コンパイル使用メモリ 82,280 KB
実行使用メモリ 87,076 KB
最終ジャッジ日時 2025-03-20 21:04:50
合計ジャッジ時間 5,846 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 44
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    N = int(data[idx])
    idx +=1
    M = int(data[idx])
    idx +=1
    K = int(data[idx])
    idx +=1
    
    R = list(map(int, data[idx:idx+K]))
    idx += K
    
    R_map = {}
    for i in range(K):
        road_idx = R[i]
        R_map[road_idx] = i
    
    adj = [[] for _ in range(N+1)]
    roads = []
    for j in range(M):
        A = int(data[idx])
        idx +=1
        B = int(data[idx])
        idx +=1
        C = int(data[idx])
        idx +=1
        adj[A].append((B, C, j+1))  # roads are 1-based
        adj[B].append((A, C, j+1))
    
    target_mask = (1 << K) -1
    INF = float('inf')
    distance = [[INF] * (1 << K) for _ in range(N+1)]
    distance[1][0] = 0
    
    heap = []
    heapq.heappush(heap, (0, 1, 0))
    
    found = False
    
    while heap:
        d, u, mask = heapq.heappop(heap)
        if u == N and mask == target_mask:
            print(d)
            found = True
            break
        if d > distance[u][mask]:
            continue
        for (v, cost, road_j) in adj[u]:
            if road_j in R_map:
                bit = R_map[road_j]
                new_mask = mask | (1 << bit)
            else:
                new_mask = mask
            new_d = d + cost
            if new_d < distance[v][new_mask]:
                distance[v][new_mask] = new_d
                heapq.heappush(heap, (new_d, v, new_mask))
    
    if not found:
        print(-1)

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