結果

問題 No.1069 電柱 / Pole (Hard)
ユーザー SalmonizeSalmonize
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

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

import sys, heapq as hq
readline = sys.stdin.readline
ns = 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]*N
d[t] = 0
p = [-1]*N
q = [(0, t, t)]
ret = list()
while q:
wei, src, dst = hq.heappop(q)
if p[dst] >= 0: continue
p[dst] = src
for fdst, fwei in G[dst]:
if d[fdst] > wei + fwei:
d[fdst] = wei + fwei
hq.heappush(q, (d[fdst], dst, fdst))
l = 0
R = [(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 += 1
if l == k:
return ret
for fdst, fwei in G[dst]:
hq.heappush(R, (wei + fwei - d[dst] + d[fdst], dst, fdst))
return None
def solve():
n, m, k = nm()
X, Y = nm()
X -= 1; Y -= 1
points = [tuple(nm()) for _ in range(n)]
G = [list() for _ in range(n)]
for _ in range(m):
u, v = nm()
u -= 1; v -= 1
p, q = points[u]
r, s = points[v]
c = ((p - r)**2 + (q - s)**2) ** .5
G[u].append((v, c))
G[v].append((u, c))
res = k_shortestPath(G, X, Y, k)
print(*res, sep='\n')
return
solve()
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0