Problem: There are N cities numbered 1 to N, connected by M railroads.  You are now at City 1, with 10^{100} gold coins and S silver coins in your pocket.  The i-th railroad connects City U_i and City V_i bidirectionally, and a one- way trip costs A_i silver coins and takes B_i minutes. You cannot use gold coins to pay the fare.  There is an exchange counter in each city. At the exchange counter in City i, you can get C_i silver coins for 1 gold coin. The transaction takes D_i minutes for each gold coin you give. You can exchange any number of gold coins at each exchange counter.  For each t=2, ..., N, find the minimum time needed to travel from City 1 to City t. You can ignore the time spent waiting for trains.

Submission attempts (in order):
from collections import defaultdict
import heapq
N,M,S = map(int,input().split())
E=[list(map(int,input().split())) for _ in range(M)]

C=[list(map(int,input().split())) for _ in range(N)]

A_max=max([a for _,_,a,_ in E])

D=defaultdict(lambda :[])

for u,v,a,b in E:
    u-=1;v-=1
    for from_a in range(A_max+1):
        if from_a-a<0:
            continue
        to_state_v=(v,from_a-a)
        from_state_u=(u,from_a)
        D[from_state_u].append((b,to_state_v))
        to_state_u=(u,from_a-a)
        from_state_v=(v,from_a)
        D[from_state_v].append((b,to_state_u))

for c,d in C:
    for n in range(N):
        for a in range(A_max+1):
            if a+c>A_max:
                continue
            to_state=(n,a+c)
            from_state=(n,a)
            D[from_state].append((d,to_state))


start=(0,max(A_max,S))
Q=[(0,start)]

Dist=defaultdict(lambda :float('inf'))

Dist[start]=0

while Q:
    q = heapq.heappop(Q)
    cur_time,cur_state=q

    if Dist[cur_state]<cur_time:
        continue
    for cost,next_state in D[cur_state]:
        next_time = cost+cur_time

        if Dist[next_state]>next_time:
            Dist[next_state]=next_time
            heapq.heappush(Q,(next_time,next_state))

for dest in range(1,N):
    ans=float("inf")
    for a in range(A_max+1):
        state=(dest,a)
        ans=min(ans,Dist[state])
    print(ans)


from collections import defaultdict
import heapq
N,M,S = map(int,input().split())
E=[list(map(int,input().split())) for _ in range(M)]

C=[list(map(int,input().split())) for _ in range(M)]

A_max=max([a for _,_,a,_ in E])

D=defaultdict(lambda :[])

for u,v,a,b in E:
    u-=1;v-=1
    for from_a in range(A_max+1):
        if from_a-a<0:
            continue
        to_state_v=(v,from_a-a)
        from_state_u=(u,from_a)
        D[from_state_u].append((b,to_state_v))
        to_state_u=(u,from_a-a)
        from_state_v=(v,from_a)
        D[from_state_v].append((b,to_state_u))

for c,d in C:
    for n in range(N):
        for a in range(A_max+1):
            if a+c>A_max:
                continue
            to_state=(n,a+c)
            from_state=(n,a)
            D[from_state].append((d,to_state))


start=(0,max(A_max,S))
Q=[(0,start)]

Dist=defaultdict(lambda :float('inf'))

Dist[start]=0

while Q:
    q = heapq.heappop(Q)
    cur_time,cur_state=q

    if Dist[cur_state]<cur_time:
        continue
    for cost,next_state in D[cur_state]:
        next_time = cost+cur_time

        if Dist[next_state]>next_time:
            Dist[next_state]=next_time
            heapq.heappush(Q,(next_time,next_state))

for dest in range(1,N):
    ans=float("inf")
    for a in range(A_max+1):
        state=(dest,a)
        ans=min(ans,Dist[state])
    print(ans)


from collections import defaultdict
import heapq
N,M,S = map(int,input().split())
E=[list(map(int,input().split())) for _ in range(M)]

C=[list(map(int,input().split())) for _ in range(M)]

