Problem:


Score : 500 points

Problem Statement

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.

Constraints

2 \leq N \leq 50

N-1 \leq M \leq 100

0 \leq S \leq 10^9

1 \leq A_i \leq 50

1 \leq B_i,C_i,D_i \leq 10^9

1 \leq U_i < V_i \leq N

There is no pair i, j(i \neq j) such that (U_i,V_i)=(U_j,V_j).

Each city t=2,...,N can be reached from City 1 with some number of railroads.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M S
U_1 V_1 A_1 B_1
:
U_M V_M A_M B_M
C_1 D_1
:
C_N D_N

Output

For each t=2, ..., N in this order, print a line containing the minimum time needed to travel from City 1 to City t.

Sample Input 1

3 2 1
1 2 1 2
1 3 2 4
1 11
1 2
2 5

Sample Output 1

2
14

The railway network in this input is shown in the figure below.

In this figure, each city is labeled as follows:

The first line: the ID number i of the city (i for City i)

The second line: C_i / D_i

Similarly, each railroad is labeled as follows:

The first line: the ID number i of the railroad (i for the i-th railroad in input)

The second line: A_i / B_i

You can travel from City 1 to City 2 in 2 minutes, as follows:

Use the 1-st railroad to move from City 1 to City 2 in 2 minutes.

You can travel from City 1 to City 3 in 14 minutes, as follows:

Use the 1-st railroad to move from City 1 to City 2 in 2 minutes.

At the exchange counter in City 2, exchange 3 gold coins for 3 silver coins in 6 minutes.

Use the 1-st railroad to move from City 2 to City 1 in 2 minutes.

Use the 2-nd railroad to move from City 1 to City 3 in 4 minutes.

Sample Input 2

4 4 1
1 2 1 5
1 3 4 4
2 4 2 2
3 4 1 1
3 1
3 1
5 2
6 4

Sample Output 2

5
5
7

The railway network in this input is shown in the figure below:

You can travel from City 1 to City 4 in 7 minutes, as follows:

At the exchange counter in City 1, exchange 2 gold coins for 6 silver coins in 2 minutes.

Use the 2-nd railroad to move from City 1 to City 3 in 4 minutes.

Use the 4-th railroad to move from City 3 to City 4 in 1 minutes.

Sample Input 3

6 5 1
1 2 1 1
1 3 2 1
2 4 5 1
3 5 11 1
1 6 50 1
1 10000
1 3000
1 700
1 100
1 1
100 1

Sample Output 3

1
9003
14606
16510
16576

The railway network in this input is shown in the figure below:

You can travel from City 1 to City 6 in 16576 minutes, as follows:

Use the 1-st railroad to move from City 1 to City 2 in 1 minute.

At the exchange counter in City 2, exchange 3 gold coins for 3 silver coins in 9000 minutes.

Use the 1-st railroad to move from City 2 to City 1 in 1 minute.

Use the 2-nd railroad to move from City 1 to City 3 in 1 minute.

At the exchange counter in City 3, exchange 8 gold coins for 8 silver coins in 5600 minutes.

Use the 2-nd railroad to move from City 3 to City 1 in 1 minute.

Use the 1-st railroad to move from City 1 to City 2 in 1 minute.

Use the 3-rd railroad to move from City 2 to City 4 in 1 minute.

At the exchange counter in City 4, exchange 19 gold coins for 19 silver coins in 1900 minutes.

Use the 3-rd railroad to move from City 4 to City 2 in 1 minute.

Use the 1-st railroad to move from City 2 to City 1 in 1 minute.

Use the 2-nd railroad to move from City 1 to City 3 in 1 minute.

Use the 4-th railroad to move from City 3 to City 5 in 1 minute.

At the exchange counter in City 5, exchange 63 gold coins for 63 silver coins in 63 minutes.

Use the 4-th railroad to move from City 5 to City 3 in 1 minute.

Use the 2-nd railroad to move from City 3 to City 1 in 1 minute.

Use the 5-th railroad to move from City 1 to City 6 in 1 minute.

Sample Input 4

4 6 1000000000
1 2 50 1
1 3 50 5
1 4 50 7
2 3 50 2
2 4 50 4
3 4 50 3
10 2
4 4
5 5
7 7

Sample Output 4

1
3
5

The railway network in this input is shown in the figure below:

Sample Input 5

2 1 0
1 2 1 1
1 1000000000
1 1

