Problem:


Score : 400 points

Problem Statement

Kenkoooo is planning a trip in Republic of Snuke.
In this country, there are n cities and m trains running.
The cities are numbered 1 through n, and the i-th train connects City u_i and v_i bidirectionally.
Any city can be reached from any city by changing trains.

Two currencies are used in the country: yen and snuuk.
Any train fare can be paid by both yen and snuuk.
The fare of the i-th train is a_i yen if paid in yen, and b_i snuuk if paid in snuuk.

In a city with a money exchange office, you can change 1 yen into 1 snuuk.
However, when you do a money exchange, you have to change all your yen into snuuk.
That is, if Kenkoooo does a money exchange when he has X yen, he will then have X snuuk.
Currently, there is a money exchange office in every city, but the office in City i will shut down in i years and can never be used in and after that year.

Kenkoooo is planning to depart City s with 10^{15} yen in his pocket and head for City t, and change his yen into snuuk in some city while traveling.
It is acceptable to do the exchange in City s or City t.

Kenkoooo would like to have as much snuuk as possible when he reaches City t by making the optimal choices for the route to travel and the city to do the exchange.
For each i=0,...,n-1, find the maximum amount of snuuk that Kenkoooo has when he reaches City t if he goes on a trip from City s to City t after i years.
You can assume that the trip finishes within the year.

Constraints

2 \leq n \leq 10^5

1 \leq m \leq 10^5

1 \leq s,t \leq n

s \neq t

1 \leq u_i < v_i \leq n

1 \leq a_i,b_i \leq 10^9

If i\neq j, then u_i \neq u_j  or v_i \neq v_j.

Any city can be reached from any city by changing trains.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

n m s t
u_1 v_1 a_1 b_1
:
u_m v_m a_m b_m

Output

Print n lines.
In the i-th line, print the maximum amount of snuuk that Kenkoooo has when he reaches City t if he goes on a trip from City s to City t after i-1 years.

Sample Input 1

4 3 2 3
1 4 1 100
1 2 1 10
1 3 20 1

Sample Output 1

999999999999998
999999999999989
999999999999979
999999999999897

After 0 years, it is optimal to do the exchange in City 1.

After 1 years, it is optimal to do the exchange in City 2.

Note that City 1 can still be visited even after the exchange office is closed.
Also note that, if it was allowed to keep 1 yen when do the exchange in City 2 and change the remaining yen into snuuk, we could reach City 3 with 999999999999998 snuuk, but this is NOT allowed.

After 2 years, it is optimal to do the exchange in City 3.

After 3 years, it is optimal to do the exchange in City 4.
Note that the same train can be used multiple times.

Sample Input 2

8 12 3 8
2 8 685087149 857180777
6 7 298270585 209942236
2 4 346080035 234079976
2 5 131857300 22507157
4 8 30723332 173476334
2 6 480845267 448565596
1 4 181424400 548830121
4 5 57429995 195056405
7 8 160277628 479932440
1 6 475692952 203530153
3 5 336869679 160714712
2 7 389775999 199123879

Sample Output 2

999999574976994
999999574976994
999999574976994
999999574976994
999999574976994
999999574976994
999999574976994
999999574976994



Sample input:
4 3 2 3
1 4 1 100
1 2 1 10
1 3 20 1


Sample output:
999999999999998
999999999999989
999999999999979
999999999999897

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import heapq

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


def dijkstra(s,cu):
    inf = 10**18
    d = [inf]*n
    d[s] = 0
    q = [s]
    heapq.heapify(q)

    while len(q)>0:
        v = heapq.heappop(q)
        for u,ud in e[v]:
            if d[u]>d[v]+ud[cu]:
                d[u] = d[v] + ud[cu]
                heapq.heappush(q, u)
    return d


da = dijkstra(s,0)
db = dijkstra(t,1)
res = [0]*n
res[n-1] = da[n-1]+db[n-1]
for i in range(n-2,-1,-1):
    res[i] = min(res[i+1], da[i]+db[i])

x = 10**15
for i in range(n):
    print(x - res[i])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import heapq

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


