結果
問題 | No.1812 Uribo Road |
ユーザー | MasKoaTS |
提出日時 | 2022-01-13 22:48:11 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
AC
|
実行時間 | 3,056 ms / 5,000 ms |
コード長 | 1,873 bytes |
コンパイル時間 | 87 ms |
コンパイル使用メモリ | 12,928 KB |
実行使用メモリ | 35,840 KB |
最終ジャッジ日時 | 2024-04-28 21:02:56 |
合計ジャッジ時間 | 31,374 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 38 ms
11,776 KB |
testcase_01 | AC | 38 ms
11,904 KB |
testcase_02 | AC | 40 ms
11,648 KB |
testcase_03 | AC | 752 ms
17,792 KB |
testcase_04 | AC | 38 ms
11,648 KB |
testcase_05 | AC | 38 ms
11,776 KB |
testcase_06 | AC | 38 ms
11,776 KB |
testcase_07 | AC | 87 ms
12,288 KB |
testcase_08 | AC | 74 ms
12,416 KB |
testcase_09 | AC | 92 ms
12,544 KB |
testcase_10 | AC | 71 ms
12,288 KB |
testcase_11 | AC | 61 ms
12,288 KB |
testcase_12 | AC | 1,488 ms
32,512 KB |
testcase_13 | AC | 1,102 ms
31,872 KB |
testcase_14 | AC | 1,078 ms
31,232 KB |
testcase_15 | AC | 1,215 ms
20,196 KB |
testcase_16 | AC | 689 ms
24,320 KB |
testcase_17 | AC | 2,155 ms
25,080 KB |
testcase_18 | AC | 2,468 ms
22,652 KB |
testcase_19 | AC | 2,849 ms
30,208 KB |
testcase_20 | AC | 2,868 ms
30,336 KB |
testcase_21 | AC | 2,882 ms
35,840 KB |
testcase_22 | AC | 3,056 ms
35,840 KB |
testcase_23 | AC | 176 ms
13,312 KB |
testcase_24 | AC | 38 ms
11,648 KB |
testcase_25 | AC | 286 ms
18,176 KB |
testcase_26 | AC | 77 ms
12,288 KB |
testcase_27 | AC | 1,669 ms
18,492 KB |
testcase_28 | AC | 472 ms
20,736 KB |
testcase_29 | AC | 38 ms
11,776 KB |
testcase_30 | AC | 202 ms
13,056 KB |
testcase_31 | AC | 1,865 ms
22,912 KB |
testcase_32 | AC | 95 ms
12,544 KB |
testcase_33 | AC | 1,092 ms
22,784 KB |
ソースコード
import itertools as iter import collections as coll import heapq as hq import bisect as bis from decimal import Decimal as dec from copy import deepcopy as dcopy import math import sys sys.setrecursionlimit(10**6) def input(): return sys.stdin.readline().rstrip() def getN(): return int(sys.stdin.readline()) def getNs(): return map(int,sys.stdin.readline().split()) def getList(): return list(map(int,sys.stdin.readline().split())) def strinps(n): return [sys.stdin.readline().rstrip() for _ in range(n)] pi = 3.141592653589793 mod = 10**9+7 MOD = 998244353 INF = math.inf dx = [1,0,-1,0]; dy = [0,1,0,-1] """ Main Code """ N, M, K = getNs() R = [i - 1 for i in getNs()] S = set(R) route = [[] for _ in [0] * N] edge = [] for _ in [0] * M: a, b, c = getNs() a -= 1; b -= 1 edge.append((a, b, c)) route[a].append((b,c)) route[b].append((a,c)) def dijkstra(s): path = [-1] * N que = [(0, s)] while(que): d, v = hq.heappop(que) if(path[v] != -1): continue path[v] = d for nv, nd in route[v]: hq.heappush(que, (d + nd, nv)) return path dist = [[] for _ in [0] * N] T = set([0, N - 1]) for i in S: T.add(edge[i][0]) T.add(edge[i][1]) for i in T: dist[i] = dijkstra(i) dp = [[[INF] * 2 for _ in [0] * K] for _ in [0] * (1 << K)] for i in range(K): for j in range(2): dp[1 << i][i][j] = dist[0][edge[R[i]][j ^ 1]] + edge[R[i]][2] for bit in range(1, 1 << K): for s in range(K): if not((bit >> s) & 1): continue for t in range(K): if((bit >> t) & 1): continue for x in range(2): for y in range(2): b = bit | (1 << t) p = edge[R[s]][x] q = edge[R[t]][y ^ 1] d = dp[bit][s][x] + dist[p][q] + edge[R[t]][2] if(dp[b][t][y] > d): dp[b][t][y] = d ans = INF for i in range(K): for j in range(2): p = edge[R[i]][j] d = dp[-1][i][j] + dist[p][N - 1] if(ans > d): ans = d print(ans)