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:
import sys,bisect,string,math,time,functools,random
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            a,b,c=(inp+[1])[:3]
            org_inp.append(inp)
        else:
            #index=0
            a,b,c=(list(ls[i])+[1])[:3]
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)];rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()

class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]

    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo

show_flg=False
show_flg=True


## Segment Tree ##

## Initializer Template ##
# Range Sum:        sg=SegTree(n)
# Range Minimum:    sg=SegTree(n,inf,min,inf)

class SegTree:

    def __init__(self,n,init_ls=None,init_val=0,function=lambda a,b:a+b,ide=0):
        self.n=n
        self.ide_ele=ide_ele=ide
        self.num=num=2**(n-1).bit_length()
        self.seg=seg=[self.ide_ele]*2*self.num
        self.lazy=lazy=[self.ide_ele]*2*self.num
        self.segfun=segfun=function
        #set_val
        if init_ls==None:
            for i in range(n):
                self.seg[i+self.num-1]=init_val
        else:
            for i in range(n):
                self.seg[i+self.num-1]=init_ls[i]
        #build
        for i in range(self.num-2,-1,-1):
            self.seg[i]=self.segfun(self.seg[2*i+1],self.seg[2*i+2])
    
    def update(self,k,x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfun(self.seg[k*2+1],self.seg[k*2+2])
        
    def evaluate(k,l,r): #遅延評価処理
        if lazy[k]!=0:
            node[k]+=lazy[k]
            if(r-l>1):
                lazy[2*k+1]+=lazy[k]//2
                lazy[2*k+2]+=lazy[k]//2

        lazy[k]=0
        
    def query(self,p,q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfun(res,self.seg[p])
            if q&1 == 1:
                res = self.segfun(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfun(res,self.seg[p])
        else:
            res = self.segfun(self.segfun(res,self.seg[p]),self.seg[q])
        return res
    
    def find_min_index(self,p,q,m):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfun(res,self.seg[p])
            if q&1 == 1:
                res = self.segfun(res,self.seg[q])
                q -= 1
            p >>= 1
            q = (q-1)//2
        if p == q:
            res = self.segfun(res,self.seg[p])
        else:
            res = self.segfun(self.segfun(res,self.seg[p]),self.seg[q])
        return res


    def __str__(self):
        # 生配列を表示
        rt=self.seg[self.num-1:self.num-1+self.n]
        return str(rt)

class Tree:
    def __init__(self,inp_size=None,init=True):
        if init:
            self.stdin(inp_size)
        return

    def stdin(self,inp_size=None):
        if inp_size==None:
            self.size=int(input())
        else:
            self.size=inp_size
        self.edges,_=GI(self.size,self.size-1)
        return
    
    def listin(self,ls):
        self.size=len(ls)+1
        self.edges,_=GI(self.size,self.size-1,ls)
        return

    def __str__(self):
        return  str(self.edges)

    def dfs(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
        q=deque()
        q.append(x)
        v=[-1]*self.size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==-1:
                    q.append(nb)
                    v[nb]=func(v[c],nb,d)
        return v

    def EulerTour(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
        q=deque()
        q.append((-1,x))
        v=[None]*self.size
        v[x]=root_v
        et=[]
        while q:
            cb,ce=q.pop()
            et.append(ce)
            for nb,d in self.edges[ce]:
                if v[nb]==None:
                    q.append((nb,ce))
                    q.append((ce,nb))
                    v[nb]=func(v[ce],nb,d)
        vid=[[-1,-1]for i in range(self.size)]
        for i,j in enumerate(et):
            if vid[j][0]==-1:
                vid[j][0]=i
            else:
                vid[j][1]=i
        return v,et,vid
    
    def LCA_init(self,depth,et):
        self.st=SegTree(self.size*2-1,func=min,ide=inf)
        for i,j in enumerate(et):
            self.st.update(i,j)
        self.LCA_init_stat==True
        return
    
    def LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            depth,et,vid=self.EulerTour(root)
            self.LCA_init(depth,et)
        return self.st.query(x,y+1)

def dijkstra(edge,st):
    # edge=[[(v_to,dist_to_v),...],[],...]
    # initialize: def: d=dist(st,i), prev=[previous vertex in minimum path], q[]
    n=len(edge)
    d=[(0 if st==i else inf) for i in range(n)]
    prev=[0]*n
    q=[(j,i) for i,j in enumerate(d)]
    heapify(q)
    
    # calc
    while q:
        dist,cur=heappop(q)
        for dst,dist in edge[cur]:
            alt=d[cur]+dist
            if alt<d[dst]:
                d[dst]=alt
                prev[dst]=cur
                heappush(q,(alt,dst))
    return d,prev


ans=0

n,m,s=LI()
t_ls=[]
p_ls=[]
k=2501
s=min(k-1,s)
for i in range(m):
    u,v,a,b=LI()
    p_ls+=[(u,v,a)]
    u-=1
    v-=1
    for j in range(a,k):
        t_ls+=[(u*k+j,v*k+j-a,b)]

C,D=[],[]
for i in range(n):
    c,d=LI()
    for j in range(k):
        t_ls+=[(i*k+j,i*k+min(j+c,k-1),d)]
    C+=[c]
    D+=[d]

gp,_=GI(n,m,ls=p_ls,index=1)
gt,_=GI(n*k,len(t_ls),ls=t_ls,index=0)

dist_t,_=dijkstra(gt,i*k+s)
for i in range(1,n):
    ans=inf
    for j in range(k):
        alt=dist_t[i*k+j]
        if alt<ans:
            ans=alt
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import networkx as nx

N, M, S = map(int, readline().split())
C = 500

edges = []
for _ in range(M):
    u, v, a, b = map(int, readline().split())
    for coin in range(a, C):
        edges.append(((u, coin), (v, coin - a), b))
        edges.append(((v, coin), (u, coin - a), b))

for u in range(1, N + 1):
    c, d = map(int, readline().split())
    for coin in range(C):
        edges.append(((u, coin), (u, min(coin + c, C-1)), d))


G = nx.DiGraph()
G.add_weighted_edges_from(edges)

Submission status: Wrong Answer

Solution code:
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra


def add_modified_edge(from_, to, time):
    modified_edges_from.append(from_)
    modified_edges_to.append(to)
    modified_edge_time.append(time)


def add_coin_charge_edge(city, bank, s):
    city_0_coin = city * MAX_COIN
    city_maxim_coin = city_0_coin + MAX_COIN-1

    coin, time = bank
    from_ = city_0_coin
    if city == 0:
        from_ = s
    while from_ < city_maxim_coin:
        to = min(from_ + coin, city_maxim_coin)
        add_modified_edge(from_, to, time)
        from_ = to


def expand_edge(from_, to, cost, time):
    with_0_coin_from = from_ * MAX_COIN
    with_0_coin_to = to * MAX_COIN

    for my_coin in range(cost, MAX_COIN):
        add_modified_edge(with_0_coin_from+my_coin, with_0_coin_to+my_coin-cost, time)
        add_modified_edge(with_0_coin_to+my_coin, with_0_coin_from+my_coin-cost, time)


n, m, s = map(int, input().split())
MAX_COIN = 50 * (n-1)
if s > MAX_COIN:
    s = MAX_COIN-1
edges = []
for _ in range(m):
    from_, to, cost, time = map(int, input().split())
    edges.append([from_-1, to-1, cost, time])

banks = []
for _ in range(n):
    coin, time = map(int, input().split())
    banks.append([coin, time])

modified_edges_from = [0]
modified_edges_to = [s]
modified_edge_time = [0]

for city, bank in enumerate(banks):
    add_coin_charge_edge(city, bank, s)

for natural_from, natural_to, cost, time in edges:
    expand_edge(natural_from, natural_to, cost, time)

csr = csr_matrix((modified_edge_time, (modified_edges_from, modified_edges_to)), (n*MAX_COIN, n*MAX_COIN))
results = dijkstra(csr, indices=0)

second_city = MAX_COIN
last_city = MAX_COIN * (n-1)
for to_city in range(second_city, last_city+1, MAX_COIN):
    print(int(min(results[to_city:to_city+MAX_COIN])))

Submission status: Wrong Answer

Solution code:
import networkx as nx

Submission status: Wrong Answer

Solution code:
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra


def add_modified_edge(from_, to, time):
    modified_edges_from.append(from_)
    modified_edges_to.append(to)
    modified_edge_time.append(time)


def add_coin_charge_edge(city, bank, s):
    city_0_coin = city * MAX_COIN
    city_maxim_coin = city_0_coin + MAX_COIN-1

    coin, time = bank
    from_ = city_0_coin
    if city == 0:
        from_ = s
    while from_ < city_maxim_coin:
        to = min(from_ + coin, city_maxim_coin)
        add_modified_edge(from_, to, time)
        from_ = to


def expand_edge(from_, to, cost, time):
    with_0_coin_from = from_ * MAX_COIN
    with_maxim_coin_from = with_0_coin_from + MAX_COIN-1
    with_0_coin_to = to * MAX_COIN
    with_maxim_coin_to = with_0_coin_to + MAX_COIN-1

    for with_coin_from in range(with_maxim_coin_from, with_0_coin_from+cost-1, -1):
        coin = with_coin_from % MAX_COIN - cost
        with_coin_to = with_0_coin_to + coin
        add_modified_edge(with_coin_from, with_coin_to, time)

    for with_coin_to in range(with_maxim_coin_to, with_0_coin_to+cost-1, -1):
        coin = with_coin_to % MAX_COIN - cost
        with_coin_from = with_0_coin_from + coin
        add_modified_edge(with_coin_to, with_coin_from, time)


n, m, s = map(int, input().split())
MAX_COIN = 50 * (n-1)
if s > MAX_COIN:
    s = MAX_COIN-1
edges = []
for _ in range(m):
    from_, to, cost, time = map(int, input().split())
    edges.append([from_-1, to-1, cost, time])

banks = []
for _ in range(n):
    coin, time = map(int, input().split())
    banks.append([coin, time])

modified_edges_from = [0]
modified_edges_to = [s]
modified_edge_time = [0]

for city, bank in enumerate(banks):
    add_coin_charge_edge(city, bank, s)

for natural_from, natural_to, cost, time in edges:
    expand_edge(natural_from, natural_to, cost, time)

csr = csr_matrix((modified_edge_time, (modified_edges_from, modified_edges_to)), (n*MAX_COIN, n*MAX_COIN))
results = dijkstra(csr, indices=0)

second_city = MAX_COIN
last_city = MAX_COIN * (n-1)
for to_city in range(second_city, last_city+1, MAX_COIN):
    print(int(min(results[to_city:to_city+MAX_COIN])))

Submission status: Wrong Answer

Solution code:
from scipy.sparse import coo_matrix
from scipy.sparse.csgraph import dijkstra


def add_modified_edge(from_, to, time):
    modified_edges_from.append(from_)
    modified_edges_to.append(to)
    modified_edge_time.append(time)


def add_coin_charge_edge(city, bank, s):
    city_0_coin = city * MAX_COIN
    city_maxim_coin = city_0_coin + MAX_COIN-1

    coin, time = bank
    from_ = city_0_coin
    if city == 0:
        from_ = s
    while from_ < city_maxim_coin:
        to = min(from_ + coin, city_maxim_coin)
        add_modified_edge(from_, to, time)
        from_ = to


def expand_edge(from_, to, cost, time):
    with_0_coin_from = from_ * MAX_COIN
    with_maxim_coin_from = with_0_coin_from + MAX_COIN-1
    with_0_coin_to = to * MAX_COIN
    with_maxim_coin_to = with_0_coin_to + MAX_COIN-1

    for with_coin_from in range(with_maxim_coin_from, with_0_coin_from+cost-1, -1):
        coin = with_coin_from % MAX_COIN - cost
        with_coin_to = with_0_coin_to + coin
        add_modified_edge(with_coin_from, with_coin_to, time)

    for with_coin_to in range(with_maxim_coin_to, with_0_coin_to+cost-1, -1):
        coin = with_coin_to % MAX_COIN - cost
        with_coin_from = with_0_coin_from + coin
        add_modified_edge(with_coin_to, with_coin_from, time)


n, m, s = map(int, input().split())
MAX_COIN = 50 * (n-1)
if s > MAX_COIN:
    s = MAX_COIN-1
edges = []
for _ in range(m):
    from_, to, cost, time = map(int, input().split())
    edges.append([from_-1, to-1, cost, time])

banks = []
for _ in range(n):
    coin, time = map(int, input().split())
    banks.append([coin, time])

modified_edges_from = [0]
modified_edges_to = [s]
modified_edge_time = [0]

for city, bank in enumerate(banks):
    add_coin_charge_edge(city, bank, s)

for natural_from, natural_to, cost, time in edges:
    expand_edge(natural_from, natural_to, cost, time)

csr = coo_matrix((modified_edge_time, (modified_edges_from, modified_edges_to)), (n*MAX_COIN, n*MAX_COIN)).tocsr()
results = dijkstra(csr, indices=0)

second_city = MAX_COIN
last_city = MAX_COIN * (n-1)
for to_city in range(second_city, last_city+1, MAX_COIN):
    print(int(min(results[to_city:to_city+MAX_COIN])))

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import networkx as nx

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

edges = []
for _ in range(M):
    u, v, a, b = map(int, readline().split())
    for coin in range(a, 2500):
        edges.append(((u, coin), (v, coin - a), b))
        edges.append(((v, coin), (u, coin - a), b))

for u in range(1, N + 1):
    c, d = map(int, readline().split())
    for coin in range(2500):
        edges.append(((u, coin), (u, min(coin + c, 2499)), d))

if S >= 2500:
    S = 2499


G = nx.DiGraph()
# G.add_weighted_edges_from(edges)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import networkx as nx

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

edges = []
for _ in range(M):
    u, v, a, b = map(int, readline().split())
    for coin in range(a, 2500):
        edges.append(((u, coin), (v, coin - a), b))
        edges.append(((v, coin), (u, coin - a), b))

for u in range(1, N + 1):
    c, d = map(int, readline().split())
    for coin in range(2500):
        edges.append(((u, coin), (u, min(coin + c, 2499)), d))

Submission status: Wrong Answer

Solution code:
n, m, s = map(int, input().split())
if s > 2850:
    s = 2850
start = s

from collections import defaultdict

G = defaultdict(list)

for _ in range(m):
    u, v, a, b = map(int, input().split())
    for i in range(2900):
        if i + a < 2900:
            G[(u - 1) * 3000 + i + a].append(((v - 1) * 3000 + i, b))
            G[(v - 1) * 3000 + i + a].append(((u - 1) * 3000 + i, b))

for j in range(n):
    c, d = map(int, input().split())
    for i in range(2900):
        if i + c < 2900:
            G[j * 3000 + i].append((j * 3000 + i + c, d))


# V: 頂点数
# g[v] = {(w, cost)}:
#     頂点vから遷移可能な頂点(w)とそのコスト(cost)
# r: 始点の頂点

from heapq import heappush, heappop

INF = 10 ** 10


def dijkstra(N, G, s):
    dist = [INF] * N
    que = [(0, s)]
    dist[s] = 0
    while que:
        c, v = heappop(que)
        if dist[v] < c:
            continue
        for t, cost in G[v]:
            if dist[v] + cost < dist[t]:
                dist[t] = dist[v] + cost
                heappush(que, (dist[t], t))
    return dist

dist = dijkstra(n*3000, G, start)

for i in range(1, n):
    print(min(dist[3000*i:3000*(i+1)+1]))

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import networkx as nx

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

edges = []
for _ in range(M):
    u, v, a, b = map(int, readline().split())
    for coin in range(a, 2500):
        edges.append(((u, coin), (v, coin - a), b))
        edges.append(((v, coin), (u, coin - a), b))

for u in range(1, N + 1):
    c, d = map(int, readline().split())
    for coin in range(2500):
        edges.append(((u, coin), (u, min(coin + c, 2499)), d))

if S >= 2500:
    S = 2499


G = nx.DiGraph()
G.add_weighted_edges_from(edges)

Submission status: Wrong Answer

Solution code:
n, m, s = map(int, input().split())
if s > 2850:
    s = 2850
start = s

from collections import defaultdict

G = defaultdict(list)

for _ in range(m):
    u, v, a, b = map(int, input().split())
    for i in range(2900):
        if i + a < 2900:
            G[(u - 1) * 3000 + i + a].append(((v - 1) * 3000 + i, b))
            G[(v - 1) * 3000 + i + a].append(((u - 1) * 3000 + i, b))

for j in range(n):
    c, d = map(int, input().split())
    for i in range(2900):
        if i + c < 2900:
            G[j * 3000 + i].append((j * 3000 + i + c, d))


# V: 頂点数
# g[v] = {(w, cost)}:
#     頂点vから遷移可能な頂点(w)とそのコスト(cost)
# r: 始点の頂点

from heapq import heappush, heappop

INF = 10 ** 10


def dijkstra(N, G, s):
    dist = [INF] * N
    que = [(0, s)]
    dist[s] = 0
    while que:
        c, v = heappop(que)
        if dist[v] < c:
            continue
        for t, cost in G[v]:
            if dist[v] + cost < dist[t]:
                dist[t] = dist[v] + cost
                heappush(que, (dist[t], t))
    return dist

dist = dijkstra(n*3000, G, start)

for i in range(1, n):
    print(min(dist[3000*i:3000*(i+1)]))

Submission status: Wrong Answer

Solution code:
n, m, s = map(int, input().split())
if s > 2850:
    s = 2850
start = s

from collections import defaultdict

G = defaultdict(list)

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

for j in range(n):
    c, d = map(int, input().split())
    for i in range(2900):
        G[j * 3000 + i].append((j * 3000 + i + c, d))


# V: 頂点数
# g[v] = {(w, cost)}:
#     頂点vから遷移可能な頂点(w)とそのコスト(cost)
# r: 始点の頂点

from heapq import heappush, heappop

INF = 10 ** 10


def dijkstra(N, G, s):
    dist = [INF] * N
    que = [(0, s)]
    dist[s] = 0
    while que:
        c, v = heappop(que)
        if dist[v] < c:
            continue
        for t, cost in G[v]:
            if dist[v] + cost < dist[t]:
                dist[t] = dist[v] + cost
                heappush(que, (dist[t], t))
    return dist

dist = dijkstra(n*3000, G, start)

for i in range(1, n):
    print(min(dist[3000*i:3000*(i+1)]))

Submission status: Wrong Answer

Solution code:
n, m, s = map(int, input().split())
if s > 3000:
    s = 2850
start = s

from collections import defaultdict

G = defaultdict(list)

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

for j in range(n):
    c, d = map(int, input().split())
    for i in range(2900):
        G[j * 3000 + i].append((j * 3000 + i + c, d))


# V: 頂点数
# g[v] = {(w, cost)}:
#     頂点vから遷移可能な頂点(w)とそのコスト(cost)
# r: 始点の頂点

from heapq import heappush, heappop

INF = 10 ** 10


def dijkstra(N, G, s):
    dist = [INF] * N
    que = [(0, s)]
    dist[s] = 0
    while que:
        c, v = heappop(que)
        if dist[v] < c:
            continue
        for t, cost in G[v]:
            if dist[v] + cost < dist[t]:
                dist[t] = dist[v] + cost
                heappush(que, (dist[t], t))
    return dist

dist = dijkstra(n*3000, G, start)

for i in range(1, n):
    print(min(dist[3000*i:3000*(i+1)]))

Submission status: Wrong Answer

Solution code:
z=lambda i,c:i+c*50;n,m,s=map(int,input().split());e=[[]for _ in range(1<<20)];from heapq import*;t=z(0,min(2500,s));d=[9**9]*(1<<20);d[t]=0;h=[[0,t]];q=[9**9]*(n-1)
for _ in range(m):
  u,v,a,b=map(int,input().split())
  for i in range(a,2501):e[z(u-1,i)].append((z(v-1,i-a),b));e[z(v-1,i)].append((z(u-1,i-a),b))
for i in range(n):
  c,r=map(int,input().split())
  for j in range(c,2501):e[z(i,j-c)].append((z(i,j),r))
while h:
  c,v=heappop(h)
  if d[v]<c:continue
  for u,t in e[v]:
    if c+t<d[u]:d[u]=c+t;heappush(h,[c+t,u])
for i in range(n-1):
  for j in range(2501):q[i]=min(q[i],d[z(i+1,j)])
print(*q)

Submission status: Wrong Answer

Solution code:
import heapq

#dg = 10**7#ノード数より多く取る

n,m, S = map(int,input().split()) #n:頂点数　m:辺の数

edge = [[] for i in range(n)]
#edge[i] : iから出る道の[重み,行先]の配列


Cs=[]
Ds=[]
amax=0
for _ in range(m):
    u, v, a, b = map(int,input().split())
    edge[u-1].append([v-1,a,b])
    edge[v-1].append([u-1,a,b])#有向グラフの場合コメント
    amax=max(a,amax)

for _ in range(n):
    c, d = map(int,input().split())
    Cs.append(c)
    Ds.append(d)

dg=(n-1)*amax

def cut(S): 
    if S>dg:
        return dg
    else: return S

S=cut(S)

def dijkstra(start):

    #dijkstra
    # d : minimum distance from s
    d = [[10**20]*(dg+1) for _ in range(n)]
    d[start][cut(S)] = 0
    edgelist = []

    heapq.heappush(edgelist,(Ds[0], 0, cut(S+Cs[0])))

    for e in edge[start]:
        if S-e[1]>=0:
            heapq.heappush(edgelist,(e[2],e[0],S-e[1]))

    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        t,ce,cs = minedge[0],minedge[1],minedge[2]
        #print(t,ce,cs)
        if  d[ce][cs]== 10**20:
            d[ce][cs] = t
            ns=cut(cs+Cs[ce])
            print(ce,ns)
            if d[ce][ns]==10**20:
                #d[ce][ns]=t+Ds[ce]
                heapq.heappush(edgelist, (t+Ds[ce],ce,ns))

            for e in edge[ce]:
                if cs>=e[1]:
                    #print(e)
                    ne=e[0]
                    ns=cs-e[1]
                    if d[ne][ns]==10**20:
                        #print(ne)
                        heapq.heappush(edgelist, (t+e[2],ne,ns))
    return d

d=dijkstra(start=0)
for x in d[1:]:
    print(min(x))
#print(d)

Submission status: Wrong Answer

Solution code:
from scipy.sparse import coo_matrix
from scipy.sparse.csgraph import dijkstra


def add_modified_edge(from_, to, time):
    modified_edges_from.append(from_)
    modified_edges_to.append(to)
    modified_edge_time.append(time)


def add_coin_charge_edge(city, bank, s):
    city_0_coin = city * 2500
    city_maxim_coin = city_0_coin + 2499

    coin, time = bank
    from_ = city_0_coin
    if city == 0:
        from_ = s
    while from_ < city_maxim_coin:
        to = min(from_ + coin, city_maxim_coin)
        add_modified_edge(from_, to, time)
        from_ = to


def expand_edge(from_, to, cost, time):
    with_0_coin_from = from_ * 2500
    with_maxim_coin_from = with_0_coin_from + 2499
    with_0_coin_to = to * 2500
    with_maxim_coin_to = with_0_coin_to + 2499

    for with_coin_from in range(with_maxim_coin_from, with_0_coin_from+cost-1, -1):
        coin = with_coin_from % 2500 - cost
        with_coin_to = with_0_coin_to + coin
        add_modified_edge(with_coin_from, with_coin_to, time)

    for with_coin_to in range(with_maxim_coin_to, with_0_coin_to+cost-1, -1):
        coin = with_coin_to % 2500 - cost
        with_coin_from = with_0_coin_from + coin
        add_modified_edge(with_coin_to, with_coin_from, time)


n, m, s = map(int, input().split())
if s > 2500:
    s = 2499
edges = []
for _ in range(m):
    from_, to, cost, time = map(int, input().split())
    edges.append([from_-1, to-1, cost, time])

banks = []
for _ in range(n):
    coin, time = map(int, input().split())
    banks.append([coin, time])

modified_edges_from = [0]
modified_edges_to = [s]
modified_edge_time = [0]

for city, bank in enumerate(banks):
    add_coin_charge_edge(city, bank, s)

for natural_from, natural_to, cost, time in edges:
    expand_edge(natural_from, natural_to, cost, time)

csr = coo_matrix((modified_edge_time, (modified_edges_from, modified_edges_to)), (n*2500, n*2500)).tocsr()
results = dijkstra(csr, indices=0)
second_city = 2500
last_city = 2500 * (n-1)
for to_city in range(second_city, last_city+1, 2500):
    print(int(min(results[to_city:to_city+2500])))