def dijkstra(s,cu):
    inf = 10**15
    d = [inf]*n
    d[s] = 0
    q = [s]
    heapq.heapify(q)

    while len(q)>0:
        v = heapq.heappop(q)
        for u,ud in e[v]:
            if d[u]>d[v]+ud[cu]:
                d[u] = d[v] + ud[cu]
                heapq.heappush(q, u)
    return d


da = dijkstra(s,0)
db = dijkstra(t,1)
res = [0]*n
m = 10**15
res[n-1] = da[n-1]+db[n-1]
for i in range(n-2,-1,-1):
    res[i] = min(res[i+1], da[i]+db[i])

x = 10**15
for i in range(n):
    print(x - res[i])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import heapq

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


def dijkstra(s,cu):
    inf = 10**15
    d = [inf]*n
    d[s] = 0
    q = [(s,0)]
    heapq.heapify(q)

    while len(q)>0:
        v,c = heapq.heappop(q)
        if d[v]<c:
            continue
        for u,ud in e[v]:
            if d[u]>c+ud[cu]:
                d[u] = c + ud[cu]
                heapq.heappush(q, (u, d[u]))
    return d


da = dijkstra(s,0)
db = dijkstra(t,1)
res = [0]*n
m = 10**15
res[n-1] = da[n-1]+db[n-1]
for i in range(n-2,-1,-1):
    res[i] = min(res[i+1], da[i]+db[i])

x = 10**15
for i in range(n):
    print(x - res[i])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import heapq

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


def dijkstra(s,cu):
    inf = 10**15
    d = [inf]*n
    d[s] = 0
    q = [(s,0)]
    heapq.heapify(q)

    while len(q)>0:
        v,c = heapq.heappop(q)
        if d[v]<c:
            continue
        for u,ud in e[v]:
            if d[u]>c+ud[cu]:
                d[u] = c + ud[cu]
                heapq.heappush(q, (u, d[u]))
    return d


da = dijkstra(s,0)
db = dijkstra(t,1)
res = [0]*n
m = 10**15
for i in range(n-1,-1,-1):
    r = da[i]+db[i]
    m = min(m,r)

    res[i] = m

x = 10**15
for i in range(n):
    print(x - res[i])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import heapq

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


def dijkstra(e,n,s,cu):
    inf = 10**15
    d = [inf]*n
    d[s] = 0
    q = [(s,0)]
    heapq.heapify(q)

    while len(q)>0:
        v,c = heapq.heappop(q)
        if d[v]<c:
            continue
        for u,ud in e[v]:
            if d[u]>c+ud[cu]:
                d[u] = c + ud[cu]
                heapq.heappush(q, (u, d[u]))
    return d


da = dijkstra(e,n,s,0)
db = dijkstra(e,n,t,1)
res = [0]*n
m = 10**15
for i in range(n-1,-1,-1):
    r = da[i]+db[i]
    m = min(m,r)

    res[i] = m

x = 10**15
for i in range(n):
    print(x - res[i])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import heapq

n,m,s,t = map(int, input().split())
s -= 1
t -= 1
ea = [[] for _ in range(n)]
eb = [[] for _ in range(n)]
for _ in range(m):
    v,u,a,b = map(int, input().split())
    v -= 1
    u -= 1
    ea[v].append((u,a))
    ea[u].append((v,a))
    eb[v].append((u,b))
    eb[u].append((v,b))


def dijkstra(e,n,s):
    inf = 10**15
    d = [inf]*n
    d[s] = 0
    q = [(s,0)]
    heapq.heapify(q)

    while len(q)>0:
        v,c = heapq.heappop(q)
        if d[v]<c:
            continue
        for u,ud in e[v]:
            if d[u]>c+ud:
                d[u] = c + ud
                heapq.heappush(q, (u, d[u]))
    return d


da = dijkstra(ea,n,s)
db = dijkstra(eb,n,t)
res = [0]*n
m = 10**15
for i in range(n-1,-1,-1):
    r = da[i]+db[i]
    m = min(m,r)

    res[i] = m

x = 10**15
for i in range(n):
    print(x - res[i])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import heapq

n,m,s,t = map(int, input().split())
s -= 1
t -= 1
ea = [[] for _ in range(n)]
eb = [[] for _ in range(n)]
for _ in range(m):
    v,u,a,b = map(int, input().split())
    v -= 1
    u -= 1
    ea[v].append((u,a))
    ea[u].append((v,a))
    eb[v].append((u,b))
    eb[u].append((v,b))


