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: Accepted

Solution code:
def main():
    import heapq
    inf = 10**16
    n, m, s = map(int, input().split())
    uvab = [list(map(int, input().split())) for _ in [0]*m]
    cd = [list(map(int, input().split())) for _ in [0]*n]
    g = [[] for _ in [0]*n]
    [g[a-1].append([b-1, c, d]) for a, b, c, d in uvab]
    [g[b-1].append([a-1, c, d]) for a, b, c, d in uvab]
    vertex = [[inf]*2501 for _ in [0]*n]
    h = [(0, 0, min(s, 2500))]  # 時刻、位置、所持金
    heapq.heapify(h)
    while h:
        t, p, money = heapq.heappop(h)
        if vertex[p][money] != inf:
            continue
        vertex[p][money] = t
        newmoney = min(money+cd[p][0], 2500)
        if vertex[p][newmoney] == inf:
            heapq.heappush(h, (t+cd[p][1], p, newmoney))
        for a, b, c in g[p]:  # 行き先、運賃、時間
            if money < b:
                continue
            if vertex[a][money-b] != inf:
                continue
            heapq.heappush(h, (t+c, a, money-b))
    for i in vertex[1:]:
        print(min(i))


main()

Submission status: Accepted

Solution code:
n,m,s = map(int,input().split())
road = [[] for _ in range(n)]
#print(road)
for _ in range(m):
  u,v,a,b = map(int,input().split())
  u -= 1
  v -= 1
  road[u].append([v,a,b])
  road[v].append([u,a,b])
#print(road)
coin = []
for _ in range(n):
  c,d = map(int,input().split())
  coin.append([c,d])
if s >= 2500:
  s = 2499
inf = 10**18
#print('#')
arr = [[inf for _ in range(2500)] for _ in range(n)]
c,d = coin[0]
#print(c,d)
#print(len(arr[0]))
for i in range(2500):
  if i <= s:
    arr[0][i] = 0
  elif i - c < 0:
    arr[0][i] = arr[0][0]+d
  else:
    arr[0][i] = arr[0][i-c]+d
now = {0}
#print(road)
for _ in range(50):
  #print(now)
  last = now
  now = set()
  for x in last:
    for y in road[x]:
      #print('#',x,y)
      v,a,b = y
      now.add(v)
      c,d = coin[v]
      for i in range(2500):
        if i + a < 2500:
          arr[v][i] = min(arr[v][i],arr[x][i+a]+b)
      for i in range(2500):
        if i - c < 0:
          arr[v][i] = min(arr[v][i],arr[v][0]+d)
        else:
          arr[v][i] = min(arr[v][i],arr[v][i-c]+d)
for ii in range(1,n):
  print(arr[ii][0])
#print(arr[0])

Submission status: Accepted

Solution code:
import heapq

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

E = [[] for _ in range(N)]
A = [[0]*N for _ in range(N)]
B = [[0]*N for _ in range(N)]
for i in range(M):
    U, V, a, b = map(int, input().split())
    u = U-1
    v = V-1
    E[u].append(v)
    E[v].append(u)
    A[u][v] = A[v][u] = a
    B[u][v] = B[v][u] = b

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

M = 50*N
T = [[-1]*M for _ in range(N)]
h = []
heapq.heappush(h, (0, 0, min(M-1, S))) # (time, inode, snode)
while h:
    dmin, inode, snode = heapq.heappop(h)
    if T[inode][snode]!=-1: continue
    T[inode][snode] = dmin

    # (inode,snode) -> (enode, snode-a) with time b
    for enode in E[inode]:
        a = A[inode][enode]
        b = B[inode][enode]
        esnode = snode-a
        if esnode<0 or T[enode][esnode]!=-1: continue
        heapq.heappush(h, (dmin+b, enode, esnode))

    # (inode, snode) -> (inode, snode+c) with time d
    c = C[inode]
    d = D[inode]
    snode_c = min(M-1, snode+c)
    if T[inode][snode_c]!=-1: continue
    heapq.heappush(h, (dmin+d, inode, snode_c))

for inode in range(1, N):
    print(min([x for x in T[inode] if x>=0]))

Submission status: Accepted

