結果

問題 No.1320 Two Type Min Cost Cycle
ユーザー maspy
提出日時 2020-12-09 18:15:03
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 868 ms / 2,000 ms
コード長 1,308 bytes
コンパイル時間 311 ms
コンパイル使用メモリ 81,848 KB
実行使用メモリ 80,824 KB
最終ジャッジ日時 2024-09-20 01:21:21
合計ジャッジ時間 13,075 ms
ジャッジサーバーID
(参考情報)
judge4 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 57
権限があれば一括ダウンロードができます

ソースコード

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

import sys
import bisect
from heapq import *
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
INF = 1 << 60
T = int(readline())
N, M = map(int, readline().split())
G = []
for e in range(M):
u, v, c = map(int, readline().split())
G.append((u, v, c))
if T == 0:
G.append((v, u, c))
G.sort()
frm = [g[0] for g in G]
idx = [bisect.bisect_left(frm, v) for v in range(N + 2)]
def dijkstra(S, T):
dist = [INF] * (N + 1)
dist[S] = 0
q = [0 << 15 | S]
while q:
dv, v = divmod(heappop(q), 1 << 15)
if dv > dist[v]:
continue
if v == T:
return dv
for e in range(idx[v], idx[v + 1]):
_, w, c = G[e]
if (v, w) == (S, T):
continue
dw = dv + c
if dist[w] > dw:
dist[w] = dw
heappush(q, dw << 15 | w)
return INF
def main():
done = set()
ans = INF
for u, v, c in G:
if (u, v) in done:
continue
done.add((u, v))
done.add((v, u))
x = dijkstra(v, u) # v u
x = x + c # cycle length
ans = min(ans, x)
if ans == INF:
ans = -1
return ans
print(main())
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0