Submission #1212331

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212331		ackerman2840	Robot (JOI21_ho_t4)	Pypy 3	0 / 100	766 ms	191148 KiB

Main

from heapq import heappush, heappop

n, m = map(int, input().split())

adj = [[] for _ in range(n)]
color_count = [{} for _ in range(n)]  # Count of each color at each node

edges = []

for _ in range(m):
    a, b, c, p = map(int, input().split())
    a -= 1
    b -= 1
    adj[a].append((b, c, p))
    adj[b].append((a, c, p))
    edges.append((a, b, c, p))
    color_count[a][c] = color_count[a].get(c, 0) + 1
    color_count[b][c] = color_count[b].get(c, 0) + 1

dist = [float('inf')] * n
dist[0] = 0

pq = [(0, 0)]

while pq:
    cost_u, u = heappop(pq)
    if dist[u] < cost_u:
        continue
    for v, c, p in adj[u]:
        # If the color is unique at u, we can use the edge at 0 cost
        if color_count[u][c] == 1:
            new_cost = cost_u
        else:
            # Otherwise, we must pay p to recolor
            new_cost = cost_u + p
        if new_cost < dist[v]:
            dist[v] = new_cost
            heappush(pq, (new_cost, v))

print(-1 if dist[n - 1] == float('inf') else dist[n - 1])

Compilation message (stdout)

Compiling 'Main.py'...

=======
  adding: __main__.pyc (deflated 40%)

=======

• Subtask 1: 0 / 34
• Subtask 2: 0 / 24
• Subtask 3: 0 / 42