Solution code:
n,m,s = map(int,input().split())
road = [[] for _ in range(n)]
#print(road)
for _ in range(m):
  u,v,a,b = map(int,input().split())
  u -= 1
  v -= 1
  road[u].append([v,a,b])
  road[v].append([u,a,b])
#print(road)
coin = []
for _ in range(n):
  c,d = map(int,input().split())
  coin.append([c,d])
if s >= 2500:
  s = 2499
inf = 10**18
#print('#')
arr = [[inf for _ in range(2500)] for _ in range(n)]
c,d = coin[0]
#print(c,d)
#print(len(arr[0]))
for i in range(2500):
  if i <= s:
    arr[0][i] = 0
  elif i - c < 0:
    arr[0][i] = arr[0][0]+d
  else:
    arr[0][i] = arr[0][i-c]+d
now = {0}
#print(road)
for _ in range(100):
  #print(now)
  last = now
  now = set()
  for x in last:
    for y in road[x]:
      #print('#',x,y)
      v,a,b = y
      now.add(v)
      c,d = coin[v]
      for i in range(2500):
        if i + a < 2500:
          arr[v][i] = min(arr[v][i],arr[x][i+a]+b)
      for i in range(2500):
        if i - c < 0:
          arr[v][i] = min(arr[v][i],arr[v][0]+d)
        else:
          arr[v][i] = min(arr[v][i],arr[v][i-c]+d)
for ii in range(1,n):
  print(arr[ii][0])
#print(arr[0])

Submission status: Accepted

Solution code:
import heapq
inf = 10**18
def dijkstra(s, n, G):#スタート, 頂点数, グラフ:[[(cost, v)], ...]
    dist = [inf]*n
    edges = []#(sからvまでのコストの候補, v)
    dist[s] = 0
    for e in G[s]:
        heapq.heappush(edges, e)
    while edges:
        cost, v = heapq.heappop(edges)
        if dist[v] != inf:
            continue
        dist[v] = cost
        for c, nv in G[v]:
            if dist[nv] == inf:
                heapq.heappush(edges, (cost + c, nv))
    return dist
mx = 5005
n, m, s = map(int, input().split())
g = [[] for _ in range(n*mx)]
for i in range(m):
    u, v, a, b = map(int, input().split())
    u-=1
    v-=1
    for j in range(mx):
        if j>=a:
            g[u*mx+j].append((b, v*mx+j-a))
            g[v*mx+j].append((b, u*mx+j-a))
for i in range(n):
    c, d = map(int, input().split())
    for j in range(mx-c):
        g[i*mx+j].append((d, i*mx+j+c))
dist = dijkstra(min(s, mx-1), len(g), g)
for i in range(1, n):
    res = inf
    for j in range(mx):
        res = min(res, dist[i*mx+j])
    print(res)

Submission status: Accepted

Solution code:
import heapq
from collections import defaultdict
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines

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

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

c, d = [-1], [-1]
for i in range(n):
    c_, d_ = map(int, input().split())
    c.append(c_)
    d.append(d_)

ans = [-1] * (n+1)
dp = [{} for _ in range(n+1)]
coin_max = [-1] * (n+1)

h = [(0, s, 1)]
heapq.heapify(h)

while heapq:
    t, coin, city = heapq.heappop(h)

    if ans[city] == -1:
        ans[city] = t
        if all([v >= 0 for v in ans[2:]]):
            break

    if coin not in dp[city]:
        dp[city][coin] = t
    else:
        continue

    if coin_max[city] >= coin:
        continue
    else:
        coin_max[city] = coin

    for neighbor, a, b in connect[city]:
        if coin - a >= 0 and neighbor != city:
            if coin-a not in dp[neighbor]:
                heapq.heappush(h, (t+b, coin-a, neighbor))

    if coin+c[city] not in dp[city]:
        heapq.heappush(h, (t+d[city], coin+c[city], city))

print('\n'.join(map(str, ans[2:])))

Submission status: Accepted

Solution code:
n, m, s = [int(i) for i in input().split()]

e = []
for _ in range(m):
    u, v, a, b = [int(i) for i in input().split()]
    u -= 1
    v -= 1
    e.append([u, v, a, b])

