結果
問題 | No.1812 Uribo Road |
ユーザー | Shirotsume |
提出日時 | 2022-01-01 01:34:53 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,030 ms / 5,000 ms |
コード長 | 1,964 bytes |
コンパイル時間 | 398 ms |
コンパイル使用メモリ | 87,184 KB |
実行使用メモリ | 101,752 KB |
最終ジャッジ日時 | 2023-08-09 06:21:15 |
合計ジャッジ時間 | 14,172 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 77 ms
71,432 KB |
testcase_01 | AC | 78 ms
71,464 KB |
testcase_02 | AC | 90 ms
76,712 KB |
testcase_03 | AC | 182 ms
82,764 KB |
testcase_04 | AC | 78 ms
71,440 KB |
testcase_05 | AC | 77 ms
71,104 KB |
testcase_06 | AC | 78 ms
71,192 KB |
testcase_07 | AC | 111 ms
77,796 KB |
testcase_08 | AC | 214 ms
79,716 KB |
testcase_09 | AC | 253 ms
79,988 KB |
testcase_10 | AC | 187 ms
79,396 KB |
testcase_11 | AC | 202 ms
79,236 KB |
testcase_12 | AC | 562 ms
92,572 KB |
testcase_13 | AC | 323 ms
88,660 KB |
testcase_14 | AC | 339 ms
88,616 KB |
testcase_15 | AC | 508 ms
85,564 KB |
testcase_16 | AC | 457 ms
86,468 KB |
testcase_17 | AC | 882 ms
96,700 KB |
testcase_18 | AC | 359 ms
87,112 KB |
testcase_19 | AC | 982 ms
101,424 KB |
testcase_20 | AC | 1,030 ms
101,752 KB |
testcase_21 | AC | 845 ms
99,760 KB |
testcase_22 | AC | 660 ms
96,024 KB |
testcase_23 | AC | 185 ms
79,460 KB |
testcase_24 | AC | 90 ms
76,456 KB |
testcase_25 | AC | 356 ms
83,436 KB |
testcase_26 | AC | 201 ms
79,556 KB |
testcase_27 | AC | 340 ms
83,568 KB |
testcase_28 | AC | 531 ms
86,824 KB |
testcase_29 | AC | 79 ms
71,292 KB |
testcase_30 | AC | 237 ms
81,296 KB |
testcase_31 | AC | 678 ms
91,072 KB |
testcase_32 | AC | 158 ms
79,084 KB |
testcase_33 | AC | 442 ms
90,956 KB |
ソースコード
INF = 10 ** 18 def dijkstra(s, n, graph): import heapq dist = [INF] * n dist[s] = 0 bef = [0] * n bef[s] = s hq = [(0, s)] #距離、地点を記録したヒープを作る heapq.heapify(hq) visit = [False] * n #訪れたかの判定 while(len(hq) > 0): c, v = heapq.heappop(hq) #ヒープから地点を1つ持ってくる visit[v] = True if c > dist[v]: continue for to, cost in graph[v]: if visit[to] == False and dist[v] + cost < dist[to]: dist[to] = cost + dist[v] bef[to] = v heapq.heappush(hq, (dist[to], to)) ''' return bef ''' return dist n, m, k = map(int,input().split()) r = list(map(int,input().split())) graph = [[] for _ in range(n)] edge = [None] * k dist = [[] for _ in range(n)] for i in range(m): a, b, c = map(int,input().split()) a -= 1 b -= 1 if b < a: a, b = b, a graph[a].append((b, c)) graph[b].append((a, c)) if i + 1 in r: edge[r.index(i + 1)] = (a, b, c) dist[0] = dijkstra(0, n, graph) dist[n - 1] = dijkstra(n - 1, n, graph) for x, y, z in edge: dist[x] = dijkstra(x, n, graph) dist[y] = dijkstra(y, n, graph) dp = [[[INF] * 2 for _ in range(k + 1)] for _ in range(2 ** k + 1)] for i in range(k): for j in range(2): dp[2 ** i][i][j] = dist[0][edge[i][1 - j]] + edge[i][2] for bit in range(2 ** k): for now in range(k): if not (1 & (bit >> now)): continue for to in range(k): if (1 & (bit >> to)): continue for v in range(2): for u in range(2): dp[bit + 2 ** to][to][v] = min(dp[bit + 2 ** to][to][v], dp[bit][now][u] + dist[edge[now][u]][edge[to][1 - v]] + edge[to][2]) ans = INF for i in range(k): for v in range(2): ans = min(ans, dp[2 ** k - 1][i][v] + dist[n - 1][edge[i][v]]) print(ans)