Sample Output 5

1000000001

The railway network in this input is shown in the figure below:

You can travel from City 1 to City 2 in 1000000001 minutes, as follows:

At the exchange counter in City 1, exchange 1 gold coin for 1 silver coin in 1000000000 minutes.

Use the 1-st railroad to move from City 1 to City 2 in 1 minute.



Sample input:
3 2 1
1 2 1 2
1 3 2 4
1 11
1 2
2 5


Sample output:
2
14

Submission status: Wrong Answer

Solution code:
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

import heapq
n,m,s = inm()
dst = [{} for i in range(n+1)]
for i in range(m):
    uu,vv,aa,bb = inm()
    dst[uu][vv] = (aa,bb)
    dst[vv][uu] = (aa,bb)
c = [-1]
d = [-1]
for i in range(n):
    cc,dd = inm()
    c.append(cc)
    d.append(dd)

cost = [(BIG,0)]*(n+1)  # time, money left
cost[1] = (0,s)
done = [False]*(n+1)
first = True
while True:
    if first:
        stt = 1
        m0 = s
        first = False
    else:
        mn = BIG
        for i in range(1,n+1):
            if not done[i] and cost[i][0]<mn:
                mn = cost[i][0]
                stt = i
                m0 = cost[i][1]
        if mn==BIG:
            break
    done[stt] = True
    #ddprint(f"loop stt {stt} cost:")
    #ddprint(cost)

    cost2 = [(BIG,0)]*(n+1)
    q = [(0,stt,0,0)]
    # totaltime, node, time, fare
    xchgtime = d[stt]
    xchgamt = c[stt]
    while len(q)>0:
        dd,p,t,fare = heapq.heappop(q)
        if cost2[p][0]<=dd:
            continue
        cost2[p] = (dd, (m0-fare)%xchgamt)
        for v in dst[p]:
            timepv = dst[p][v][1]
            farepv = dst[p][v][0]
            newd = t+timepv+ \
              ((max(0,fare+farepv-m0)+xchgamt-1)//xchgamt)*xchgtime
            heapq.heappush(q,(newd, v, t+timepv, fare+farepv))
            #ddprint("newd {} v {} t {} fare {}".format( \
            #      newd, v, t+timepv, fare+farepv))
    for i in range(1,n+1):
        if cost[i][0]>cost[stt][0]+cost2[i][0]:
            cost[i] = (cost[stt][0]+cost2[i][0], cost2[i][1])

for i in range(2,n+1):
    print(cost[i][0])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)

N, M, S = map(int, input().split())

graph = [[] for i in range(N)]
for i in range(M):
  u, v, a, b = map(int, input().split())
  u -=1; v -=1
  graph[u].append([v, a, b])
  graph[v].append([u, a, b])

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

p = [[] for i in range(N)]
def calc_path(node, stack, cost, time):
  global p
  children = graph[node]
  for child, c, t in children:
    if stack.count(child) >= 2:
      continue
    p[child].append([stack, cost+c, time+t])
    calc_path(child, stack+[child], cost+c, time+t)


calc_path(0, [0], 0, 0)

def calc_min_time(via, diff):
  via_set = set(via)
  num_time = []
  for node in via_set:
    num, time = trans[node]
    num_time.append([num, time])
  if num_time:
    dp = [10**10] * (diff + 1)
    dp[0] = 0
    for i in range(1, diff+1):
      for num, time in num_time:
        idx = max(0, i - num)
        dp[i] = min(dp[i], dp[idx] + time)
    return dp[-1]
  else:
    return 10**10
  

for t in range(1, N):
  ps = p[t]
  ans = 10**10
  for via, cost, time in ps:
    if cost <= S:
      ans = min(ans, time)
    else:
      min_time = calc_min_time(via, cost - S)
      ans = min(ans, time + min_time)
  print(ans)

Submission status: Wrong Answer

Solution code:
import copy
# スペース区切りの整数入力
N,M,S = map(int, input().split())

U=[]
V=[]
A=[]
B=[]

for i in range(M):
    u,v,a,b = map(int, input().split())
    U.append(u)
    V.append(v)
    A.append(a)
    B.append(b)

C=[]
D=[]
for i in range(N):
    c,d = map(int, input().split())
    C.append(c)
    D.append(d)