co = [[int(i) for i in input().split()] for _ in range(n)]

dp = [[10 ** 18] * 6000 for _ in range(n)]
dp[0][min(5999,s)] = 0
for i in range(6000):
    if i + co[0][0] < 6000:
        dp[0][i + co[0][0]] = min(dp[0][i + co[0][0]], dp[0][i] + co[0][1])

for _ in range(n):
    for u, v, a, b in e:
        for j in range(a, 6000):
            dp[v][j - a] = min(dp[v][j - a], dp[u][j] + b)
        for i in range(6000):
            if i + co[v][0] < 6000:
                dp[v][i + co[v][0]] = min(dp[v][i + co[v][0]], dp[v][i] + co[v][1])

        for j in range(a, 6000):
            dp[u][j - a] = min(dp[u][j - a], dp[v][j] + b)
        for i in range(6000):
            if i + co[u][0] < 6000:
                dp[u][i + co[u][0]] = min(dp[u]
                                          [i + co[u][0]], dp[u][i] + co[u][1])

for i in range(1, n):
    print(min(dp[i]))

Submission status: Accepted

Solution code:
from heapq import heappush, heappop


def dijkstra(graph: list, n: int, v_s: int, INF: int = float('inf')) -> list:
    # graph[v_from] = [(cost, v_to), ...]
    dist = [INF] * n

    dist[v_s] = 0
    heap = [(0, v_s)]  # heap = [(dist[v], v), ...]
    while heap:
        dist2v, v_from = heappop(heap)
        if dist[v_from] < dist2v:
            continue
        for cost, v_to in graph[v_from]:
            dist_cand = dist2v + cost
            if dist_cand < dist[v_to]:
                dist[v_to] = dist_cand
                heappush(heap, (dist[v_to], v_to))
    return dist


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

MAX_SILVER = 5005
n2 = MAX_SILVER * n
graph = [[] for _ in range(n2)]
for _ in range(m):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    for k in range(a, MAX_SILVER):
        graph[u * MAX_SILVER + k].append((b, v * MAX_SILVER + k - a))
        graph[v * MAX_SILVER + k].append((b, u * MAX_SILVER + k - a))
for i in range(n):
    c, d = map(int, input().split())
    for k in range(MAX_SILVER - 1):
        graph[i * MAX_SILVER + k].append(
            (d, i * MAX_SILVER + min(k + c, MAX_SILVER - 1)))

dist = dijkstra(graph, n2, 0 + min(s, MAX_SILVER - 1))

for i in range(1, n):
    ans_i = 10**20
    for k in range(MAX_SILVER):
        ans_i = min(ans_i, dist[i * MAX_SILVER + k])
    print(ans_i)

Submission status: Accepted

Solution code:
import sys, heapq
def input():
	return sys.stdin.readline()[:-1]

class DijkstraList():
	#隣接リスト版
	#同一頂点の複数回探索を防ぐため訪問した頂点数を変数cntで持つ
	def __init__(self, adj, start):
		self.list = adj
		self.start = start
		self.size = len(adj)

	def solve(self):
		self.dist = [10**30 for _ in range(self.size)]
		self.dist[self.start] = 0
		self.prev = [-1 for _ in range(self.size)]
		self.q = []
		self.cnt = 0

		heapq.heappush(self.q, (0, self.start))

		while self.q and self.cnt < self.size:
			u_dist, u = heapq.heappop(self.q)
			if self.dist[u] < u_dist:
				continue
			for v, w in self.list[u]:
				if self.dist[v] > u_dist + w:
					self.dist[v] = u_dist + w
					self.prev[v] = u
					heapq.heappush(self.q, (self.dist[v], v))
			self.cnt += 1
		return

	def distance(self, goal):
		return self.dist[goal]

	def path(self, goal):
		self.path = [goal]
		while self.path[-1] != self.start:
			self.path.append(self.prev[self.path[-1]])
		return self.path[::-1]

INF = 10**20
n, m, s = map(int, input().split())
s = min(s, m*50)
adj = [[] for _ in range(n*(m+1)*50)]

