結果

問題 No.1812 Uribo Road
ユーザー lam6er
提出日時 2025-03-20 21:16:42
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,370 bytes
コンパイル時間 179 ms
コンパイル使用メモリ 82,488 KB
実行使用メモリ 85,712 KB
最終ジャッジ日時 2025-03-20 21:17:40
合計ジャッジ時間 9,963 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 8 TLE * 1 -- * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from heapq import heappush, heappop

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

    R = list(map(int, input[ptr:ptr+K]))
    ptr += K

    required_edges = { r: i for i, r in enumerate(R) }

    adj = [[] for _ in range(N+1)]
    for edge_idx in range(1, M+1):
        A = int(input[ptr]); ptr +=1
        B = int(input[ptr]); ptr +=1
        C = int(input[ptr]); ptr +=1
        adj[A].append( (B, C, edge_idx) )
        adj[B].append( (A, C, edge_idx) )

    INF = float('inf')
    full_mask = (1 << K) - 1
    dist = [ [INF]*(1<<K) for _ in range(N+1) ]
    dist[1][0] = 0
    heap = []
    heappush(heap, (0, 1, 0))

    while heap:
        cost, u, mask = heappop(heap)
        if u == N and mask == full_mask:
            print(cost)
            return
        if cost > dist[u][mask]:
            continue
        for (v, c, edge_idx) in adj[u]:
            new_mask = mask
            if edge_idx in required_edges:
                bit = required_edges[edge_idx]
                new_mask |= (1 << bit)
            new_cost = cost + c
            if new_cost < dist[v][new_mask]:
                dist[v][new_mask] = new_cost
                heappush(heap, (new_cost, v, new_mask))

    print(-1)

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