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:
import sys
input = sys.stdin.readline
from collections import defaultdict, deque
from itertools import accumulate
n,m,s,t= map(int,input().split())
uvab = [list(map(int,input().split())) for i in range(m)]

g = defaultdict(list)
c = {}
for i in range(1,n+1):
    g[i].append(n+i)
    c[(i,n+i)] = 0
for u,v,a,b in uvab:
    g[u].append(v)
    g[v].append(u)
    g[n+u].append(n+v)
    g[n+v].append(n+u)
    c[(u,v)] = a
    c[(v,u)] = a
    c[(n+u,n+v)] = b
    c[(n+v,n+u)] = b

inf = 10**15
ds2t = [inf for i in range(2*n+1)]
ds2t[s] = 0

dq = deque([s])
while dq:
    v = dq.popleft()
    for nv in g[v]:
        if ds2t[nv] > ds2t[v] + c[(v,nv)]:
            ds2t[nv] = ds2t[v] + c[(v,nv)]
            dq.append(nv)


dt2s = [inf for i in range(2*n+1)]
dt2s[n+t] = 0

dq = deque([n+t])
while dq:
    v = dq.popleft()
    for nv in g[v]:
        if dt2s[nv] > dt2s[v] + c[(v,nv)]:
            dt2s[nv] = dt2s[v] + c[(v,nv)]
            dq.append(nv)

ds = []
for i in range(1,n+1):
    ds.append(ds2t[i] + dt2s[n+i])

ds = accumulate(ds[::-1], min)

for d in reversed(list(ds)): 
    print(10**15-d)

Submission status: Time Limit Exceeded

Solution code:
import heapq

def dijkstra(s, edge):
    cost = [float('inf')] * n
    cost[s] = 0
    hq = [(0, s)]
    heapq.heapify(hq)
    while hq:
        c, v = heapq.heappop(hq)
        if c > cost[v]:
            continue
        for d, u in edge[v]:
            if c + d < cost[u]:
                heapq.heappush(hq, (c + d, u))
                cost[u] = c + d
    return cost

n, m, s, t = map(int, input().split())
s -= 1
t -= 1
yen = [[] for _ in range(n)]
snuuk = [[] for _ in range(n)]
for _ in range(m):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    yen[u].append((a, v))
    yen[v].append((a, u))
    snuuk[u].append((b, v))
    snuuk[v].append((b, u))
py = dijkstra(s, yen)
ps = dijkstra(t, snuuk)
idx = -1
for i in range(n):
    if idx < i:
        res, idx = min((py[j] + ps[j], j) for j in range(i, n))
    print(10 ** 15 - res)

Submission status: Time Limit Exceeded

Solution code:
import heapq

def dijkstra(s, edge):
    cost = [float('inf')] * n
    hq = [(0, s)]
    heapq.heapify(hq)
    while hq:
        c, v = heapq.heappop(hq)
        if c < cost[v]:
            cost[v] = c
        for d, u in edge[v]:
            if c + d < cost[u]:
                heapq.heappush(hq, (c + d, u))
    return cost

n, m, s, t = map(int, input().split())
s -= 1
t -= 1
yen = [[] for _ in range(n)]
snuuk = [[] for _ in range(n)]
for _ in range(m):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    yen[u].append((a, v))
    yen[v].append((a, u))
    snuuk[u].append((b, v))
    snuuk[v].append((b, u))
py = dijkstra(s, yen)
ps = dijkstra(t, snuuk)
idx = -1
for i in range(n):
    if idx < i:
        res, idx = min((py[j] + ps[j], j) for j in range(i, n))
    print(10 ** 15 - res)

Submission status: Time Limit Exceeded

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

N, M, S, T, *UVAB = map(int, open(0).read().split())
if N < 2 or M < 1:
    raise ValueError()

A, B, R, C = [], [], [], []
for u, v, a, b in zip(*[iter(UVAB)] * 4):
    A.append(a)
    B.append(b)
    R.append(u)
    C.append(v)

A = dijkstra(csr_matrix((A, (R, C)), (N + 1, N + 1)), False, S)
B = dijkstra(csr_matrix((B, (R, C)), (N + 1, N + 1)), False, T)