for _ in range(m):
	u, v, a, b = map(int, input().split())
	u, v = u-1, v-1
	for i in range(a, m*50+1):
		adj[i * n + u].append(((i - a) * n + v, b))
		adj[i * n + v].append(((i - a) * n + u, b))

for i in range(n):
	c, d = map(int, input().split())
	for j in range(m*50):
		adj[j * n + i].append((min(m*50, j + c) * n + i, d))

dijk = DijkstraList(adj, s*n)
dijk.solve()
ans = [INF for _ in range(n)]
for num, x in enumerate(dijk.dist):
	i = num%n
	ans[i] = min(ans[i], x)
print(*ans[1:], sep="\n")

Submission status: Accepted

Solution code:
from queue import PriorityQueue
from collections import defaultdict
from heapq import heappush, heappop

n, m, s = map(int, input().split())
graph = defaultdict(dict)
for i in range(m):
    u, v, a, b = map(int, input().split())
    graph[u][v] = (a, b)
    graph[v][u] = (a, b)

town = [None]*(n+1)
for i in range(n):
    c, d = map(int, input().split())
    town[i+1] = (c, d)

if s >= 2501:
    s = 2501
x = (1, s)
cost = 0
visit = set()
heap = []
heappush(heap, (cost, x))
ans = [None]*(n+1)
check = 0
while len(heap) > 0:
    cost, x = heappop(heap)
    if x in visit:
        continue
    visit.add(x)
    p, m = x
    if ans[p] is None:
        ans[p] = cost
        check += 1
        if check >= n:
            break
    c, d = town[p]
    if m <= 2501:
        heappush(heap, (cost+d, (p, m+c)))
    for q, edge in graph[p].items():
        a, b = edge
        if m-a >= 0:
            heappush(heap, (cost+b, (q, m-a)))
for i in range(2, n+1):
    print(ans[i])

Submission status: Accepted

Solution code:
from heapq import heappop, heappush, heapify
from collections import deque

class Graph():  #directed
    def __init__(self, n, edge):
        self.n = n
        self.graph = [[] for _ in range(n)]
        self.deg = [0 for _ in range(n)]
        for e in edge:
            self.graph[e[0]].append((e[1], e[2]))
            self.deg[e[1]] += 1

    def dijkstra(self, s, INF=10**18):
        dist = [INF for _ in range(self.n)]
        dist[s] = 0
        heap = [(0, s)]
        while heap:
            cost, node = heappop(heap)
            if dist[node] < cost:
                continue
            for adj, adjcost in self.graph[node]:
                if dist[node] + adjcost < dist[adj]:
                    dist[adj] = dist[node] + adjcost
                    heappush(heap, (dist[adj], adj))
        return dist

N, M, S = map(int, input().split())
T = [tuple(map(int, input().split())) for _ in range(M)]
C = [tuple(map(int, input().split())) for _ in range(N)]

node = [[0 for j in range(2500)] for i in range(N)]
E = []

for i in range(M):
    u, v, a, b = T[i]
    u -= 1
    v -= 1
    for c in range(2500):
        if c - a >= 0:
            E.append((2500 * u + c, 2500 * v + c - a, b))
            E.append((2500 * v + c, 2500 * u + c - a, b))

for i in range(N):
    a, b = C[i]
    for c in range(2500):
        if c + a < 2500:
            E.append((2500 * i + c, 2500 * i + c + a, b))
        else:
            E.append((2500 * i + c, 2500 * i + 2499, b))

G = Graph(2500 * N, E)
D = G.dijkstra(min(2499, S))

for i in range(N):
    if i == 0:
        continue
    res = 10**18
    for j in range(2500):
        res = min(res, D[i * 2500 + j])
    print(res)

Submission status: Accepted

Solution code:
import heapq
import sys
input = sys.stdin.readline

INF = 10**20
A = 50  # max A


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


