結果
問題 | No.1812 Uribo Road |
ユーザー | Shirotsume |
提出日時 | 2021-12-29 23:57:32 |
言語 | PyPy3 (7.3.15) |
結果 |
MLE
|
実行時間 | - |
コード長 | 1,478 bytes |
コンパイル時間 | 135 ms |
コンパイル使用メモリ | 82,224 KB |
実行使用メモリ | 749,412 KB |
最終ジャッジ日時 | 2024-04-15 06:09:15 |
合計ジャッジ時間 | 9,389 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 39 ms
60,084 KB |
testcase_01 | AC | 42 ms
53,816 KB |
testcase_02 | AC | 42 ms
54,304 KB |
testcase_03 | AC | 270 ms
79,820 KB |
testcase_04 | AC | 38 ms
53,064 KB |
testcase_05 | AC | 39 ms
54,120 KB |
testcase_06 | AC | 38 ms
54,912 KB |
testcase_07 | AC | 44 ms
60,312 KB |
testcase_08 | AC | 434 ms
82,036 KB |
testcase_09 | AC | 709 ms
87,116 KB |
testcase_10 | AC | 332 ms
79,736 KB |
testcase_11 | AC | 218 ms
78,932 KB |
testcase_12 | MLE | - |
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 | -- | - |
ソースコード
import heapq n, m, k = map(int,input().split()) r = list(map(int,input().split())) for i in range(k): r[i] -= 1 graph = [[] for _ in range(n)] r_n = len(r) r_edges = {} r.sort() for i in range(m): a, b, c = map(int,input().split()) if b < a: a, b = b, a graph[a - 1].append((b - 1, c)) graph[b - 1].append((a - 1, c)) if i in r: r_edges[(a - 1, b - 1)] = r.index(i) def dijkstra(n, graph): INF = 10 ** 15 dist = [[INF] * (2 ** r_n) for _ in range(n)] dist[0][0] = 0 hq = [] heapq.heappush(hq, (0, 0, 0)) visit = [[False] * (2 ** r_n) for _ in range(n)] visit[0][0] = True while hq: c, v, bit = heapq.heappop(hq) visit[v][bit] = True if c > dist[v][bit]: continue for to, cost in graph[v]: if (min(v, to), max(v, to)) in r_edges: msk = 1 << r_edges[(min(v, to), max(v, to))] if visit[to][bit | msk] == False and dist[v][bit] + cost < dist[to][bit | msk]: dist[to][bit | msk] = dist[v][bit] + cost heapq.heappush(hq, (dist[to][bit | msk], to, bit | msk)) elif visit[to][bit] == False and dist[v][bit] + cost < dist[to][bit]: dist[to][bit] = dist[v][bit] + cost heapq.heappush(hq, (dist[to][bit], to, bit)) return dist ans = dijkstra(n, graph) print(ans[n - 1][2 ** r_n - 1])