C = (A + B).astype(int)

init = 10 ** 15
ans = []
cur = float("inf")
for c in reversed(C[1:]):
    cur = min(cur, c)
    ans.append(init - cur)

for a in reversed(ans):
    print(a)

Submission status: Time Limit Exceeded

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

N, M, S, T, *UVAB = map(int, open(0).read().split())
A, B, R, C = [], [], [], []
for u, v, a, b in zip(*[iter(UVAB)] * 4):
    if a < 1 or b < 1:
        raise ValueError("a < 1 or b < 1")
    A.append(a)
    B.append(b)
    R.append(u)
    C.append(v)

A = dijkstra(csr_matrix((A, (R, C)), (N + 1, N + 1)), False, S)
B = dijkstra(csr_matrix((B, (R, C)), (N + 1, N + 1)), False, T)

C = (A + B).astype(int)

init = 10 ** 15
ans = []
cur = float("inf")
for c in reversed(C[1:]):
    cur = min(cur, c)
    ans.append(init - cur)

for a in reversed(ans):
    print(a)

Submission status: Time Limit Exceeded

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

N, M, S, T, *UVAB = map(int, open(0).read().split())
A, B, R, C = [], [], [], []
for u, v, a, b in zip(*[iter(UVAB)] * 4):
    A.append(a)
    B.append(b)
    R.append(u)
    C.append(v)

A = dijkstra(csr_matrix((A, (R, C)), (N + 1, N + 1)), False, S)
B = dijkstra(csr_matrix((B, (R, C)), (N + 1, N + 1)), False, T)

C = (A + B).astype(int)

init = 10 ** 15
ans = []
cur = float("inf")
for c in reversed(C[1:]):
    cur = min(cur, c)
    ans.append(init - cur)

for a in reversed(ans):
    print(a)

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
from heapq import heappush, heappop
import sys
input = sys.stdin.readline

money = 10**15
N, M, s, t = map(int, input().split())
s -= 1; t -= 1
data1 = []; row1 = []; col1 = []
data2 = []; row2 = []; col2 = []
for i in range(M):
  u, v, a, b = map(int, input().split())
  u -= 1; v -= 1
  data1 += [a]; data2 += [b]
  row1 += [u]; row2 += [u]
  col1 += [v]; col2 += [v]

graph1 = csr_matrix((data1, (row1, col1)), shape=(N, N))
graph2 = csr_matrix((data2, (row2, col2)), shape=(N, N))
dist1 = dijkstra(graph1, indices=s, directed=False).astype(int)
dist2 = dijkstra(graph2, indices=t, directed=False).astype(int)

value = [dist1[i]+dist2[i] for i in range(N)]
ans = []
cost = []
for i in range(N-1, -1, -1):
  heappush(cost, value[i])
  ans.append(money - cost[0])

print(*(ans[::-1]), sep='\n')

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
from heapq import heappush, heappop

money = 10**15
N, M, s, t = map(int, input().split())
s -= 1; t -= 1
data1 = []; row1 = []; col1 = []
data2 = []; row2 = []; col2 = []
for i in range(M):
  u, v, a, b = map(int, input().split())
  u -= 1; v -= 1
  data1 += [a]; data2 += [b]
  row1 += [u]; row2 += [u]
  col1 += [v]; col2 += [v]

graph1 = csr_matrix((data1, (row1, col1)), shape=(N, N))
graph2 = csr_matrix((data2, (row2, col2)), shape=(N, N))
dist1 = dijkstra(graph1, indices=s, directed=False).astype(int)
dist2 = dijkstra(graph2, indices=t, directed=False).astype(int)

value = [dist1[i]+dist2[i] for i in range(N)]
ans = []
cost = []
for i in range(N-1, -1, -1):
  heappush(cost, value[i])
  ans.append(money - cost[0])

