結果
問題 | No.1301 Strange Graph Shortest Path |
ユーザー |
|
提出日時 | 2024-10-27 00:55:32 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,221 bytes |
コンパイル時間 | 369 ms |
コンパイル使用メモリ | 82,404 KB |
実行使用メモリ | 277,540 KB |
最終ジャッジ日時 | 2024-10-27 00:57:11 |
合計ジャッジ時間 | 95,645 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 16 WA * 4 TLE * 13 |
ソースコード
from heapq import heappop, heappushN, M = map(int, input().split())graph = [[] for _ in range(N)]pos = {}for _ in range(M):a, b, c, d = map(int, input().split())a -= 1; b -= 1pos[a, b, c] = len(graph[a])pos[b, a, c] = len(graph[b])graph[a].append([b, c])graph[b].append([a, c])pos[a, b, d] = len(graph[a])pos[b, a, d] = len(graph[b])graph[a].append([b, d])graph[b].append([a, d])D = [[-1, None] for _ in range(N+1)]hq = [(0, 0, None)]while hq:d, node, par = heappop(hq)if D[node][0] != -1:continueD[node] = [d, par]for nex, c in graph[node]:if D[nex][0] == -1:heappush(hq, (D[node][0]+c, nex, node))INF = 10**10ans = D[N-1][0]now = N-1while now:d, par = D[now]c = d - D[par][0]i1 = pos[par, now, c]i2 = pos[now, par, c]graph[par][i1][1] = graph[now][i2][1] = INFnow = parD = [[-1, None] for _ in range(N)]hq = [(0, N-1, None)]while hq:d, node, par = heappop(hq)if D[node][0] != -1:continueD[node] = [d, par]for nex, c in graph[node]:if D[nex][0] == -1:heappush(hq, (D[node][0]+c, nex, node))print(D[0][0]+ans)