def main():
    N, M, S = inpl()
    S = min(S, M * A)

    lines = [[] for _ in range(N * (M * A + 1))]
    for _ in range(M):
        in_s, in_t, cost, time = inpl()
        in_s -= 1
        in_t -= 1

        for n in range(cost, M * A + 1):
            s = in_s + n * N
            t = in_t + (n - cost) * N
            lines[s].append((t, time))

            s = in_s + (n - cost) * N
            t = in_t + n * N
            lines[t].append((s, time))

    for i in range(N):
        cost, time = inpl()
        for n in range(0, M * A + 1):
            s = i + n * N
            if n + cost > M * A:
                t = i + (M * A) * N
            else:
                t = i + (n + cost) * N
            lines[s].append((t, time))

    def dijkstra(N, S):
        weight = [INF] * N
        weight[S] = 0
        q = [[0, S]]
        heapq.heapify(q)
        while q:
            w0, s = heapq.heappop(q)
            for t, w in lines[s]:
                w += w0
                if weight[t] > w:
                    heapq.heappush(q, [w, t])
                    weight[t] = w

        return weight

    weight = dijkstra(N * (M * A + 1), 0 + S * N)

    ansl = [INF] * N
    for i, w in enumerate(weight):
        n = i % N
        if n == 0:
            continue
        else:
            ansl[n] = min(w, ansl[n])

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import heapq
from collections import defaultdict as dd
from bisect import bisect_left
N, M, S = map(int, input().split())
costs = dd(dict)
times = dd(dict)
MAX = 0
for _ in range(M):
    u, v, a, b = map(int, input().split())
    MAX += a
    costs[u][v] = costs[v][u] = a
    times[u][v] = times[v][u] = b
Cs = [0]
Ds = [0]
for _ in range(N):
    c, d = map(int, input().split())
    Cs.append(c)
    Ds.append(d)

thres = [[] for _ in range(N+1)]
vals = [[] for _ in range(N+1)]

q = []
heapq.heappush(q, (0, 1, S))
while q:
    if all(thres):
        break
    c, i, m = heapq.heappop(q)
    if thres[i] and thres[i][-1] >= m:
        continue
    thres[i].append(m)
    vals[i].append(c)
    for to in costs[i].keys():
        cost = costs[i][to]
        t = times[i][to]
        if m >= cost:
            heapq.heappush(q, (c+t, to, m-cost))

    if m < MAX:
        heapq.heappush(q, (c+Ds[i], i, m+Cs[i]))

for i in range(2, N+1):
    print(vals[i][0])

Submission status: Accepted

Solution code:
class Dijkstra():
    """ ダイクストラ法
    重み付きグラフにおける単一始点最短路アルゴリズム

    * 使用条件
        - 負のコストがないこと
        - 有向グラフ、無向グラフともにOK

    * 計算量はO(E*log(V))

    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """
    class Edge():
        """ 重み付き有向辺 """
        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        """ 重み付き有向辺
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい

        Args:
            V(int): 頂点の数
        """
        self.G = [[] for i in range(V)]  # 隣接リストG[u][i] := 頂点uのi個目の隣接辺
        self._E = 0  # 辺の数
        self._V = V  # 頂点の数

    @property
    def E(self):
        """ 辺数
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return self._E

    @property
    def V(self):
        """ 頂点数 """
        return self._V

    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.G[_from].append(self.Edge(_to, _cost))
        self._E += 1

    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路を格納したリストを返す
        Args:
            s(int): 始点s
        Returns:
            d(list): d[i] := 始点sから頂点iまでの最短コストを格納したリスト。
                     到達不可の場合、値はfloat("inf")
        """
        import heapq
        que = []  # プライオリティキュー（ヒープ木）
        d = [float("inf")] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))  # 始点の(最短距離, 頂点番号)をヒープに追加する

        while len(que) != 0:
            cost, v = heapq.heappop(que)
            # キューに格納されている最短経路の候補がdの距離よりも大きければ、他の経路で最短経路が存在するので、処理をスキップ
            if d[v] < cost: continue

            for i in range(len(self.G[v])):
                # 頂点vに隣接する各頂点に関して、頂点vを経由した場合の距離を計算し、今までの距離(d)よりも小さければ更新する
                e = self.G[v][i]  # vのi個目の隣接辺e
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost  # dの更新
                    heapq.heappush(que, (d[e.to], e.to))  # キューに新たな最短経路の候補(最短距離, 頂点番号)の情報をpush
        return d