print(*(ans[::-1]), sep='\n')

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop,heappush
def dijkstra(s,n,edge):
  """
  始点sから各頂点への最短距離を返す

  Parameters
  ----------
  s : int
      視点とする頂点（0-indexed）
  n : int
      グラフの要素数
  eage:list
      グラグ

  Returns
  -------
  dist ：list
  始点sから各頂点への最短距離
  """
  dist=[float("inf")]*n
  dist[s]=0
  used=[-1]*n
  hq=[[dist[s],s]]
  while hq:
    d,cur=heappop(hq)
    if dist[cur]<d:continue # 距離が最小でない場合は飛ばす
    for nx,nxd in edge[cur]:
      if dist[cur]+nxd<dist[nx]:
        dist[nx]=dist[cur]+nxd
        used[nx]=cur
        heappush(hq,[dist[cur]+nxd,nx])
  return dist

n,m,s,t=map(int,input().split())
Gs=[[] for i in range(n)]
Gt=[[] for i in range(n)]
for i in range(m):
  u,v,a,b=map(int,input().split())
  Gs[u-1].append([v-1,a])
  Gs[v-1].append([u-1,a])
  Gt[u-1].append([v-1,b])
  Gt[v-1].append([u-1,b])
s-=1
t-=1
yen=dijkstra(s,n,Gs)
snk=dijkstra(t,n,Gt)
cost=[10**15-(yen[i]+snk[i]) for i in range(n)]
for i in range(n-2,-1,-1):
  cost[i]=max(cost[i],cost[i+1])
for c in cost:
  print(c)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import heapq


class Dijkstra:
    """
    dijkstraの最短経路問題を解く
    input:
        S: start node
        mat : mat[a][b] = edge_weight(a,b)
    """

    def __init__(self, start, num_node, mat):
        """
        mat: mat[a][b] = edge_weight(a,b)
        num_node: num of nodes
        dist: dist from start_node
        prev: 最短経路において、一つ前のノードを記憶。経路復元に使う?
        """
        self.start_node = start
        self.mat = mat
        self.num_node = num_node
        self.dist = [float('inf')]*num_node
        self.prev = defaultdict(lambda: None)

        # dist form S to S = 0
        self.dist[start] = 0

    def calc_dist(self):
        """
        最短経路 distを計算する
        Q: content (dist_from_start,node)
        Qはheapqとして使う。dist_from_startの小さい順になる
        """
        Q = []
        heapq.heappush(Q, (0, self.start_node))
        while Q:
            dist_to_node, node = heapq.heappop(Q)
            # 現在の値よりも大きくて、更新にならない場合
            if self.dist[node] < dist_to_node:
                continue

            # 次のホップを計算する
            for nex in range(self.num_node):
                weight = self.mat[node][nex]
                cand = dist_to_node + weight

                if self.dist[nex] > cand:  # update
                    self.dist[nex] = cand
                    self.prev[nex] = node
                    heapq.heappush(Q, (cand, nex))

    def get_dist(self, d):
        """
            startからdまでの距離を返す
            これの前にcalc()を実行しておく
            たどり着けない場合は、float('inf')がかえる
        """
        return self.dist[d]
    def get_path(self,dst):
        """
        startからdstまでのpathをlistでreturn
        valifyしてないので怪しい
        """
        cur=dst
        ret=[cur]
        while cur!=self.start_node:
            cur=self.prev[cur]
            ret.append(cur)
        return list(reversed(ret))

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

mat_s=[[float('inf')]*N for _ in range(N)]
mat_t=[[float('inf')]*N for _ in range(N)]
for _ in range(M):
    a,b,c,d = map(int,input().split())
    mat_s[a-1][b-1]=c
    mat_s[b-1][a-1]=c
    mat_t[a-1][b-1]=d
    mat_t[b-1][a-1]=d

D_S = Dijkstra(S-1,N,mat_s)
D_T = Dijkstra(T-1,N,mat_t)

D_S.calc_dist()
D_T.calc_dist()

ans=[None]*N

for i in range(N):
    ans[i]= D_S.get_dist(i)+D_T.get_dist(i)

tmp=float("inf")

ans_list=[]
for i in reversed(range(N)):
    tmp = min(tmp,ans[i])
    ans_list.append(10**15-tmp)
print("\n".join(map(str,reversed(ans_list))))

Submission status: Time Limit Exceeded