for pp in range(2,N+1):
    p0 = [[0,1,100,S]]

    res = 999999999999999999
    while True:
        p0.sort()
        t,p,g,s = p0.pop(0)
        if t >= res:
            break
        if t > 16576:
            print("over")
            break
        #g2s
        if g > 0:
            if [t+D[p-1],p,g-1,s+C[p-1]] in p0:
                pass
            else:
                p0.append([t+D[p-1],p,g-1,s+C[p-1]])
        #move
        for i in range(M):
            if U[i] == p and A[i] <= s:
                if [t+B[i],V[i],g,s-A[i]] in p0:
                    pass
                else:
                    p0.append([t+B[i],V[i],g,s-A[i]])
                    if V[i] == pp:
                        res = min(res,t+B[i])
            if V[i] == p and A[i] <= s:
                if [t+B[i],U[i],g,s-A[i]] in p0:
                    pass
                else:
                    p0.append([t+B[i],U[i],g,s-A[i]])
                    if U[i] == pp:
                        res = min(res,t+B[i])
    print(res)

Submission status: Wrong Answer

Solution code:
#### 拡張ダイクストラではないが方針は良さそうに見えたので貼っておく
#### たぶんdfsで全経路列挙がうまくできていない
#### そこをなおしてもたぶんTLE

import sys, copy, math, heapq, bisect
from itertools import accumulate
from collections import deque, defaultdict, Counter
input = sys.stdin.readline # 文字列の入力のとき'/n'まで受け取るので注意!!!
sys.setrecursionlimit(500000)


N,M,S = map(int,input().split())

G = [[] for i in range(N)]
AB = [[0]*N for i in range(N)]
for i in range(M):
    U,V,A,B = map(int,input().split())
    AB[U-1][V-1] = (A,B)
    AB[V-1][U-1] = (A,B)
    G[U-1].append(V-1)
    G[V-1].append(U-1)
CD = [tuple(map(int,input().split())) for i in range(N)]
CD.sort(key=lambda x: x[1])
CD.sort(key=lambda x: x[0])
C = [CD[i][0] for i in range(N)]
D = [CD[i][1] for i in range(N)]
root = []
def dfs(i,goal,visited_i,cost,time):
    visited = visited_i.copy()
    for j in G[i]:
        if visited[j]==2:
            continue
        visited[j] += 1
        if j==goal:
            root.append((cost+AB[i][j][0],time+AB[i][j][1],visited))
            continue
        dfs(j,goal,visited,cost+AB[i][j][0],time+AB[i][j][1])

for t in range(1,N):
    visited = [0]*N
    visited[0]=1
    dfs(0,t,visited,0,0)
    root.sort(key=lambda x: x[1])
    
    if root[0][0]<=S:
        print(root[0][1])
        root = []
        continue
    m = 10**10
    for r in range(len(root)):
        rest = root[r][0]-S
        Cr = [C[i] for i in range(N) if root[r][2][i]>=1]
        Dr = [D[i] for i in range(N) if root[r][2][i]>=1]
        id = bisect.bisect_left(Cr,rest)
        if id==len(Cr):
            continue
        m = min(m,root[r][1]+min(Dr[id:]))
    print(m)

Submission status: Wrong Answer

Solution code:
from collections import deque
from itertools import product
import sys
import math

sys.setrecursionlimit(200000)
input = sys.stdin.readline


def read(INF=10**15):
    N, M, S = map(int, input().strip().split())
    A = [[-1 for j in range(N+1)] for i in range(N+1)]
    B = [[-1 for j in range(N+1)] for i in range(N+1)]
    for i in range(M):
        u, v, a, b = map(int, input().strip().split())
        A[u][v] = a
        B[u][v] = b
        A[v][u] = a
        B[v][u] = b
    C = [INF, ]
    D = [INF, ]
    for i in range(N):
        c, d =  map(int, input().strip().split())
        C.append(c)
        D.append(d)
    return N, M, S, A, B, C, D


