結果

問題 No.1812 Uribo Road
ユーザー tamatotamato
提出日時 2022-01-14 22:14:03
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,607 bytes
コンパイル時間 151 ms
コンパイル使用メモリ 82,508 KB
実行使用メモリ 1,112,148 KB
最終ジャッジ日時 2024-11-20 11:13:03
合計ジャッジ時間 69,921 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 16 TLE * 9 MLE * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline
    import heapq

    def dijkstra(adj, start, idx, K):
        # adj: [[to, cost] * vertices], 0th index must be empty
        inf = 1 << 60
        N = len(adj) - 1
        dist = [inf] * (1 + N * (1 << K))
        dist[start] = 0
        q = []
        heapq.heappush(q, (0, start))
        while q:
            min_dist, v_from = heapq.heappop(q)
            if min_dist > dist[v_from]:
                continue
            vf = ((v_from - 1) % N) + 1
            state = (v_from - 1) // N
            v_tos = adj[vf]
            for v_to, cost in v_tos:
                ab = vf * mod + v_to
                if ab in idx:
                    j = idx[ab]
                    state_new = state | (1 << j)
                else:
                    state_new = state
                v_to_ = v_to + N * state_new
                if min_dist + cost < dist[v_to_]:
                    dist[v_to_] = min_dist + cost
                    heapq.heappush(q, (dist[v_to_], v_to_))
        return dist

    N, M, K = map(int, input().split())
    R = list(map(int, input().split()))

    idx = {r: i for i, r in enumerate(R)}
    adj = [[] for _ in range(N + 1)]
    idx_ab = {}
    for i in range(1, M+1):
        a, b, c = map(int, input().split())
        adj[a].append((b, c))
        adj[b].append((a, c))
        if i in idx:
            j = idx[i]
            idx_ab[a * mod + b] = j
            idx_ab[b * mod + a] = j

    dist = dijkstra(adj, 1, idx_ab, K)
    print(dist[-1])


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