Solution code:
import heapq
n,m,s,t = map(int,input().split())
edgeY = [[] for _ in range(n)]
edgeS = [[] for _ in range(n)]
for i in range(m):
    u,v,a,b = map(int,input().split())
    edgeY[u-1].append([a, v-1])
    edgeY[v-1].append([a, u-1])
    edgeS[u-1].append([b, v-1])
    edgeS[v-1].append([b, u-1])
costY = [float('inf')]*n
costS = [float('inf')]*n
costY[s-1] = 0
costS[t-1] = 0

# 円の時
q = []
for i in edgeY[s-1]:
    heapq.heappush(q, i)
while len(q):
    nowEdge = heapq.heappop(q)
    if costY[nowEdge[1]] == float('inf'):
        costY[nowEdge[1]] = nowEdge[0]
        for i in edgeY[nowEdge[1]]:
            heapq.heappush(q , [i[0]+costY[nowEdge[1]], i[1]])

# スヌークの時
q = []
for i in edgeS[t-1]:
    heapq.heappush(q, i)        
while len(q):
    nowEdge = heapq.heappop(q)
    if costS[nowEdge[1]] == float('inf'):
        costS[nowEdge[1]] = nowEdge[0]
        for i in edgeS[nowEdge[1]]:
            heapq.heappush(q , [i[0]+costS[nowEdge[1]], i[1]])
cost = []
ans = []
first = 10**15
minCost = 10**15
for i in range(n-1,-1,-1):
    nowCost = costY[i]+costS[i]
    if minCost > nowCost:
        minCost = nowCost
    ans.append(minCost)
for i in range(n-1,-1,-1):
    print(first- ans[i])

Submission status: Time Limit Exceeded

Solution code:
import heapq
def dijkstra_heap(s,edge):
    #始点sから各頂点への最短距離
    d = [float("inf")] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d


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

y_edge = [[] for i in range(n)]
s_edge = [[] for i in range(n)]
#edge[i] : iから出る道の[重み,行先]の配列
for i in range(m):
    x,y,yen,strc = map(int,input().split())
    y_edge[x-1].append([yen,y-1])
    y_edge[y-1].append([yen,x-1])
    s_edge[x-1].append([strc,y-1]) 
    s_edge[y-1].append([strc,x-1])

y_dis = dijkstra_heap(s-1,y_edge)
s_dis = dijkstra_heap(t-1,s_edge)
m = 0
ans = []
for y,s in zip(y_dis[::-1], s_dis[::-1]):
    t = 10**15-y-s
    m = max(m,t)
    ans.append(m)

print(*ans[::-1], sep="\n")

Submission status: Time Limit Exceeded

Solution code:
import collections
import heapq


class Dijkstra:
    def __init__(self):
        self.e = collections.defaultdict(list)

    def add(self, u, v, d):  #無向グラフの場合
        self.e[u].append([v, d])
        self.e[v].append([u, d])

    def delete(self, u, v):
        self.e[u] = [_ for _ in self.e[u] if _[0] != v]
        self.e[v] = [_ for _ in self.e[v] if _[0] != u]

    def search(self, s):  #d[i]はsからiまでの最短距離
        d = collections.defaultdict(lambda: float('inf'))
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True

            for uv, ud in self.e[u]:
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    heapq.heappush(q, (vd, uv))

        return d

n,m,s,t = map(int,input().split())
data = [list(map(int,input().split())) for i in range(m)]

G1 = Dijkstra()
G2 = Dijkstra()

for i in range(m):
    G1.add(data[i][0],data[i][1],data[i][2])
    G2.add(data[i][0],data[i][1],data[i][3])

D1 = G1.search(s)
D2 = G2.search(t)

A = []

for i in range(1,n+1):
    A.append((D1[i]+D2[i],i))

A.sort()

b = 0
for i in range(n):
    if i == 0:
        print(10**15-A[i][0])
    elif i < A[b][1]:
        print(10**15-A[b][0])
    else:
        while i >= A[b][1]:
            b += 1
        print(10**15-A[b][0])

Submission status: Time Limit Exceeded

Solution code:
import heapq
INF = 10 ** 16


