PAST4J

PAST4J

Thoughts.

connected simple undirected graph

warp

The edge is 10^5, but if we explicitly make the warp an edge, we get 10^10

There must be a limit to the number of times you can use warp.

We're not going to make it in time.

A few more considerations

Warp on the first move to a city of a different color than the start.

The same warp is never needed in subsequent explorations, the score is always bad.

Is the same true for return jumps?

No, answers don't match, hold.

Before modification, 31 TLE

6WA, 1TLE after modification

Is it getting better?

What's wrong with using only one jump for each color?

Not one way, both ways.

Still, it's going to be 1 TLE.

quite so

When does that happen?

heapify collectively without heappush each time.

Oh, no.

Increased to 33 TLE.

Add visited

Passed through!

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))

---