Submission #1212330

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212330		ackerman2840	Robot (JOI21_ho_t4)	Pypy 3	0 / 100	701 ms	158776 KiB

Main

from heapq import heappop,heappush

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

col=[]
adj=[[] for _ in range(n)]

for _ in range(n):

    col.append(dict())

for _ in range(m):

    a,b,c,p=map(int,input().split())

    adj[a-1].append((b-1,c,p))
    adj[b-1].append((a-1,c,p))

    col[a-1][c]=col[a-1].get(c,0)+1
    col[b-1][c]=col[b-1].get(c,0)+1

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

pq=[(0,0)]

while pq:

    d_v,node=heappop(pq)

    if dist[node]!=d_v:
        continue

    for to,c,p in adj[node]:

        dis=p
        if col[node][c]==1:
            dis=0

        if d_v+dis<dist[to]:
            dist[to]=d_v+dis 
            heappush(pq,(dist[to],to))

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

Compilation message (stdout)

Compiling 'Main.py'...

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

=======

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