def dijkstra(n, train, start):
    d = []
    queue = []
    for i in range(n):
        d.append(INF)
    d[start] = 0
    heapq.heappush(queue, (0, start))
    # 都市kに行く時の円またはスヌークのの最小値
    while len(queue) != 0:
        distance, v = queue.pop()
        if d[v] < distance:
            continue
        for u in range(len(train[v])):
            if d[train[v][u][0]] > d[v] + train[v][u][1]:
                d[train[v][u][0]] = d[v] + train[v][u][1]
                heapq.heappush(queue, (d[train[v][u][0]], train[v][u][0]))

    return d


def main():
    n, m, s, t = map(int, input().split())
    s -= 1
    t -= 1
    money = 10 ** 15
    train_en = []
    train_snuuk = []

    for i in range(n):
        train_en.append([])
        train_snuuk.append([])
    for i in range(m):
        fro, to, a, b = map(int, input().split())
        fro -= 1
        to -= 1
        train_en[fro].append((to, a))
        train_en[to].append((fro, a))
        train_snuuk[fro].append((to, b))
        train_snuuk[to].append((fro, b))

    a = dijkstra(n, train_en, s)
    b = dijkstra(n, train_snuuk, t)

    total = []
    for i in range(n):
        heapq.heappush(total, (a[i] + b[i], i + 1))
    mon, year = heapq.heappop(total)
    for i in range(n):
        while year <= i:
            mon, year = heapq.heappop(total)
        print(money - mon)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import heapq
INF = 10 ** 16


def dijkstra(n, town, k, start):
    d = []
    queue = []
    for i in range(n):
        d.append(INF)
    d[start] = 0
    heapq.heappush(queue, (0, start))
    # 都市kに行く時の円またはスヌークのの最小値
    while len(queue) != 0:
        distance, v = queue.pop()
        if d[v] < distance:
            continue
        for u in range(len(town[v])):
            if d[town[v][u][0]] > d[v] + town[v][u][k]:
                d[town[v][u][0]] = d[v] + town[v][u][k]
                heapq.heappush(queue, (d[town[v][u][0]], town[v][u][0]))

    return d


def main():
    n, m, s, t = map(int, input().split())
    s -= 1
    t -= 1
    money = 10 ** 15
    town = []

    for i in range(n):
        town.append([])
    for i in range(m):
        fro, to, a, b = map(int, input().split())
        fro -= 1
        to -= 1
        town[fro].append((to, a, b))
        town[to].append((fro, a, b))

    a = dijkstra(n, town, 1, s)
    b = dijkstra(n, town, 2, t)

    total = []
    for i in range(n):
        heapq.heappush(total, (a[i] + b[i], i + 1))
    mon, year = heapq.heappop(total)
    for i in range(n):
        while year <= i:
            mon, year = heapq.heappop(total)
        print(money - mon)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import heapq
INF = 10 ** 16


def dijkstra(n, town, k, start):
    d = []
    queue = []
    for i in range(n):
        d.append(INF)
    d[start] = 0
    heapq.heappush(queue, (0, start))
    # 都市kで交換した時の円またはスヌークのの最小値
    while len(queue) != 0:
        distance, v = queue.pop()
        if d[v] < distance:
            continue
        for u in range(len(town[v])):
            if d[town[v][u][0]] > d[v] + town[v][u][k]:
                d[town[v][u][0]] = d[v] + town[v][u][k]
                heapq.heappush(queue, (d[town[v][u][0]], town[v][u][0]))

    return d


def main():
    n, m, s, t = map(int, input().split())
    s -= 1
    t -= 1
    money = 10 ** 15
    town = []

    for i in range(n):
        town.append([])
    for i in range(m):
        fro, to, a, b = map(int, input().split())
        fro -= 1
        to -= 1
        town[fro].append((to, a, b))
        town[to].append((fro, a, b))

    a = dijkstra(n, town, 1, s)
    b = dijkstra(n, town, 2, t)

    total = []
    for i in range(n):
        heapq.heappush(total, (a[i] + b[i], i + 1))
    mon, year = heapq.heappop(total)
    for i in range(n):
        while year <= i:
            mon, year = heapq.heappop(total)
        print(money - mon)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import heapq
INF = 10 ** 16