def solve(N, M, S, A, B, C, D, INF=10**15):
    t = [[INF for j in range(N+1)] for i in range(N+1)]  # time
    c = [[INF for j in range(N+1)] for i in range(N+1)]  # cost
    for i in range(1, N+1):
        for j in range(1, N+1):
            t[i][j] = B[i][j] if B[i][j] >= 0 else INF
            c[i][j] = A[i][j] if A[i][j] >= 0 else INF
    for i in range(1, N+1):
        t[i][i] = 0
        c[i][i] = 0
    for k in range(1, N+1):
        for i in range(1, N+1):
            for j in range(1, N+1):
                if t[i][j] > t[i][k] + t[k][j]:
                    t[i][j] = t[i][k] + t[k][j]
                    c[i][j] = c[i][k] + c[k][j]
    for j in range(2, N+1):
        if c[1][j] <= S:
            print(t[1][j])
        else:
            min_time = INF
            for x in range(1, N+1):
                if c[1][x] <= S:
                    min_time = min(min_time, t[1][x] + t[x][j] + math.ceil((c[x][j] - S + c[1][x]) / C[x]) * D[x])
            print(min_time)

if __name__ == '__main__':
    inputs = read()
    solve(*inputs)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

n,m,s=l_in()

uvab=[]
edges = [[] for _ in range(n)]
for _ in range(m):
    u,v,a,b = l_in()
    edges[u-1].append((v-1,a,b))
    edges[v-1].append((u-1,a,b))

cd = [l_in() for _ in range(n)]

# dp[i][g] city i で g まいの銀貨をもつための最小時間
m = 101
#m = 4
dp = [[-1]*m for _ in range(n)]


from heapq import heappush,heappop
h = []

for g in range(min(s+1,m+3)):
    heappush(h, (0,-g,0))

while len(h) > 0:
    t,g,i = h[0]
    g = -g
#    print("t,g,i", t,g,i)
    # 
    heappop(h)

    if dp[i][min(g,m-1)] != -1:
        dp[i][min(g,m-1)] = min(t, dp[i][min(g,m-1)])
    else:
        dp[i][min(g,m-1)] = t
    
    for v,a,b in edges[i]:
        if g-a >= 0 and dp[v][min(g-a,m-1)] == -1:
            heappush(h,(t+b,-(g-a),v))
#            print("push", t+b,-g+a,v)

    c,d = cd[i]
    if dp[i][min(g+c,m-1)] == -1:
        heappush(h,(t+d,-(g+c),i))

for d in dp:
    pass
#    print(d)


for i in range(1, n):
    res = -1
    for v,a,b in edges[i]:
        min_t = -1
        for g in range(a,m):
            t = dp[v][g]
            if t == -1:
                continue
            if min_t == -1 or min_t > t:
                min_t = t
#                print("min_t", v,g,min_t)

        if res == -1 or res > min_t+b:
            res = min_t+b

#    print(dp[i])
    for t in dp[i]:
        if t == -1:
            continue
        if res == -1  or t < res:
            continue
            res = t
            
    print(res)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect, heapq
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,m,s0 = map(int,input().split())
s0 = min(250,s0)
G = [[] for i in range(n)]
for i in range(m):
  u,v,a,b = map(int,input().split())
  u-=1;v-=1
  G[u].append((v,a,b))
  G[v].append((u,a,b))
kankin = [tuple(map(int,input().split())) for i in range(n)]

def ceil(x,y):
  return (x-1)//y+1


def dijktra(g,s):
    n=len(g)
    dist = [[inf]*251 for i in range(n)]
    dist[s][s0]
    hq=[]
    heapq.heappush(hq,(0,s0,s))
    while hq:
        time,money,u = heapq.heappop(hq)
        if dist[u][money] < time: continue
        c,d = kankin[u]
        while money <= 250:
          for v,money1,time1 in g[u]:
            if not money >= money1: continue
            if dist[v][money-money1] > time + time1:
              dist[v][money-money1] = (time + time1)
              heapq.heappush(hq,(time + time1, money-money1,v))
          money += c; time += d

    return dist

dist = dijktra(G,0)
for i in range(1,n):
  print(min(dist[i]))

Submission status: Wrong Answer

Solution code:
from heapq import *
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():

    inf=10**32
    n,m,s=MI()
    to=[[] for _ in range(n)]
    for _ in range(m):
        u,v,a,b=MI()
        to[u-1].append((v-1,a,b))
        to[v-1].append((u-1,a,b))
    cd=LLI(n)

    dp=[[inf]*3005 for _ in range(n)]
    hp=[]
    heappush(hp,(0,min(s,3000),0))

    cnt=0
    while hp:
        t,g,u=heappop(hp)
        if dp[u][g]<t:continue
        c,d=cd[u]
        if g+c<3000:
            if dp[u][g + c] <= t + d: continue
            dp[u][g + c] = t + d
            heappush(hp, (t + d, g + c, u))
        else:
            if dp[u][3000] <= t + d: continue
            dp[u][3000] = t + d
            heappush(hp, (t + d, 3000, u))
        for v,a,b in to[u]:
            if g-a<0:continue
            if dp[v][g-a]<=t+b:continue
            dp[v][g - a] = t + b
            heappush(hp,(t+b,g-a,v))
    for u in range(1,n):
        print(min(dp[u]))