N,M,S=map(int,input().split())
pro=Dijkstra(N*5001)
for i in range(0,M):
    u,v,a,b=map(int,input().split())
    for j in range(a,5001):
        pro.add(N*j+u-1,N*(j-a)+v-1,b)
        pro.add(N*j+v-1,N*(j-a)+u-1,b)

for i in range(0,N):
    c,d=map(int,input().split())
    for j in range(0,5000):
        to=min(5000,j+c)
        pro.add(N*j+i,N*to+i,d)

S=min(5000,S)
ans=pro.shortest_path(N*S)
for i in range(1,N):
    p=float("inf")
    for j in range(0,5001):
        p=min(p,ans[N*j+i])
    print(p)

Submission status: Accepted

Solution code:
import heapq

INF = 10**20
A = 50  # max A


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


def main():
    N, M, S = inpl()
    S = min(S, M * A)

    lines = [[] for _ in range(N * (M * A + 1))]
    for _ in range(M):
        in_s, in_t, cost, time = inpl()
        in_s -= 1
        in_t -= 1

        for n in range(cost, M * A + 1):
            s = in_s + n * N
            t = in_t + (n - cost) * N
            lines[s].append((t, time))

            s = in_s + (n - cost) * N
            t = in_t + n * N
            lines[t].append((s, time))

    for i in range(N):
        cost, time = inpl()
        for n in range(0, M * A + 1):
            s = i + n * N
            if n + cost > M * A:
                t = i + (M * A) * N
            else:
                t = i + (n + cost) * N
            lines[s].append((t, time))

    def dijkstra(N, S):
        weight = [INF] * N
        weight[S] = 0
        q = [[0, S]]
        heapq.heapify(q)
        while q:
            w0, s = heapq.heappop(q)
            for t, w in lines[s]:
                w += w0
                if weight[t] > w:
                    heapq.heappush(q, [w, t])
                    weight[t] = w

        return weight

    weight = dijkstra(N * (M * A + 1), 0 + S * N)

    ansl = [INF] * N
    for i, w in enumerate(weight):
        n = i % N
        if n == 0:
            continue
        else:
            ansl[n] = min(w, ansl[n])

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,m,s = map(int,input().split())

uvab = [tuple(map(int,input().split())) for _ in range(m)]
cd = [tuple(map(int,input().split())) for _ in range(n)]

links = [[] for _ in range(5001 * n)]
for tmp in uvab:
    u,v,a,b = tmp
    u -= 1
    v -= 1
    for i in range(4999,0,-1):
        if(i-a >= 0):
            links[u*5001+i].append((b, v*5001+i-a))
            links[v*5001+i].append((b, u*5001+i-a))
        else:
            break
    links[u*5001+5000].append((b, v*5001+5000))
    links[v*5001+5000].append((b, u*5001+5000))

for i,tmp in enumerate(cd):
    c,d = tmp
    for j in range(5000):
        links[i*5001+j].append((d ,i*5001 + min(j+c, 5000)))

# dijkstra
import heapq
def dijkstra(links, start, n):
    inf = 10**10
    d = [inf] * (n)
    d[start] = 0
    hq = []
    used = set()
    used.add(start)
    for i in links[start]:
        heapq.heappush(hq, i)
    while(hq):
        cost,i = heapq.heappop(hq)
        if( i in used):
            continue
        d[i] = cost
        used.add(i)
        for tmp in links[i]:
            cost_next, j = tmp
            if(not j in used):
                heapq.heappush(hq, (cost+cost_next, j))
    return d

s = min(s, 5000)
d = dijkstra(links, s, 5001*n)
for i in range(1,n):
    ans = d[i*5001]
    for j in range(1,5001):
        ans = min(ans, d[i*5001+j])
    print(ans)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
N, M, S = map(int, readline().split())

from heapq import heappop as hpp, heappush as hp
def dijkstra(N, s, Edge):
    # Edge は　(cost, vf) の形
    inf = 10**18
    dist = [inf] * N
    dist[s] = 0
    Q = [(0, s)]
    while Q:
        dn, vn = hpp(Q)
        if dn > dist[vn]:
            continue
        for df, vf in Edge[vn]:
            if dist[vn] + df < dist[vf]:
                dist[vf] = dist[vn] + df
                hp(Q, (dn + df,vf))
    return dist