def dijkstra(n, town, k, start):
    d = []
    used = []
    for i in range(n):
        d.append(INF)
        used.append(False)
    d[start] = 0
    # 都市kで交換した時の円またはスヌークのの最小値
    while True:
        v = -1
        for u in range(n):
            if not used[u] and (v == -1 or d[u] < d[v]):
                v = u
        if v == -1:
            break
        used[v] = True
        for u in range(len(town[v])):
            if d[v] + town[v][u][k] < d[town[v][u][0]]:
                d[town[v][u][0]] = d[v] + town[v][u][k]
    return d


def main():
    n, m, s, t = map(int, input().split())
    s -= 1
    t -= 1
    money = 10 ** 15
    town = []

    for i in range(n):
        town.append([])
    for i in range(m):
        fro, to, a, b = map(int, input().split())
        fro -= 1
        to -= 1
        town[fro].append((to, a, b))
        town[to].append((fro, a, b))

    a = dijkstra(n, town, 1, s)
    b = dijkstra(n, town, 2, t)

    total = []
    for i in range(n):
        heapq.heappush(total, (a[i] + b[i], i + 1))
    count = 0
    mon, year = heapq.heappop(total)
    for i in range(n):
        while year <= i:
            mon, year = heapq.heappop(total)
        print(money - mon)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
import copy
import heapq
INF = 10 ** 16


def dijkstra(n, town, k, start):
    d = []
    used = []
    for i in range(n):
        d.append(INF)
        used.append(False)
    d[start] = 0
    # 都市kで交換した時の円またはスヌークのの最小値
    while True:
        v = -1
        for u in range(n):
            if not used[u] and (v == -1 or d[u] < d[v]):
                v = u
        if v == -1:
            break
        used[v] = True
        for u in range(len(town[v])):
            if d[v] + town[v][u][k] < d[town[v][u][0]]:
                d[town[v][u][0]] = d[v] + town[v][u][k]
    return d


def main():
    n, m, s, t = map(int, input().split())
    s -= 1
    t -= 1
    money = 10 ** 15
    town = []

    for i in range(n):
        town.append([])
    for i in range(m):
        fro, to, a, b = map(int, input().split())
        fro -= 1
        to -= 1
        town[fro].append((to, a, b))
        town[to].append((fro, a, b))
    
    a = dijkstra(n, town, 1, s)
    b = dijkstra(n, town, 2, t)

    total = []
    for i in range(n):
        heapq.heappush(total, (a[i] + b[i], i + 1))
    count = 0
    while count < n:
        mon, year = heapq.heappop(total)
        if year > count:
            heapq.heappush(total, (mon, year))
            print(money - mon)
            count += 1
        else:
            continue
    

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

cost_a = [[float("inf")] * (n+1) for _ in range(n+1)]
cost_b = [[float("inf")] * (n+1) for _ in range(n+1)]

for _ in range(m):
    u, v, a, b = map(int, input().split())
    cost_a[u][v] = a
    cost_a[v][u] = a
    cost_b[u][v] = b
    cost_b[v][u] = b

d_a = [float("inf")] * (n+1)
d_a[s] = 0
d_b = [float("inf")] * (n+1)
d_b[t] = 0
visit_a = [False] * (n+1)
visit_b = [False] * (n+1)

while True:
    v = -1
    for i in range(1, n+1):
        if v == -1 and not visit_a[i]:
            v = i
        elif d_a[i] < d_a[v] and not visit_a[i]:
            v = i
    if v == -1:
        break
    visit_a[v] = True
    
    for j in range(1, n+1):
        d_a[j] = min(d_a[j], d_a[v] + cost_a[v][j])
        
while True:
    v = -1
    for i in range(1, n+1):
        if v == -1 and not visit_b[i]:
            v = i
        elif d_b[i] < d_b[v] and not visit_b[i]:
            v = i
    if v == -1:
        break
    visit_b[v] = True
    
    for j in range(1, n+1):
        d_b[j] = min(d_b[j], d_b[v] + cost_b[v][j])
    
for i in range(n):
    cost = 0
    for j in range(i+1, n+1):
        cost = max(cost, 10 ** 15 - d_a[j] - d_b[j])
    print(cost)

Submission status: Time Limit Exceeded

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

def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d


