結果

問題 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 41 ms
60,592 KB
testcase_01 AC 43 ms
491,608 KB
testcase_02 AC 42 ms
242,092 KB
testcase_03 AC 262 ms
85,004 KB
testcase_04 AC 41 ms
177,356 KB
testcase_05 MLE -
testcase_06 MLE -
testcase_07 AC 50 ms
68,984 KB
testcase_08 MLE -
testcase_09 AC 405 ms
89,120 KB
testcase_10 MLE -
testcase_11 AC 210 ms
78,516 KB
testcase_12 TLE -
testcase_13 AC 353 ms
399,108 KB
testcase_14 AC 405 ms
398,696 KB
testcase_15 AC 1,956 ms
117,172 KB
testcase_16 TLE -
testcase_17 TLE -
testcase_18 TLE -
testcase_19 TLE -
testcase_20 TLE -
testcase_21 TLE -
testcase_22 TLE -
testcase_23 AC 613 ms
85,300 KB
testcase_24 AC 76 ms
73,048 KB
testcase_25 AC 183 ms
78,716 KB
testcase_26 AC 146 ms
77,548 KB
testcase_27 AC 3,498 ms
100,404 KB
testcase_28 AC 322 ms
81,452 KB
testcase_29 AC 42 ms
53,400 KB
testcase_30 AC 240 ms
78,548 KB
testcase_31 TLE -
testcase_32 AC 192 ms
77,892 KB
testcase_33 MLE -
権限があれば一括ダウンロードができます

ソースコード

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