main()

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
inf = float('inf')
def dijkstra(graph:list, node:int, start:int) -> list:
    dist = [inf]*node

    dist[start] = 0
    heap = [(0,start)]
    while heap:
        cost,thisNode = heappop(heap)
        for NextCost,NextNode in graph[thisNode]:
            dist_cand = dist[thisNode]+NextCost
            if dist_cand < dist[NextNode]:
                dist[NextNode] = dist_cand
                heappush(heap,(dist[NextNode],NextNode))
    return dist

N,M,S = map(int,input().split())
graph = [[] for i in range(2501*N)]
for i in range(M):
    u,v,a,b = map(int,input().split())
    u -= 1
    v -= 1
    for s in range(a,2500):
        graph[2501*u+s].append([b,2501*v+s-a])
        graph[2501*v+s].append([b,2501*u+s-a])

for i in range(N):
    c,d = map(int,input().split())
    for s in range(2500):
        graph[2501*i+s].append([d,2501*i+min(2500,s+c)])

dist = dijkstra(graph,2501*N,min(2500,S))

ans = [inf]*N
for i in range(N):
    for s in range(2501):
        ans[i] = min(ans[i],dist[2500*i+s])

for i in range(1,N):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

n,m,s=l_in()

uvab=[]
edges = [[] for _ in range(n)]
for _ in range(m):
    u,v,a,b = l_in()
    edges[u-1].append((v-1,a,b))
    edges[v-1].append((u-1,a,b))

cd = [l_in() for _ in range(n)]

# dp[i][g] city i で g まいの銀貨をもつための最小時間
m = 1001
#m = 4
dp = [[-1]*m for _ in range(n)]


from heapq import heappush,heappop
h = []

for g in range(min(s+1,m+3)):
    heappush(h, (0,-g,0))
 
while len(h) > 0:
    t,g,i = h[0]
    g = -g
 #    print(t,g,1, h)
    # 
    heappop(h)

    if dp[i][min(g,m-1)] != -1:
        continue

    dp[i][min(g,m-1)] = t

    
    for v,a,b in edges[i]:
        if g-a >= 0:
            heappush(h,(t+b,-(g-a),v))

    c,d = cd[i]
    heappush(h,(t+d,-(g+c),i))
    


for d in dp:
    pass
#    print(d)


for i in range(1, n):
    res = -1
    for v,a,b in edges[i]:
        min_t = -1
        for g in range(a,m):
            t = dp[v][g]
            if t == -1:
                continue
            if min_t == -1 or min_t > t:
                min_t = t
#                print("min_t", v,g,min_t)

        if res == -1 or res > min_t+b:
            res = min_t+b

#    print(dp[i])
    for t in dp[i]:
        if t == -1:
            continue
        if res == -1  or t < res:
            continue
            res = t
            
    print(res)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

n,m,s=l_in()

uvab=[]
edges = [[] for _ in range(n)]
for _ in range(m):
    u,v,a,b = l_in()
    edges[u-1].append((v-1,a,b))
    edges[v-1].append((u-1,a,b))

cd = [l_in() for _ in range(n)]

# dp[i][g] city i で g まいの銀貨をもつための最小時間
#m = 1001
m = 4
dp = [[-1]*m for _ in range(n)]

from heapq import heappush,heappop
h = []

for g in range(min(s+1,m+3)):
    heappush(h, (0,-g,0))
 
while len(h) > 0:
    t,g,i = h[0]
    g = -g
 #    print(t,g,1, h)
    # 
    heappop(h)

    if dp[i][min(g,m-1)] != -1:
        continue

    dp[i][min(g,m-1)] = t

    
    for v,a,b in edges[i]:
        if g-a >= 0:
            heappush(h,(t+b,-(g-a),v))

    c,d = cd[i]
    heappush(h,(t+d,-(g+c),i))
    


for d in dp:
    pass
    print(d)


