結果

問題 No.1812 Uribo Road
ユーザー tamatotamato
提出日時 2022-01-14 22:14:03
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,607 bytes
コンパイル時間 553 ms
コンパイル使用メモリ 87,360 KB
実行使用メモリ 449,880 KB
最終ジャッジ日時 2023-08-12 20:11:35
合計ジャッジ時間 9,608 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge7
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 72 ms
76,076 KB
testcase_01 AC 72 ms
71,812 KB
testcase_02 AC 73 ms
71,436 KB
testcase_03 AC 284 ms
80,324 KB
testcase_04 AC 72 ms
71,852 KB
testcase_05 AC 72 ms
71,812 KB
testcase_06 AC 75 ms
71,556 KB
testcase_07 AC 83 ms
75,936 KB
testcase_08 AC 318 ms
81,608 KB
testcase_09 AC 404 ms
82,952 KB
testcase_10 AC 265 ms
79,776 KB
testcase_11 AC 222 ms
79,796 KB
testcase_12 TLE -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
権限があれば一括ダウンロードができます

ソースコード

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