Submission #1159661

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159661		lidplf	Robot (JOI21_ho_t4)	Pypy 3	24 / 100	1206 ms	273788 KiB

Main

import sys
from collections import defaultdict
import heapq

MOD = 1000000007
MOD2 = 998244353

def solve(cas):
    n, m = map(int, sys.stdin.readline().split())
    g = [[] for _ in range(n)]
    ct = [defaultdict(list) for _ in range(n)]
    sm = [defaultdict(int) for _ in range(n)]
    
    for _ in range(m):
        a, b, c, d = map(int, sys.stdin.readline().split())
        a -= 1
        b -= 1
        g[a].append((b, c, d, 0))
        g[b].append((a, c, d, 0))
        ct[a][c].append(b)
        ct[b][c].append(a)
        sm[a][c] += d
        sm[b][c] += d

    heap = []
    heapq.heappush(heap, (0, 0))
    for i in range(n):
        pt = []
        for neighbor, col, cc, we in g[i]:
            if len(ct[neighbor][col]) == 2:
                pt.append((ct[neighbor][col][0] if ct[neighbor][col][0] != i else ct[neighbor][col][1], col, float('inf'), cc))
        for x in pt:
            g[i].append(x)

    dp = [float('inf')] * n
    dp[0] = 0
    while heap:
        weight, node = heapq.heappop(heap)
        if dp[node] < weight:
            continue
        if node == n - 1:
            print(weight)
            return
        for neighbor, col, cc, we in g[node]:
            if we:
                if weight + we < dp[neighbor]:
                    dp[neighbor] = weight + we
                    heapq.heappush(heap, (dp[neighbor], neighbor))
                continue
            if weight + min(cc, sm[node][col] - cc) * (len(ct[node][col]) > 1) < dp[neighbor]:
                dp[neighbor] = weight + min(cc, sm[node][col] - cc) * (len(ct[node][col]) > 1)
                heapq.heappush(heap, (dp[neighbor], neighbor))

    print(-1)

def main():
    t = 1
    # t = int(data[0])  # Uncomment if multiple test cases are needed
    for i in range(1, t + 1):
        solve(i)

if __name__ == "__main__":
    main()

Compilation message (stdout)

Compiling 'Main.py'...

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

=======

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