結果
問題 | No.1812 Uribo Road |
ユーザー |
|
提出日時 | 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 |
ソースコード
# 本質的には猪のいる道の両端の頂点の情報さえ分かればよい。# それらの頂点間の最短距離を求める。# グラフとしては、それらの頂点間だけに辺を貼ったものを作る。import sysreadline = sys.stdin.readlineN,M,K = map(int,readline().split())R = list(map(int,readline().split()))Rdic = {} # 道番号->猪の番号へのdictionaryfor 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 -= 1b -= 1# イノシシのいる道か?ino = -1if i in Rdic:ino = Rdic[i] # イノシシの番号points.add(a) # 重要な頂点として追加points.add(b)if a > b:a,b = b,aino_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 hqR = [[] 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]:continuevisited[v] = Trueif 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]:continuehq.heappush(q, (d + cost, child))# Rが重要な頂点同士のグラフになった。# あとは、このグラフで# dp[v][S] = 今いる頂点v, 逢った猪の集合S# をやる。start = Pdic[0]goal = Pdic[N - 1]INF = 1 << 60dp = [[INF] * (1 << K) for i in range(N)]q = []hq.heappush(q, (0, 0, 0)) # 距離、頂点、今までにあった猪の集合complete = (1 << K) - 1while q:d, v, ino_status = hq.heappop(q)if dp[v][ino_status] != INF:continuedp[v][ino_status] = dif v == goal and ino_status == complete:print(d)breakfor child, cost, ino in R[v]:if ino != -1: # イノシシに出会う場合next_status = ino_status | (1 << ino)if dp[child][next_status] != INF:continuehq.heappush(q, (d + cost, child, next_status))else:if dp[child][ino_status] != INF:continuehq.heappush(q, (d + cost, child, ino_status))