結果
問題 | No.1069 電柱 / Pole (Hard) |
ユーザー |
![]() |
提出日時 | 2020-05-29 23:35:43 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,446 bytes |
コンパイル時間 | 182 ms |
コンパイル使用メモリ | 13,056 KB |
実行使用メモリ | 172,324 KB |
最終ジャッジ日時 | 2024-11-06 12:15:12 |
合計ジャッジ時間 | 3,959 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | WA * 4 |
other | TLE * 1 -- * 78 |
ソースコード
import sys, heapq as hqreadline = sys.stdin.readlinens = lambda: readline().rstrip()ni = lambda: int(readline().rstrip())nm = lambda: map(int, readline().split())nl = lambda: list(map(int, readline().split()))def k_shortestPath(G, s, t, k):N = len(G)d = [10**18]*Nd[t] = 0p = [-1]*Nq = [(0, t, t)]ret = list()while q:wei, src, dst = hq.heappop(q)if p[dst] >= 0: continuep[dst] = srcfor fdst, fwei in G[dst]:if d[fdst] > wei + fwei:d[fdst] = wei + fweihq.heappush(q, (d[fdst], dst, fdst))l = 0R = [(0, -1, s)]print(d)print(p)while R:wei, src, dst = hq.heappop(R)print(wei, src, dst)if dst == t:ret.append(wei + d[s])l += 1if l == k:return retfor fdst, fwei in G[dst]:hq.heappush(R, (wei + fwei - d[dst] + d[fdst], dst, fdst))return Nonedef solve():n, m, k = nm()X, Y = nm()X -= 1; Y -= 1points = [tuple(nm()) for _ in range(n)]G = [list() for _ in range(n)]for _ in range(m):u, v = nm()u -= 1; v -= 1p, q = points[u]r, s = points[v]c = ((p - r)**2 + (q - s)**2) ** .5G[u].append((v, c))G[v].append((u, c))res = k_shortestPath(G, X, Y, k)print(*res, sep='\n')returnsolve()