def dijkstra(e,n,s):
    inf = 10**15
    d = [inf]*n
    d[s] = 0
    q = [(s,0)]
    heapq.heapify(q)

    while len(q)>0:
        v,c = heapq.heappop(q)
        if d[v]<c:
            continue
        for u,ud in e[v]:
            if d[u]>c+ud:
                d[u] = c + ud
                heapq.heappush(q, (u, d[u]))
    return d


da = dijkstra(ea,n,s)
db = dijkstra(eb,n,t)
res = [0]*n
m = None
for i in range(n-1,-1,-1):
    r = da[i]+db[i]
    if m is None:
        m = r
    else:
        m = min(m,r)

    res[i] = m

for i in range(n):
    print(10**15 - res[i])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import heapq

n,m,s,t = map(int, input().split())
s -= 1
t -= 1
ea = [[] for _ in range(n)]
eb = [[] for _ in range(n)]
for _ in range(m):
    v,u,a,b = map(int, input().split())
    v -= 1
    u -= 1
    ea[v].append((u,a))
    ea[u].append((v,a))
    eb[v].append((u,b))
    eb[u].append((v,b))


def dijkstra(e,n,s):
    d = [None]*n
    d[s] = 0
    q = [(s,0)]
    heapq.heapify(q)

    while len(q)>0:
        v,c = heapq.heappop(q)
        if d[v] is not None and d[v]<c:
            continue
        for u,ud in e[v]:
            if d[u] is None or d[u]>c+ud:
                d[u] = c + ud
                heapq.heappush(q, (u, d[u]))
    return d


da = dijkstra(ea,n,s)
db = dijkstra(eb,n,t)
res = [0]*n
m = None
for i in range(n-1,-1,-1):
    r = da[i]+db[i]
    if m is None:
        m = r
    else:
        m = min(m,r)

    res[i] = m

for i in range(n):
    print(10**15 - res[i])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import heapq

n,m,s,t = map(int, input().split())
s -= 1
t -= 1
ea = [[] for _ in range(n)]
eb = [[] for _ in range(n)]
for _ in range(m):
    v,u,a,b = map(int, input().split())
    v -= 1
    u -= 1
    ea[v].append((u,a))
    ea[u].append((v,a))
    eb[v].append((u,b))
    eb[u].append((v,b))


def dijkstra(e,n,s):
    d = [None]*n
    d[s] = 0
    q = [(s,0)]
    heapq.heapify(q)

    while len(q)>0:
        v,c = heapq.heappop(q)
        if d[v] is not None and d[v]<c:
            continue
        for u,ud in e[v]:
            if d[u] is None or d[u]>c+ud:
                d[u] = c + ud
                heapq.heappush(q, (u, d[u]))
    return d


da = dijkstra(ea,n,s)
db = dijkstra(eb,n,t)
res = []
m = None
for i in range(n-1,-1,-1):
    r = da[i]+db[i]
    if m is None:
        m = r
    else:
        m = min(m,r)

    res.append(m)

for i in range(n-1,-1,-1):
    print(10**15 - res[i])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import heapq

n,m,s,t = map(int, input().split())
s -= 1
t -= 1
ea = [set() for _ in range(n)]
eb = [set() for _ in range(n)]
for _ in range(m):
    v,u,a,b = map(int, input().split())
    v -= 1
    u -= 1
    ea[v].add((u,a))
    ea[u].add((v,a))
    eb[v].add((u,b))
    eb[u].add((v,b))


def dijkstra(e,n,s):
    d = [None]*n
    d[s] = 0
    q = [(s,0)]
    heapq.heapify(q)

    while len(q)>0:
        v,c = heapq.heappop(q)
        if d[v] is not None and d[v]<c:
            continue
        for u,ud in e[v]:
            if d[u] is None or d[u]>c+ud:
                d[u] = c + ud
                heapq.heappush(q, (u, d[u]))
    return d


da = dijkstra(ea,n,s)
db = dijkstra(eb,n,t)
res = []
m = None
for i in range(n-1,-1,-1):
    r = da[i]+db[i]
    if m is None:
        m = r
    else:
        m = min(m,r)

    res.append(m)