for i in range(1, n):
    res = -1
    for v,a,b in edges[i]:
        min_t = -1
        for g in range(a,m):
            t = dp[v][g]
            if t == -1:
                continue
            if min_t == -1 or min_t > t:
                min_t = t
#                print("min_t", v,g,min_t)

        if res == -1 or res > min_t+b:
            res = min_t+b

#    print(dp[i])
    for t in dp[i]:
        if t == -1:
            continue
        if res == -1  or t < res:
            continue
            res = t
            
    print(res)

Submission status: Wrong Answer

Solution code:
from heapq import *
n, m, s = map(int, input().split())
inf = 10**18
#train_time[i][j]: i -> jに掛かる時間
train = [[] for i in range(n+1)]

for i in range(m):
    u, v, a, b = map(int, input().split())
    train[u].append((v, a, b))
    train[v].append((u, a, b))

exchange = [[]]
for i in range(n):
    exchange.append(list(map(int, input().split())))

queue = [(0, 1, s, set([1]), [len(i) for i in train])]
cost = [inf for i in range(n+1)]
cost[1] = 0
cost[0] = 0
count = 0
while queue:
    now_t, now, now_c, visit, visit_count = heappop(queue)
    #print(now_t, now, now_c, visit, visit_count)
    if max(cost) != inf:
        break
    visit.add(now)
    cost[now] = min(cost[now], now_t)
    visit_count[now] -= 1
    if visit_count[now] < 0:
        continue
    for next, next_c, next_t in train[now]:
        if next_c > now_c:
            for ex in visit:
                next_t_plus = ((next_c-now_c-1)//exchange[ex][0] + 1)*exchange[ex][1]
                next_c_plus = ((next_c-now_c-1)//exchange[ex][0] + 1)*exchange[ex][0]
                nx = (now_t+next_t+next_t_plus, next, now_c-next_c+next_c_plus, visit, visit_count[:])
                if nx not in queue:
                    heappush(queue, nx)
        else:
            nx = (now_t+next_t, next, now_c-next_c, visit, visit_count[:])
            if nx not in queue:
                heappush(queue, (now_t+next_t, next, now_c-next_c, visit, visit_count[:]))

for i in range(2, n+1):
    print(cost[i])

Submission status: Wrong Answer

Solution code:
import copy
# スペース区切りの整数入力
N,M,S = map(int, input().split())

U=[]
V=[]
A=[]
B=[]

for i in range(M):
    u,v,a,b = map(int, input().split())
    U.append(u)
    V.append(v)
    A.append(a)
    B.append(b)

C=[]
D=[]
for i in range(N):
    c,d = map(int, input().split())
    C.append(c)
    D.append(d)

for pp in range(2,N+1):
    p0 = [[0,1,100,S]]
    p1 = []

    res = 999999999999999999
    while True:
        for t,p,g,s in p0:
            #g2s
            if g > 0:
                p1.append([t+D[p-1],p,g-1,s+C[p-1]])
            #move
            for i in range(M):
                if U[i] == p and A[i] <= s:
                    p1.append([t+B[i],V[i],g,s-A[i]])
                    if V[i] == pp:
                        res = min(res,t+B[i])
                if V[i] == p and A[i] <= s:
                    p1.append([t+B[i],U[i],g,s-A[i]])
                    if U[i] == pp:
                        res = min(res,t+B[i])
        p0 = []
        for t,p,g,s in p1:
            if t < res:
                p0.append([t,p,g,s])
        if len(p0) == 0:
            break
        p1 = []
    print(res)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

n,m,s=l_in()

uvab=[]
edges = [[] for _ in range(n)]
for _ in range(m):
    u,v,a,b = l_in()
    edges[u-1].append((v-1,a,b))
    edges[v-1].append((u-1,a,b))

cd = [l_in() for _ in range(n)]

# dp[i][g] city i で g まいの銀貨をもつための最小時間
m = 1001
dp = [[-1]*m for _ in range(n)]

from heapq import heappush,heappop
h = []

for g in range(min(s+1,m)):
    heappush(h, (0,-g,0))
 
while len(h) > 0:
    t,g,i = h[0]
    g = -g
    # 
    heappop(h)

    if dp[i][min(g,m-1)] != -1:
        continue

    dp[i][min(g,m-1)] = t

    
    for v,a,b in edges[i]:
        if g-a >= 0:
            heappush(h,(t+b,-(g-a),v))

    c,d = cd[i]
    heappush(h,(t+d,-(g+c),i))
    


#for d in dp:
#    pass
#    print(d)


for i in range(1, n):
    res = -1
    for v,a,b in edges[i]:
        min_t = -1
        for g in range(a,m):
            t = dp[v][g]
            if t == -1:
                continue
            if min_t == -1 or min_t > t:
                min_t = t
#                print("min_t", v,g,min_t)

        if res == -1 or res > min_t+b:
            res = min_t+b

#    print(dp[i])
    for t in dp[i]:
        if t == -1:
            continue
        if res == -1  or t < res:
            continue
            res = t
            
    print(res)

Submission status: Wrong Answer

Solution code:
from collections import deque

N, M, S = map(int, input().strip().split())

graph = [[] for _ in range(N)]
for _ in range(M):
	u, v, a, b = map(int, input().strip().split())
	u -= 1
	v -= 1
	graph[u].append((v, a, b))
	graph[v].append((u, a, b))

queue = deque((N - 1, ))
max_fares = [None] * N
max_fares[N - 1] = 0
while queue:
	cur = queue.pop()
	fare = max_fares[cur]
	for n, a, b in graph[cur]:
		n_fare = fare + a
		if max_fares[n] == None or max_fares[n] > n_fare:
			max_fares[n] = n_fare
			queue.append(n)

exchanges = []
for _ in range(N):
	c, d = map(int, input().strip().split())
	exchanges.append((c, d))

MAX_FARE = M * 50

queue = deque(((0, 0, S),))

state_table = [[None] * (max_fares[i] + 1) for i in range(N)]

while queue:
	cur, time, money = queue.popleft()
	count, d_time = exchanges[cur]
	if cur == N - 1:
		continue
	for n, a, b in graph[cur]:
		n_money = money - a
		n_time = time + b
		states = state_table[n]
		max_fare = max_fares[n]
		while True:
			if n_money >= 0:
				if n_money > max_fare:
					n_money = max_fare
				if states[n_money] == None or states[n_money] > n_time:
					states[n_money] = n_time
					queue.append((n, n_time, n_money))
				if n_money >= max_fare:
					break
			n_money += count
			n_time += d_time


#for i in range(N):
#	print(i, state_table[i])

for i in range(1, N):
	states = state_table[i]
	minimum = None
	for t in states:
		if t != None and (minimum == None or minimum > t):
			minimum = t
	print(minimum)

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heapify, heappop, heappush

def solve():
    input = sys.stdin.readline
    N, M, S = map(int, input().split())
    Edge = [[] for _ in range(N)] #time, nextnode, cost
    for _ in range(M):
        u, v, a, b = map(int, input().split())
        Edge[u-1].append((b, v-1, a))
        Edge[v-1].append((b, u-1, a))
    exchange = [None] * N #c枚, Dmin
    for i in range(N):
        exchange[i] = [int(c) for c in input().split()]
    Ans = [-1] * N
    q = []
    heapify(q)
    heappush(q, (0, 0, S, 0, [0] * N)) #currentTime, node, moneyLeft, visited(bit)
    visitCount = 0
    while q:
        cT, nn, mL, v, rep = heappop(q)
        if Ans[nn] == -1: 
            Ans[nn] = cT
            visitCount += 1
            if visitCount == N: break
        if visitCount < rep[nn]: continue
        newrep = [rep[i] for i in range(N)]
        newrep[nn] += 1
        for time, nextnode, paycost in Edge[nn]:
            tv = (v | (1 << nn))
            if mL >= paycost: heappush(q, (cT + time, nextnode, mL - paycost, tv, newrep))
            else:
                toAdd = paycost - mL
                addS = 0
                minExchangeTime = 10 ** 20
                for i in range(N):
                    if (tv & (1 << i)) == (1 << i):
                        c, d = exchange[i]
                        gold = (toAdd - 1) // c + 1
                        if gold * d < minExchangeTime:
                            minExchangeTime = gold * d
                            addS = gold * c
                        elif gold * d == minExchangeTime:
                            if addS < gold * c: addS = gold * c
                heappush(q, (cT + time + minExchangeTime, nextnode, mL + addS - paycost, tv, newrep))

    print("\n".join(map(str, Ans[1:])))

    return 0

if __name__ == "__main__":
    solve()