PAST4J

PAST4J

考えたこと

連結単純無向グラフ

ワープ

辺は10^5だが、ワープを明示的に辺にすると10^10

ワープを使う回数に制限があるのだろう

間に合いませんな

もう少し考察

スタートと違う色の街には初手でワープ

その後の探索で同じワープが必要になることはない、スコアは必ず悪い

戻りジャンプも同様か

ダメだ、答えが合わない、保留

修正前は31TLE

修正後は6WA, 1TLE

よくなってる？

ジャンプを各色1回しか使わないのの何が悪いのか

片道じゃなくて両方向だ

それでも1TLEしそう

そのとおり

どういう時にそうなる？

毎回heappushしないでまとめてheapify

ダメか

33TLEに増えた

visitedの追加

通った！

code:python

def solve(N, M, X, S, ABC):

INF = 1e+99

from collections import defaultdict

edges = defaultdict(dict)

for A, B, C in ABC:

for i in range(N):

usedWarp = set()

GOAL = N - 1

START = 0

from heapq import heappush, heappop, heapify

while True:

cost, pos = heappop(queue)

if pos == GOAL:

return cost

continue

for next in ep:

heappush(queue, (nc, next))

for typ in range(3):

continue

continue

nc = cost + c

heappush(queue, (nc, next))