for i in range(n-1,-1,-1):
    print(10**15 - res[i])

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix, lil_matrix
import sys
input = sys.stdin.readline
n,m,s,t = map(int, input().split())
money = lil_matrix((n+1, n+1), dtype = int)
snu = lil_matrix((n+1, n+1), dtype = int)
for i in range(m):
    u,v,a,b = map(int, input().split())
    money[u,v] = money[v,u] = a
    snu[u,v] = snu[v,u] = b
money = dijkstra(money, indices=s,directed=False)
snu = dijkstra(snu, indices=t,directed=False)
start = 10**15
#何年目か？
ans = []
ans_max = 10**15
for j in range(n,-1,-1):
    ans_max = min(ans_max, (money[j] + snu[j]))
    ans.append(ans_max)
for i in range(n-1,-1,-1):
    print(int(start - ans[i]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix, lil_matrix
import sys
input = sys.stdin.readline
n,m,s,t = map(int, input().split())
money = lil_matrix((n+1, n+1), dtype = int)
snu = lil_matrix((n+1, n+1), dtype = int)
for i in range(m):
    u,v,a,b = map(int, input().split())
    money[u,v] = money[v,u] = a
    snu[u,v] = snu[v,u] = b
money = dijkstra(money)
snu = dijkstra(snu)
start = 10**15
#何年目か？
ans = []
ans_max = 10**15
for j in range(n,-1,-1):
    ans_max = min(ans_max, (money[s][j] + snu[j][t]))
    ans.append(ans_max)
for i in range(n-1,-1,-1):
    print(int(start - ans[i]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix, lil_matrix
import sys
input = sys.stdin.readline
n,m,s,t = map(int, input().split())
money = lil_matrix((n+1, n+1), dtype = int)
snu = lil_matrix((n+1, n+1), dtype = int)
for i in range(m):
    u,v,a,b = map(int, input().split())
    money[u,v] = money[v,u] = a
    snu[u,v] = snu[v,u] = b
money = dijkstra(money)
snu = dijkstra(snu)
start = 10**15
#何年目か？
for i in range(n):
    ans = 0
    #i年目なので、iまででは両替出来ない。両替する場所を探す
    for j in range(i+1,n+1):
        ans = max(ans, start - (money[s][j] + snu[j][t]))
    print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import heapq

n,m,s,t = map(int, input().split())
s -= 1
t -= 1
ea = [set() for _ in range(n)]
eb = [set() for _ in range(n)]
for _ in range(m):
    v,u,a,b = map(int, input().split())
    v -= 1
    u -= 1
    ea[v].add((u,a))
    ea[u].add((v,a))
    eb[v].add((u,b))
    eb[u].add((v,b))


def dijkstra(e,n,s):
    d = [None]*n
    d[s] = 0
    q = [(s,0)]
    heapq.heapify(q)

    while len(q)>0:
        v,c = heapq.heappop(q)
        if d[v] is not None and d[v]<c:
            continue
        for u,ud in e[v]:
            if d[u] is None or d[u]>c+ud:
                d[u] = c + ud
                heapq.heappush(q, (u, d[u]))
    return d


da = dijkstra(ea,n,s)
db = dijkstra(eb,n,t)
res = []
m = None
for i in range(n-1,-1,-1):
    r = da[i]+db[i]
    if m is None:
        m = r
    else:
        m = min(m,r)

    res.append(m)

res.reverse()
for r in res:
    print(10**15 - r)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import heapq
    import sys
    import numpy as np
    from scipy.sparse import csr_matrix
    from scipy.sparse.csgraph import dijkstra

    input = sys.stdin.readline

    MAX  = 10 ** 15

    N, M, s, t = map(int, input().split())

    edge = np.array([input().split() for _ in range(M)], dtype = np.int64).T
    g1 = csr_matrix((edge[2], (edge[:2] - 1)), (N, N))
    g2 = csr_matrix((edge[3], (edge[:2] - 1)), (N, N))

    d1 = dijkstra(g1, directed = False, indices = s - 1)
    d2 = dijkstra(g2, directed = False, indices = t - 1)

    d = d1 + d2

    # print (d1)
    # print (d2)

    # print (g1)
    # print (g2)

    # print (edge)

    tmp = MAX
    ans = [MAX] * N
    for i in range(N - 1, -1, -1):
        tmp = min(tmp, d[i])
        ans[i] -= int(tmp)

    print (*ans, sep = '\n')

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import heapq
    import sys
    import numpy as np
    from scipy.sparse import csr_matrix
    from scipy.sparse.csgraph import dijkstra

    input = sys.stdin.readline

    MAX  = 10 ** 15

    N, M, s, t = map(int, input().split())

    edge = np.array([input().split() for _ in range(M)], dtype = np.int64).T
    g1 = csr_matrix((edge[2], (edge[:2] - 1)), (N, N))
    g2 = csr_matrix((edge[3], (edge[:2] - 1)), (N, N))

    d1 = dijkstra(g1, directed = False, indices = s - 1)
    d2 = dijkstra(g2, directed = False, indices = t - 1)

    # print (d1)
    # print (d2)

    # print (g1)
    # print (g2)

    # print (edge)

    tmp = MAX
    ans = [MAX] * N
    for i in range(N - 1, -1, -1):
        tmp = min(tmp, d1[i] + d2[i])
        ans[i] -= int(tmp)

    print (*ans, sep = '\n')

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import heapq
import sys
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

input = sys.stdin.readline

MAX  = 10 ** 15

N, M, s, t = map(int, input().split())

edge = np.array([input().split() for _ in range(M)], dtype = np.int64).T
g1 = csr_matrix((edge[2], (edge[:2] - 1)), (N, N))
g2 = csr_matrix((edge[3], (edge[:2] - 1)), (N, N))

d1 = dijkstra(g1, directed = False, indices = s - 1)
d2 = dijkstra(g2, directed = False, indices = t - 1)

# print (d1)
# print (d2)

# print (g1)
# print (g2)

# print (edge)

tmp = MAX
ans = [MAX] * N
for i in range(N - 1, -1, -1):
    tmp = min(tmp, d1[i] + d2[i])
    ans[i] -= int(tmp)

print (*ans, sep = '\n')

Submission status: Time Limit Exceeded

Solution code:
import heapq
import sys
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra



MAX  = 10 ** 15

N, M, s, t = map(int, input().split())

edge = np.array([input().split() for _ in range(M)], dtype = np.int64).T
g1 = csr_matrix((edge[2], (edge[:2] - 1)), (N, N))
g2 = csr_matrix((edge[3], (edge[:2] - 1)), (N, N))

d1 = dijkstra(g1, directed = False, indices = s - 1)
d2 = dijkstra(g2, directed = False, indices = t - 1)

# print (d1)
# print (d2)

# print (g1)
# print (g2)

# print (edge)

tmp = MAX
ans = [MAX] * N
for i in range(N - 1, -1, -1):
    tmp = min(tmp, d1[i] + d2[i])
    ans[i] -= int(tmp)

print (*ans, sep = '\n')

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
from collections import deque
import numpy as np

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)


N, M, S, T = map(int, input().split())
PATH = [[] for _ in range(N+1)]


for _ in range(M):
    u, v, a, b = map(int, input().split())
    PATH[u].append((v, a, b))
    PATH[v].append((u, a, b))

INF = 10 ** 15

da = [INF] * (N+1)
db = [INF] * (N+1)

usedA = [False] * (N+1)
usedB = [False] * (N+1)

da[S] = 0
for _ in range(N+2):
    d = -1
    v = -1
    for i in range(1, N+1):
        if not usedA[i]:
            if d == -1 or da[i] < d:
                v = i
                d = da[i]

    if d == -1:
        break

    usedA[v] = True

    for u, a, _ in PATH[v]:
        da[u] = min(da[u], da[v]+a)

db[T] = 0
for _ in range(N+2):
    d = -1
    v = -1
    for i in range(1, N+1):
        if not usedB[i]:
            if d == -1 or db[i] < d:
                v = i
                d = db[i]

    if d == -1:
        break

    usedB[v] = True

    for u, _, b in PATH[v]:
        db[u] = min(db[u], db[v]+b)

dist = [(i, da[i]+db[i]) for i in range(1, N+1)]
dist.sort(key=lambda x: x[1])
idx = 0

for i in range(N):
    while(dist[idx][0] <= i):
        idx += 1

    print(10**15 - dist[idx][1])

Submission status: Time Limit Exceeded

Solution code:
def main():
    from sys import stdin
    input = stdin.readline

    n, m, s, t = map(int, input().split())
    uvab = [list(map(int, input().split())) for _ in [0]*m]
    g_yen = [[] for _ in [0]*n]
    [g_yen[u-1].append([v-1, a]) for u, v, a, b in uvab]
    [g_yen[v-1].append([u-1, a]) for u, v, a, b in uvab]

    g_snk = [[] for _ in [0]*n]
    [g_snk[u-1].append([v-1, b]) for u, v, a, b in uvab]
    [g_snk[v-1].append([u-1, b]) for u, v, a, b in uvab]

    import heapq

    inf = 10**15

    yen = [inf for _ in [0]*n]
    h = [(0, s-1)]
    heapq.heapify(h)
    while h:
        d, i = heapq.heappop(h)
        if yen[i] == inf:
            yen[i] = d
            for x, y in g_yen[i]:
                heapq.heappush(h, (d+y, x))

    snk = [inf for _ in [0]*n]
    h = [(0, t-1)]
    heapq.heapify(h)
    while h:
        d, i = heapq.heappop(h)
        if snk[i] == inf:
            snk[i] = d
            for x, y in g_snk[i]:
                heapq.heappush(h, (d+y, x))

    cost = [yen[i]+snk[i] for i in range(n)]
    m = cost[-1]
    for i in range(n-1, -1, -1):
        m = min(m, cost[i])
        cost[i] = m

    for i in cost:
        print(10**15-i)


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    #from sys import stdin
    #input = stdin.readline

    n, m, s, t = map(int, input().split())
    uvab = [list(map(int, input().split())) for _ in [0]*m]
    g_yen = [[] for _ in [0]*n]
    [g_yen[u-1].append([v-1, a]) for u, v, a, b in uvab]
    [g_yen[v-1].append([u-1, a]) for u, v, a, b in uvab]

    g_snk = [[] for _ in [0]*n]
    [g_snk[u-1].append([v-1, b]) for u, v, a, b in uvab]
    [g_snk[v-1].append([u-1, b]) for u, v, a, b in uvab]

    import heapq

    inf = 10**15

    yen = [inf for _ in [0]*n]
    h = [(0, s-1)]
    heapq.heapify(h)
    while h:
        d, i = heapq.heappop(h)
        if yen[i] == inf:
            yen[i] = d
            for x, y in g_yen[i]:
                heapq.heappush(h, (d+y, x))

    snk = [inf for _ in [0]*n]
    h = [(0, t-1)]
    heapq.heapify(h)
    while h:
        d, i = heapq.heappop(h)
        if snk[i] == inf:
            snk[i] = d
            for x, y in g_snk[i]:
                heapq.heappush(h, (d+y, x))

    cost = [yen[i]+snk[i] for i in range(n)]
    m = cost[-1]
    for i in range(n-1, -1, -1):
        m = min(m, cost[i])
        cost[i] = m

    for i in cost:
        print(10**15-i)


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from sys import stdin
    input = stdin.readline
    import numpy as np
    import scipy.sparse as sp

    n, m, s, t = map(int, input().split())
    uvab = np.array([list(map(int, input().split())) for _ in [0]*m])

    data = np.append(uvab[:, 2], uvab[:, 2])
    row = np.append(uvab[:, 0], uvab[:, 1]) - 1
    col = np.append(uvab[:, 1], uvab[:, 0]) - 1

    matrix = sp.csr_matrix(
        (data, (row, col)), shape=(n, n), dtype=np.int32)
    yen = sp.csgraph.dijkstra(matrix, indices=s-1)

    data = np.append(uvab[:, 3], uvab[:, 3])
    matrix = sp.csr_matrix(
        (data, (row, col)), shape=(n, n), dtype=np.int32)
    snk = sp.csgraph.dijkstra(matrix, indices=t-1)

    cost = yen+snk
    m = cost[-1]
    for i in range(n-1, -1, -1):
        m = min(cost[i], m)
        cost[i] = m

    cost = 10**15-cost

    for i in cost:
        print(int(i))


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from sys import stdin
    input = stdin.readline
    import numpy as np
    import scipy.sparse as sp

    n, m, s, t = map(int, input().split())
    uvab = np.array([list(map(int, input().split())) for _ in [0]*m])

    data = np.append(uvab[:, 2], uvab[:, 2])
    row = np.append(uvab[:, 0], uvab[:, 1]) - 1
    col = np.append(uvab[:, 1], uvab[:, 0]) - 1

    matrix = sp.csr_matrix(
        (data, (row, col)), shape=(n, n), dtype=np.int64)
    yen = sp.csgraph.dijkstra(matrix, indices=s-1)

    data = np.append(uvab[:, 3], uvab[:, 3])
    matrix = sp.csr_matrix(
        (data, (row, col)), shape=(n, n), dtype=np.int64)
    snk = sp.csgraph.dijkstra(matrix, indices=t-1)

    cost = yen+snk
    m = cost[-1]
    for i in range(n-1, -1, -1):
        m = min(cost[i], m)
        cost[i] = m

    cost = 10**15-cost

    for i in cost:
        print(int(i))


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from sys import stdin
    input = stdin.readline
    import numpy as np
    import scipy.sparse as sp

    n, m, s, t = map(int, input().split())
    uvab = np.array([list(map(int, input().split())) for _ in [0]*m])

    data = uvab[:, 2]
    row = uvab[:, 0] - 1
    col = uvab[:, 1] - 1

    matrix = sp.csr_matrix(
        (data, (row, col)), shape=(n, n), dtype=np.int64)
    yen = sp.csgraph.dijkstra(matrix, indices=s-1, directed=False)

    data = uvab[:, 3]
    matrix = sp.csr_matrix(
        (data, (row, col)), shape=(n, n), dtype=np.int64)
    snk = sp.csgraph.dijkstra(matrix, indices=t-1, directed=False)

    cost = yen+snk
    m = cost[-1]
    for i in range(n-1, -1, -1):
        m = min(cost[i], m)
        cost[i] = m

    cost = 10**15-cost

    for i in cost:
        print(int(i))


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from sys import stdin
    input = stdin.readline

    n, m, s, t = map(int, input().split())
    uvab = [list(map(int, input().split())) for _ in [0]*m]

    import numpy as np
    import scipy.sparse as sp
    data = [a for u, v, a, b in uvab]
    row = [u-1 for u, v, a, b in uvab]
    col = [v-1 for u, v, a, b in uvab]
    matrix = sp.csr_matrix(
        (data, (row, col)), shape=(n, n), dtype=np.int64)
    yen = sp.csgraph.dijkstra(matrix, indices=s-1, directed=False)

    data = [b for u, v, a, b in uvab]
    matrix = sp.csr_matrix(
        (data, (row, col)), shape=(n, n), dtype=np.int64)
    snk = sp.csgraph.dijkstra(matrix, indices=t-1, directed=False)

    cost = yen+snk
    m = cost[-1]
    for i in range(n-1, -1, -1):
        cost[i] = np.min(cost[i:i+2])

    cost = 10**15-cost

    for i in cost:
        print(int(i))


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from sys import stdin
    input = stdin.readline

    n, m, s, t = map(int, input().split())
    uvab = [list(map(int, input().split())) for _ in [0]*m]

    import numpy as np
    import scipy.sparse as sp
    data = [a for u, v, a, b in uvab]
    row = [u-1 for u, v, a, b in uvab]
    col = [v-1 for u, v, a, b in uvab]
    matrix = sp.csr_matrix(
        (data, (row, col)), shape=(n, n), dtype=np.int64)
    yen = sp.csgraph.dijkstra(matrix, indices=s-1, directed=False)

    data = [b for u, v, a, b in uvab]
    matrix = sp.csr_matrix(
        (data, (row, col)), shape=(n, n), dtype=np.int64)
    snk = sp.csgraph.dijkstra(matrix, indices=t-1, directed=False)

    cost = yen+snk
    m = cost[-1]
    for i in range(n-1, -1, -1):
        m = min(m, cost[i])
        cost[i] = m

    cost = 10**15-cost

    for i in cost:
        print(int(i))

main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from sys import stdin
    input = stdin.readline

    n, m, s, t = map(int, input().split())
    uvab = [list(map(int, input().split())) for _ in [0]*m]
    g_yen = [[] for _ in [0]*n]
    [g_yen[u-1].append([v-1, a]) for u, v, a, b in uvab]
    [g_yen[v-1].append([u-1, a]) for u, v, a, b in uvab]

    g_snk = [[] for _ in [0]*n]
    [g_snk[u-1].append([v-1, b]) for u, v, a, b in uvab]
    [g_snk[v-1].append([u-1, b]) for u, v, a, b in uvab]

    import heapq

    def dijkstra(g, start):
        inf = 10**15
        dist = [inf for _ in [0]*n]
        h = [(0, start)]
        heapq.heapify(h)
        while h:
            d, i = heapq.heappop(h)
            if dist[i] == inf:
                dist[i] = d
                for x, y in g[i]:
                    heapq.heappush(h, (d+y, x))
        return dist

    yen = dijkstra(g_yen, s-1)
    snk = dijkstra(g_snk, t-1)

    cost = [yen[i]+snk[i] for i in range(n)]
    m = cost[-1]
    for i in range(n-1, -1, -1):
        m = min(m, cost[i])
        cost[i] = m

    for i in cost:
        print(10**15-i)


main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

N, M, s, t = map(int, input().split())
s, t = s - 1, t - 1

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

yen, snuke = np.asarray(yen), np.asarray(snuke)
yen_g = csr_matrix((yen[:, 2], (yen[:, 0], yen[:, 1])), shape=(N, N), dtype=np.int64)
snuke_g = csr_matrix((snuke[:, 2], (snuke[:, 0], snuke[:, 1])), shape=(N, N), dtype=np.int64)

yen_d = dijkstra(yen_g, indices=s)
snuke_d = dijkstra(snuke_g, indices=t)

pque = []
ans = []
min_cost = 10 ** 15
for i in range(N):
    min_cost = min(min_cost, int(yen_d[N-i-1] + snuke_d[N-i-1]))
    ans.append(10 ** 15 - min_cost)
for a in ans[::-1]:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra
import heapq

N, M, s, t = map(int, input().split())
s, t = s - 1, t - 1

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

yen, snuke = np.asarray(yen), np.asarray(snuke)
yen_g = csr_matrix((yen[:, 2], (yen[:, 0], yen[:, 1])) , shape=(N, N), dtype=np.int64)
snuke_g = csr_matrix((snuke[:, 2], (snuke[:, 0], snuke[:, 1])) , shape=(N, N), dtype=np.int64)

yen_d = dijkstra(yen_g, indices=s)
snuke_d = dijkstra(snuke_g, indices=t)

pque = []
ans = []

for i in range(N):
    heapq.heappush(pque, int(yen_d[N-i-1] + snuke_d[N-i-1]))
    ans.append(10 ** 15 - pque[0])
for a in ans[::-1]:
    print(a)

Submission status: Time Limit Exceeded

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

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

yen_edge = [[] for _ in range(n)]
snuke_edge = [[] for _ in range(n)]

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

class DijkstraList():
    #隣接リスト版
    def __init__(self, adj, start):
        self.list = adj
        self.start = start
        self.size = len(adj)

    def solve(self):
        self.dist = [float("inf") for _ in range(self.size)]
        self.dist[self.start] = 0
        self.q = []

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

        while self.q:
            u = heapq.heappop(self.q)
            u_dist = self.dist[u]
            for v, w in self.list[u]:
                if self.dist[v] > u_dist + w:
                    self.dist[v] = u_dist + w
                    heapq.heappush(self.q, v)

        return

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

yen = DijkstraList(yen_edge, s - 1)
snuke = DijkstraList(snuke_edge, t - 1)
yen.solve()
snuke.solve()
ans_list = []

for i in range(n):
	ans_list.append(yen.distance(i) + snuke.distance(i))

ans = []

ans.append(10 ** 15 - ans_list[n - 1])

for i in range(1, n):
	if ans_list[n - i - 1] > ans_list[n - i]:
		ans_list[n - i - 1] = ans_list[n - i]
	ans.append(10 ** 15 - ans_list[n - i - 1])

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