A_max=max([a for _,_,a,_ in E])

D=defaultdict(lambda :[])

for u,v,a,b in E:
    u-=1;v-=1
    for from_a in range(a,A_max+1):
        state=(v,from_a-a)
        D[(u,from_a)].append((b,state))

for c,d in C:
    for i in range(N):
        if i+c>A_max:
            continue
        state=(u,i+c)
        D[(u,i)].append((d,state))


start=(0,max(A_max,S))
Q=[(0,state)]

Dist=defaultdict(lambda :float('inf'))

Dist[state]=0

while Q:
    q = heapq.heappop(Q)
    cur_time,cur_state=q

    if Dist[cur_state]<cur_time:
        continue
    for cost,next_state in D[cur_state]:
        next_time = cost+cur_time

        if Dist[next_state]>next_time:
            Dist[next_state]=next_time
            heapq.heappush(Q,(next_time,next_state))

for dest in range(1,N):
    ans=float("inf")
    for a in range(A_max+1):
        state=(dest,a)
        ans=min(ans,Dist[state])
    print(ans)


from collections import defaultdict
import heapq
N,M,S = map(int,input().split())
E=[list(map(int,input().split())) for _ in range(M)]

C=[list(map(int,input().split())) for _ in range(M)]

A_max=max([a for _,_,a,_ in E])

D=defaultdict(lambda :[])

for u,v,a,b in E:
    u-=1;v-=1
    for from_a in range(a,A_max+1):
        state=(v,from_a-a)
        D[(u,from_a)].append((b,state))

for c,d in C:
    for i in range(N):
        if i+c>A_max:
            continue
        state=(u,i+c)
        D[(u,i)].append((d,state))


start=(0,max(A_max,S))
Q=[(0,state)]

Dist=defaultdict(lambda :float('inf'))

Dist[state]=0

while Q:
    q = heapq.heappop(Q)
    cur_time,cur_state=q

    if Dist[cur_state]<cur_time:
        continue
    for cost,next_state in D[cur_state]:
        next_time = cost+cur_time

        if Dist[next_state]>next_time:
            Dist[next_state]=next_time
            heapq.heappush(Q,(next_time,next_state))

for dest in range(1,N):
    ans=float("inf")
    for a in range(A_max+1):
        state=(dest,a)
        ans=min(ans,Dist[state])
    print(ans)


from collections import defaultdict
import heapq
N,M,S = map(int,input().split())
E=[list(map(int,input().split())) for _ in range(M)]

C=[list(map(int,input().split())) for _ in range(N)]

A_max=max([a for _,_,a,_ in E])*N

D=defaultdict(lambda :[])

for u,v,a,b in E:
    u-=1;v-=1
    for from_a in range(A_max+1):
        if from_a-a<0:
            continue
        from_state_u=(u,from_a)
        to_state_v=(v,from_a-a)
        D[from_state_u].append((b,to_state_v))

        from_state_v=(v,from_a)
        to_state_u=(u,from_a-a)
        D[from_state_v].append((b,to_state_u))

for n,[c,d] in enumerate(C):
    for a in range(A_max+1):
        a_after=min(A_max,a+c)
        from_state=(n,a)
        to_state=(n,a_after)
        D[from_state].append((d,to_state))


start=(0,min(A_max,S))
Q=[(0,start)]

Dist=defaultdict(lambda :float('inf'))

Dist[start]=0

while Q:
    q = heapq.heappop(Q)
    cur_time,cur_state=q

    if Dist[cur_state]<cur_time:
        continue
    for cost,next_state in D[cur_state]:
        next_time = cost+cur_time

        if Dist[next_state]>next_time:
            Dist[next_state]=next_time
            heapq.heappush(Q,(next_time,next_state))

for dest in range(1,N):
    ans=float("inf")
    for a in range(A_max+1):
        state=(dest,a)
        ans=min(ans,Dist[state])
    print(ans)


Verdicts: Wrong Answer

Runtime Error

Runtime Error

Runtime Error

Accepted