結果
問題 | No.1812 Uribo Road |
ユーザー | Shirotsume |
提出日時 | 2022-01-01 01:34:53 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 856 ms / 5,000 ms |
コード長 | 1,964 bytes |
コンパイル時間 | 246 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 99,680 KB |
最終ジャッジ日時 | 2024-04-26 21:13:18 |
合計ジャッジ時間 | 11,454 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 41 ms
53,376 KB |
testcase_01 | AC | 40 ms
53,248 KB |
testcase_02 | AC | 54 ms
64,384 KB |
testcase_03 | AC | 145 ms
81,536 KB |
testcase_04 | AC | 40 ms
52,608 KB |
testcase_05 | AC | 41 ms
53,120 KB |
testcase_06 | AC | 45 ms
53,888 KB |
testcase_07 | AC | 87 ms
76,544 KB |
testcase_08 | AC | 188 ms
78,696 KB |
testcase_09 | AC | 225 ms
78,332 KB |
testcase_10 | AC | 150 ms
77,976 KB |
testcase_11 | AC | 167 ms
78,424 KB |
testcase_12 | AC | 454 ms
91,240 KB |
testcase_13 | AC | 277 ms
87,136 KB |
testcase_14 | AC | 274 ms
87,460 KB |
testcase_15 | AC | 435 ms
83,128 KB |
testcase_16 | AC | 396 ms
84,908 KB |
testcase_17 | AC | 756 ms
95,772 KB |
testcase_18 | AC | 309 ms
84,584 KB |
testcase_19 | AC | 831 ms
99,680 KB |
testcase_20 | AC | 856 ms
99,676 KB |
testcase_21 | AC | 691 ms
95,208 KB |
testcase_22 | AC | 554 ms
92,528 KB |
testcase_23 | AC | 149 ms
77,928 KB |
testcase_24 | AC | 53 ms
63,360 KB |
testcase_25 | AC | 284 ms
81,704 KB |
testcase_26 | AC | 159 ms
77,440 KB |
testcase_27 | AC | 288 ms
82,244 KB |
testcase_28 | AC | 435 ms
84,616 KB |
testcase_29 | AC | 40 ms
53,504 KB |
testcase_30 | AC | 193 ms
78,480 KB |
testcase_31 | AC | 602 ms
89,928 KB |
testcase_32 | AC | 128 ms
77,240 KB |
testcase_33 | AC | 369 ms
89,196 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)