geta = 2451
Edge = [[] for _ in range(N*geta)]
S = min(S, geta - 1)
for m in range(M):
    u, v, a, b = map(int, readline().split())
    u -= 1
    v -= 1
    for mon in range(a, geta):
        Edge[u*geta+mon].append((b, v*geta + (mon - a)))
        Edge[v*geta+mon].append((b, u*geta + (mon - a)))

for n in range(N):
    c, d = map(int, readline().split())
    for mon in range(geta):
        Edge[n*geta + mon].append((d, n*geta + min(geta-1, mon + c)))

dist = dijkstra(N*geta, S, Edge) 
INF = 10**18
ans = [INF]*N
for i in range(N*geta):
    ans[i//geta] = min(ans[i//geta], dist[i])
print('\n'.join(map(str, ans[1:])))

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
import sys
input = sys.stdin.readline

def dijkstra(edges, size, source):
    distance = [float('inf')] * size
    distance[source] = 0
    visited = [False] * size
    pq = []
    heappush(pq, (0, source))
    while pq:
        dist_v, v = heappop(pq)
        visited[v] = True
        for u, weight in edges[v]:
            if not visited[u]:
                new_dist = dist_v + weight
                if distance[u] > new_dist:
                    distance[u] = new_dist
                    heappush(pq, (new_dist, u))
    return distance

def main():
    N, M, S = map(int, input().split())
    AB = [[None] * N for _ in range(N)]
    s = 0
    for _ in range(M):
        U, V, A, B = map(int, input().split())
        U -= 1
        V -= 1
        AB[U][V] = AB[V][U] = (A, B)
        s += A
    MAX = s + 1
    CD = [tuple(map(int, input().split())) for _ in range(N)]
    edges = [[] for _ in range(N*MAX)]
    for v in range(N):
        C, D = CD[v]
        for i in range(MAX-1):
            edges[v*MAX+i].append((min(v*MAX+i+C, (v+1)*MAX-1), D))
    for u in range(N-1):
        for v in range(u+1, N):
            if not AB[u][v]:
                continue
            A, B = AB[u][v]
            for i in range(A, MAX):
                edges[u*MAX+i].append((v*MAX+i-A, B))
                edges[v*MAX+i].append((u*MAX+i-A, B))
    dist = dijkstra(edges, N*MAX, min(S, MAX-1))
    for v in range(1, N):
        print(min(dist[v*MAX:(v+1)*MAX]))
main()

Submission status: Accepted

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    import heapq
    input = sys.stdin.buffer.readline

    def dijkstra(adj, start):
        # adj: [[to, cost] * vertices], 0th index must be empty
        inf = 1 << 60
        dist = [inf] * len(adj)
        dist[start] = 0
        q = []
        heapq.heappush(q, (0, start))
        while q:
            min_dist, v_from = heapq.heappop(q)
            if min_dist > dist[v_from]:
                continue
            v_tos = adj[v_from]
            for v_to, cost in v_tos:
                if min_dist + cost < dist[v_to]:
                    dist[v_to] = min_dist + cost
                    heapq.heappush(q, (dist[v_to], v_to))
        return dist

    N, M, S = map(int, input().split())
    K = 5001
    adj = [[] for _ in range(N * K + 1)]
    for _ in range(M):
        u, v, a, b = map(int, input().split())
        for j in range(a, K):
            uu = (u-1) * K + j + 1
            vv = (v-1) * K + (j-a) + 1
            adj[uu].append((vv, b))
            uu = (u - 1) * K + (j-a) + 1
            vv = (v - 1) * K + j + 1
            adj[vv].append((uu, b))
    for i in range(1, N+1):
        c, d = map(int, input().split())
        for j in range(K-1):
            adj[(i-1) * K + j + 1].append(((i-1) * K + min(j+c, K-1) + 1, d))

    S = min(5000, S)
    dist = dijkstra(adj, S + 1)
    for v in range(2, N+1):
        ans = 10**18
        for j in range(K):
            ans = min(ans, dist[(v-1) * K + j + 1])
        print(ans)


if __name__ == '__main__':
    main()