結果

問題 No.1812 Uribo Road
ユーザー tobusakana
提出日時 2022-10-23 21:06:08
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 3,266 bytes
コンパイル時間 1,327 ms
コンパイル使用メモリ 81,452 KB
実行使用メモリ 533,624 KB
最終ジャッジ日時 2024-07-02 11:11:36
合計ジャッジ時間 8,821 ms
ジャッジサーバーID
(参考情報)
judge4 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 8 MLE * 1 -- * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#
#
#
import sys
readline = sys.stdin.readline
N,M,K = map(int,readline().split())
R = list(map(int,readline().split()))
Rdic = {} # ->dictionary
for i in range(K):
Rdic[R[i] - 1] = i
#
G = [[] for i in range(N)]
#
points = set()
points.add(0)
points.add(N - 1)
ino_road = {}
for i in range(M):
a,b,c = map(int,readline().split())
a -= 1
b -= 1
#
ino = -1
if i in Rdic:
ino = Rdic[i] #
points.add(a) #
points.add(b)
if a > b:
a,b = b,a
ino_road[(a, b)] = [c, ino]
G[a].append([b, c, ino])
G[b].append([a, c, ino])
points = sorted(points)
L = len(points) #
# ->->
# -> points[]
Pdic = {}
for i in range(L):
Pdic[points[i]] = i
# ->Pdic[]
import heapq as hq
R = [[] for i in range(L)] #
#
for key, value in ino_road.items():
a_ind = Pdic[key[0]]
b_ind = Pdic[key[1]]
R[a_ind].append([b_ind, value[0], value[1]])
R[b_ind].append([a_ind, value[0], value[1]])
for start in range(L): #
s = points[start] #
# G
visited = [False] * N #
q = []
hq.heappush(q, (0, s)) #
while q:
d, v = hq.heappop(q)
if visited[v]:
continue
visited[v] = True
if v in Pdic: #
imp = Pdic[v] #
if start != imp and start < imp and (start, imp) not in ino_road:
R[start].append([imp, d, -1])
R[imp].append([start, d, -1])
for child, cost, ino in G[v]:
if visited[child]:
continue
hq.heappush(q, (d + cost, child))
# R
#
# dp[v][S] = v, S
#
start = Pdic[0]
goal = Pdic[N - 1]
INF = 1 << 60
dp = [[INF] * (1 << K) for i in range(N)]
q = []
hq.heappush(q, (0, 0, 0)) #
complete = (1 << K) - 1
while q:
d, v, ino_status = hq.heappop(q)
if dp[v][ino_status] != INF:
continue
dp[v][ino_status] = d
if v == goal and ino_status == complete:
print(d)
break
for child, cost, ino in R[v]:
if ino != -1: #
next_status = ino_status | (1 << ino)
if dp[child][next_status] != INF:
continue
hq.heappush(q, (d + cost, child, next_status))
else:
if dp[child][ino_status] != INF:
continue
hq.heappush(q, (d + cost, child, ino_status))
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0