def main():
    n, m, s, t = map(int, input().split())
    trains = [list(map(int, input().split())) for i in range(m)]

    INF = float('inf')

    cost_yen = [[INF for i in range(n)] for j in range(n)]
    cost_snuuk = [[INF for i in range(n)] for j in range(n)]

    for train in trains:
        u, v, a, b = train
        cost_yen[u-1][v-1] = a
        cost_yen[v-1][u-1] = a
        cost_snuuk[u-1][v-1] = b
        cost_snuuk[v-1][u-1] = b

    d_yen = dijkstra(s-1, n, m, cost_yen)
    d_snuuk = dijkstra(t-1, n, m, cost_snuuk)


    cost_sum = [[d_yen[i]+d_snuuk[i], i+1] for i in range(n)]
    heapq.heapify(cost_sum)
    c, l = heapq.heappop(cost_sum)
    for i in range(n):
        while l<=i:
            c, l = heapq.heappop(cost_sum)
        print(10**15 - c)

if __name__ == '__main__':
     main()

Submission status: Time Limit Exceeded

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

def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d


def main():
    n, m, s, t = map(int, input().split())
    trains = [list(map(int, input().split())) for i in range(m)]

    INF = float('inf')

    cost_yen = [[INF for i in range(n)] for j in range(n)]
    cost_snuuk = [[INF for i in range(n)] for j in range(n)]

    for train in trains:
        u, v, a, b = train
        cost_yen[u-1][v-1] = a
        cost_yen[v-1][u-1] = a
        cost_snuuk[u-1][v-1] = b
        cost_snuuk[v-1][u-1] = b

    d_yen = dijkstra(s-1, n, m, cost_yen)
    d_snuuk = dijkstra(t-1, n, m, cost_snuuk)


    cost_sum = [[d_yen[i]+d_snuuk[i], i+1] for i in range(n)]
    heapq.heapify(cost_sum)
    c, l = heapq.heappop(cost_sum)
    for i in range(n):
        while l<=i:
            c, l = heapq.heappop(cost_sum)
        print(10**15 - c)
main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq

def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d

input = sys.stdin.readline

n, m, s, t = map(int, input().split())
trains = [list(map(int, input().split())) for i in range(m)]

INF = float('inf')

cost_yen = [[INF for i in range(n)] for j in range(n)]
cost_snuuk = [[INF for i in range(n)] for j in range(n)]

for train in trains:
    u, v, a, b = train
    cost_yen[u-1][v-1] = a
    cost_yen[v-1][u-1] = a
    cost_snuuk[u-1][v-1] = b
    cost_snuuk[v-1][u-1] = b

d_yen = dijkstra(s-1, n, m, cost_yen)
d_snuuk = dijkstra(t-1, n, m, cost_snuuk)


cost_sum = [[d_yen[i]+d_snuuk[i], i+1] for i in range(n)]
heapq.heapify(cost_sum)
c, l = heapq.heappop(cost_sum)
for i in range(n):
    while l<=i:
        c, l = heapq.heappop(cost_sum)
    print(10**15 - c)

Submission status: Time Limit Exceeded

Solution code:
import sys
from scipy.sparse.csgraph import csgraph_from_dense, dijkstra

""" def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d """

input = sys.stdin.readline

n, m, s, t = map(int, input().split())
trains = [list(map(int, input().split())) for i in range(m)]

INF = float('inf')

cost_yen = [[INF for i in range(n)] for j in range(n)]
cost_snuuk = [[INF for i in range(n)] for j in range(n)]

for train in trains:
    u, v, a, b = train
    cost_yen[u-1][v-1] = a
    cost_yen[v-1][u-1] = a
    cost_snuuk[u-1][v-1] = b
    cost_snuuk[v-1][u-1] = b

G_yen = csgraph_from_dense(cost_yen, null_value=INF)
G_snuuk = csgraph_from_dense(cost_snuuk, null_value=INF)

d_yen = dijkstra(G_yen, indices=s-1)
d_snuuk = dijkstra(G_snuuk, indices=t-1)


cost_sum = [x+y for x, y in zip(d_yen, d_snuuk)]
for i in range(n):
    print(int(10**15 - min(cost_sum[i:])))