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 heapq

class Dijkstra(object):
    def dijkstra(self, adj, start, goal=None):
        '''
        ダイクストラアルゴリズムによる最短経路を求めるメソッド
        入力
        adj: adj[i][j]の値が頂点iから頂点jまでの距離(頂点iから頂点jに枝がない場合，値はfloat('inf'))となるような2次元リスト(正方行列)
        start: 始点のID
        goal: オプション引数．終点のID
        出力
        goalを引数に持つ場合，startからgoalまでの最短経路を格納したリストを返す
        持たない場合は，startから各頂点までの最短距離を格納したリストを返す
        >>> d = Dijkstra()
        >>> d.dijkstra([[float('inf'), 2, 4, float('inf'), float('inf')], [2, float('inf'), 3, 5, float('inf')], [4, 3, float('inf'), 1, 4], [float('inf'), 5, 1, float('inf'), 3], [float('inf'), float('inf'), 4, 3, float('inf')]], 0)
        [0, 2, 4, 5, 8] # 例えば，始点0から頂点3までの最短距離は5となる
        >>> d.dijkstra([[float('inf'), 2, 4, float('inf'), float('inf')], [2, float('inf'), 3, 5, float('inf')], [4, 3, float('inf'), 1, 4], [float('inf'), 5, 1, float('inf'), 3], [float('inf'), float('inf'), 4, 3, float('inf')]], 0, goal=4)
        [0, 2, 4] # 頂点0から頂点4までの最短経路は0 -> 2 -> 4となる
        '''
        num = len(adj)          # グラフのノード数
        dist = [float('inf') for i in range(num)] # 始点から各頂点までの最短距離を格納する
        prev = [float('inf') for i in range(num)] # 最短経路における，その頂点の前の頂点のIDを格納する
        
        dist[start] = 0
        q = []                  # プライオリティキュー．各要素は，(startからある頂点vまでの仮の距離, 頂点vのID)からなるタプル
        heapq.heappush(q, (0, start)) # 始点をpush

        while len(q) != 0:
            prov_cost, src = heapq.heappop(q) # pop
            
            # プライオリティキューに格納されている最短距離が，現在計算できている最短距離より大きければ，distの更新をする必要はない
            if dist[src] < prov_cost:
                continue

            # 他の頂点の探索
            for dest in range(num):
                cost = adj[src][dest]
                if cost != float('inf') and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost # distの更新
                    heapq.heappush(q, (dist[dest], dest)) # キューに新たな仮の距離の情報をpush
                    prev[dest] = src                      # 前の頂点を記録
                    
        if goal is not None:
            return self.get_path(goal, prev)
        else:
            return dist

    def get_path(self, goal, prev):
        '''
        始点startから終点goalまでの最短経路を求める
        '''
        path = [goal]           # 最短経路
        dest = goal

        # 終点から最短経路を逆順に辿る
        while prev[dest] != float('inf'):
            path.append(prev[dest])
            dest = prev[dest]

        # 経路をreverseして出力
        return list(reversed(path))


n, m, s, t = map(int, input().split())
s, t = s-1, t-1
route_yen = [[10**15 for i in range(n)] for j in range(n)]
route_snook = [[10**15 for i in range(n)] for j in range(n)]
for i in range(m):
    ui, vi, ai, bi = map(int, input().split())
    ui, vi = vi-1, ui-1
    route_yen[ui][vi], route_yen[vi][ui] = ai, ai
    route_snook[ui][vi], route_snook[vi][ui] = bi, bi

yen = Dijkstra()
distance_yen = yen.dijkstra(route_yen, s)
snook = Dijkstra()
distance_snook = snook.dijkstra(route_snook, t)

ans_lst = [0 for i in range(n)]
temp_min = 10**15
for i in range(n)[::-1]:
    now = distance_yen[i] + distance_snook[i]
    temp_min = min(temp_min, now)
    ans_lst[i] = 10**15 - temp_min

for i in range(n):
    print(ans_lst[i])

Submission status: Time Limit Exceeded

Solution code:
n, m, s, t = map(int, input().split())
s, t = s-1, t-1
route_yen = [[0 for i in range(n)] for j in range(n)]
route_snook = [[0 for i in range(n)] for j in range(n)]
for i in range(m):
    ui, vi, ai, bi = map(int, input().split())
    ui, vi = vi-1, ui-1
    route_yen[ui][vi], route_yen[vi][ui] = ai, ai
    route_snook[ui][vi], route_snook[vi][ui] = bi, bi

node_num = n #ノードの数

unsearched_nodes = list(range(node_num)) # 未探索ノード
distance_yen = [10**15] * node_num # ノードごとの距離のリスト
previous_nodes = [-1] * node_num # 最短経路でそのノードのひとつ前に到達するノードのリスト
distance_yen[s] = 0 # 初期のノードの距離は0とする

# @GDaigo さんのコメントより関数の追加 2017/03/18
def get_target_min_index(min_index, distance, unsearched_nodes):
    start = 0
    while True:
        index = distance.index(min_index, start)
        found = index in unsearched_nodes
        if found:
            return index
        else:
            start = index + 1

while(len(unsearched_nodes) != 0): #未探索ノードがなくなるまで繰り返す
    # まず未探索ノードのうちdistanceが最小のものを選択する
    posible_min_distance = 10**15 # 最小のdistanceを見つけるための一時的なdistance。初期値は inf に設定。
    for node_index in unsearched_nodes: # 未探索のノードのループ
        if posible_min_distance > distance_yen[node_index]: 
            posible_min_distance = distance_yen[node_index] # より小さい値が見つかれば更新
    target_min_index = get_target_min_index(posible_min_distance, distance_yen, unsearched_nodes) # 未探索ノードのうちで最小のindex番号を取得
    unsearched_nodes.remove(target_min_index) # ここで探索するので未探索リストから除去

    target_edge = route_yen[target_min_index] # ターゲットになるノードからのびるエッジのリスト
    for index, route_dis in enumerate(target_edge):
        if route_dis != 0:
            if distance_yen[index] > (distance_yen[ target_min_index] + route_dis):
                distance_yen[index] = distance_yen[ target_min_index] + route_dis # 過去に設定されたdistanceよりも小さい場合はdistanceを更新
                previous_nodes[index] =  target_min_index #　ひとつ前に到達するノードのリストも更新


unsearched_nodes = list(range(node_num)) # 未探索ノード
distance_snook = [10**15] * node_num # ノードごとの距離のリスト
previous_nodes = [-1] * node_num # 最短経路でそのノードのひとつ前に到達するノードのリスト
distance_snook[t] = 0 # 初期のノードの距離は0とする

while(len(unsearched_nodes) != 0): #未探索ノードがなくなるまで繰り返す
    # まず未探索ノードのうちdistanceが最小のものを選択する
    posible_min_distance = 10**15 # 最小のdistanceを見つけるための一時的なdistance。初期値は inf に設定。
    for node_index in unsearched_nodes: # 未探索のノードのループ
        if posible_min_distance > distance_snook[node_index]: 
            posible_min_distance = distance_snook[node_index] # より小さい値が見つかれば更新
    target_min_index = get_target_min_index(posible_min_distance, distance_snook, unsearched_nodes) # 未探索ノードのうちで最小のindex番号を取得
    unsearched_nodes.remove(target_min_index) # ここで探索するので未探索リストから除去

    target_edge = route_snook[target_min_index] # ターゲットになるノードからのびるエッジのリスト
    for index, route_dis in enumerate(target_edge):
        if route_dis != 0:
            if distance_snook[index] > (distance_snook[ target_min_index] + route_dis):
                distance_snook[index] = distance_snook[ target_min_index] + route_dis # 過去に設定されたdistanceよりも小さい場合はdistanceを更新
                previous_nodes[index] =  target_min_index #　ひとつ前に到達するノードのリストも更新


ans_lst = [0 for i in range(n)]
temp_min = 10**15
for i in range(n)[::-1]:
    now = distance_yen[i] + distance_snook[i]
    temp_min = min(temp_min, now)
    ans_lst[i] = 10**15 - temp_min

for i in range(n):
    print(ans_lst[i])

Submission status: Time Limit Exceeded

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


def to_v(i, j):
    return 2*i+j


N = 2*n
edges = [[]for _ in range(N)]
for _ in range(m):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    edges[to_v(u, 0)].append((a, to_v(v, 0)))
    edges[to_v(v, 0)].append((a, to_v(u, 0)))
    edges[to_v(u, 1)].append((b, to_v(v, 1)))
    edges[to_v(v, 1)].append((b, to_v(u, 1)))

for u in range(n):
    edges[to_v(u, 0)].append((0, to_v(u, 1)))


def dijkstra(init_v):
    next_v = [(0, init_v)]
    INF = 10**18
    dist = [INF]*N
    dist[init_v] = 0
    while next_v:
        d, v = heapq.heappop(next_v)
        if dist[v] < d:
            continue
        for d, v2 in edges[v]:
            if dist[v2] <= dist[v]+d:
                continue
            dist[v2] = dist[v]+d
            heapq.heappush(next_v, (dist[v2], v2))
    return dist
  

for i in range(n):
    if i != 0:
        i -= 1
        edges[to_v(i, 0)].pop()
    dist = dijkstra(to_v(s-1, 0))
    print(10**15-dist[to_v(t-1, 1)])

Submission status: Time Limit Exceeded

Solution code:
import heapq
def dijkstra(G, s):
    dist = [float("inf")]*len(G)
    q = []
    dist[s] = 0
    heapq.heapify(q)
    heapq.heappush(q, [0, s])
    while 0 < len(q):
        pre_cost, p = heapq.heappop(q)
        if dist[p] < pre_cost:
            continue
        for v, d in G[p]:
            if dist[v] > dist[p] + d:
                dist[v] = dist[p] + d
                heapq.heappush(q, [dist[v], v])
    return dist
def main():
    n, m, s, t = map(int, input().split())
    s, t = s-1, t-1
    G_y = [[] for _ in range(n)]
    G_s = [[] for _ in range(n)]
    f = [True]*n
    for _ in range(m):
        u, v, a, b = map(int, input().split())
        u, v = u-1, v-1
        G_y[u].append([v, a])
        G_y[v].append([u, a])
        G_s[u].append([v, b])
        G_s[v].append([u, b])
    cost_y = dijkstra(G_y, s)
    cost_s = dijkstra(G_s, t)
    cost = [[cost_y[i] + cost_s[i], i] for i in range(n)]
    cost.sort()
    x = 0
    for i in range(n):
        while not f[cost[x][1]]:
            x += 1
        print(10**15 - cost[x][0])
        f[i] = False

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import heapq
def dijkstra(G, s):
    dist = [float("inf")]*len(G)
    q = []
    dist[s] = 0
    heapq.heapify(q)
    heapq.heappush(q, [0, s])
    while 0 < len(q):
        pre_cost, p = heapq.heappop(q)
        if dist[p] < pre_cost:
            continue
        for v, d in G[p]:
            if dist[v] > dist[p] + d:
                dist[v] = dist[p] + d
                heapq.heappush(q, [dist[v], v])
    return dist
def main():
    n, m, s, t = map(int, input().split())
    s, t = s-1, t-1
    G_y = [[] for _ in range(n)]
    G_s = [[] for _ in range(n)]
    f = [True]*n
    for _ in range(m):
        u, v, a, b = map(int, input().split())
        u, v = u-1, v-1
        G_y[u].append([v, a])
        G_y[v].append([u, a])
        G_s[u].append([v, b])
        G_s[v].append([u, b])
    cost_y = dijkstra(G_y, s)
    cost_s = dijkstra(G_s, t)
    cost = [[cost_y[i] + cost_s[i], i] for i in range(n)]
    cost.sort()
    x = 0
    for i in range(n):
        while not f[cost[x][1]]:
            x += 1
        print(pow(10, 15) - cost[x][0])
        f[i] = False

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import namedtuple
from heapq import heappush, heappop

INF = sys.maxsize

P = namedtuple('P', 'cost v')
Edage = namedtuple('Edge', 'to cost')

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

s, t = 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, v = u - 1, v - 1
  
  Yen[u].append(Edage(v, a))
  Yen[v].append(Edage(u, a))
  Snuuk[u].append(Edage(v, b))
  Snuuk[v].append(Edage(u, b))

  
def min_costs(graph, start):
  costs = [INF] * n
  costs[start] = 0
  
  q = [P(0, start)]
  
  while q:
    cost, v = heappop(q)
    if cost > costs[v]:
      continue
    for to, cost in graph[v]:
      if costs[to] > costs[v] + cost:
        costs[to] = costs[v] + cost
        heappush(q, P(costs[to], to))        
        
  return costs
  
total_costs = [
  min_costs(Yen, s)[i] + min_costs(Snuuk, t)[i] 
  for i in range(n)
]

# 両替所が閉鎖されていく
for i in range(n - 1, 0, -1):
  total_costs[i - 1] = min(total_costs[i - 1], total_costs[i])
                      
    
for i in range(n):
  print(10 ** 15 - total_costs[i])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
n,m,s,t = map(int,input().split())
es = deque([])
der = deque([])
for i in range(m):
  u,v,a,b = map(int,input().split())
  es.append((u-1,v-1,a))
  es.append((v-1,u-1,a))
  der.append((u-1,v-1,b))
  der.append((v-1,u-1,b))

es = tuple(es)
der = tuple(der)
def shortest_path(S,n,w,es): 
  d = [10**15] * n #d[i] : s→iの最短距離
  d[S] = 0
  while True:
    update = False
    for p,q,r in es: # e: 辺iについて [from,to,cost]
      if d[p] != 10**15 and d[q] > d[p] + r:
        d[q] = d[p] + r
        update = True       
    if not update:
      break
  return d

chk = [0]*n
ES = tuple(shortest_path(s-1,n,m*2,es))
DER = tuple(shortest_path(t-1,n,m*2,der))
cost = 10**15
for i in range(n-1,-1,-1):
  cost = min(cost,ES[i]+DER[i])
  chk[i] = 10**15-cost
chk = tuple(chk)

print(*chk, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
n,m,s,t = map(int,input().split())
es = deque([])
der = deque([])
for i in range(m):
  u,v,a,b = map(int,input().split())
  es.append((u-1,v-1,a))
  es.append((v-1,u-1,a))
  der.append((u-1,v-1,b))
  der.append((v-1,u-1,b))

es = tuple(es)
der = tuple(der)
def shortest_path(S,g,w,es): 
  d = [10**15] * n #d[i] : s→iの最短距離
  d[S] = 0
  while True:
    update = False
    for p,q,r in es: # e: 辺iについて [from,to,cost]
      if d[p] != 10**15 and d[q] > d[p] + r:
        d[q] = d[p] + r
        update = True       
    if not update:
      break
  return d[g]

chk = [0]*(n+1)
for i in range(n-1,-1,-1):
  chk[i] = max(chk[i+1],10**15-shortest_path(s-1,i,m*2,es)-shortest_path(t-1,i,m*2,der))

chk = tuple(chk)
for i in range(n):
  print(chk[i])

Submission status: Time Limit Exceeded

Solution code:
def main():  
  import sys
  input = sys.stdin.readline
  from collections import deque
  n,m,s,t = map(int,input().split())
  es = deque([])
  der = deque([])
  for _ in range(m):
    u,v,a,b = map(int,input().split())
    es.append((u-1,v-1,a))
    es.append((v-1,u-1,a))
    der.append((u-1,v-1,b))
    der.append((v-1,u-1,b))

  es = tuple(es)
  der = tuple(der)
  def shortest_path(S,g,w,es): 
    d = [10**15] * n #d[i] : s→iの最短距離
    d[S] = 0
    while True:
      update = False
      for p,q,r in es: # e: 辺iについて [from,to,cost]
        if d[p] != 10**15 and d[q] > d[p] + r:
          d[q] = d[p] + r
          update = True       
      if not update:
        break
    return d[g]

  chk = deque([])
  for i in range(n):
    chk.append(10**15-shortest_path(s-1,i,m*2,es)-shortest_path(t-1,i,m*2,der))

  chk = tuple(chk)
  for i in range(n):
    print(max(chk[i:]))
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
n,m,s,t = map(int,input().split())
es = deque([])
der = deque([])
for i in range(m):
  u,v,a,b = map(int,input().split())
  es.append((u-1,v-1,a))
  es.append((v-1,u-1,a))
  der.append((u-1,v-1,b))
  der.append((v-1,u-1,b))

es = tuple(es)
der = tuple(der)
def shortest_path(S,n,w,es): 
  d = [10**15] * n #d[i] : s→iの最短距離
  d[S] = 0
  while True:
    update = False
    for p,q,r in es: # e: 辺iについて [from,to,cost]
      if d[p] != 10**15 and d[q] > d[p] + r:
        d[q] = d[p] + r
        update = True       
    if not update:
      break
  return d

chk = [0]*(n+1)
ES = tuple(shortest_path(s-1,n,m*2,es))
DER = tuple(shortest_path(t-1,n,m*2,der))
for i in range(n-1,-1,-1):
  chk[i] = max(chk[i+1],10**15-ES[i]-DER[i])

chk = tuple(chk)
for i in range(n):
  print(chk[i])

Submission status: Time Limit Exceeded

Solution code:
def main():  
  import sys
  input = sys.stdin.readline
  from collections import deque
  n,m,s,t = [int(i) for i in input().split()]
  es = deque([])
  der = deque([])
  for i in range(m):
    u,v,a,b = [int(i) for i in input().split()]
    es.append((u-1,v-1,a))
    es.append((v-1,u-1,a))
    der.append((u-1,v-1,b))
    der.append((v-1,u-1,b))

  es = tuple(es)
  der = tuple(der)
  def shortest_path(S,n,w,es): 
    d = [10**15] * n #d[i] : s→iの最短距離
    d[S] = 0
    while True:
      update = False
      for p,q,r in es: # e: 辺iについて [from,to,cost]
        if d[p] != 10**15 and d[q] > d[p] + r:
          d[q] = d[p] + r
          update = True       
      if not update:
        break
    return d

  chk = [0]*(n+1)
  ES = tuple(shortest_path(s-1,n,m*2,es))
  DER = tuple(shortest_path(t-1,n,m*2,der))
  for i in range(n-1,-1,-1):
    chk[i] = max(chk[i+1],10**15-ES[i]-DER[i])

  chk = tuple(chk)
  for i in range(n):
    print(chk[i])
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
n,m,s,t = [int(i) for i in input().split()]
es = deque([])
der = deque([])
for i in range(m):
  u,v,a,b = [int(i) for i in input().split()]
  es.append((u-1,v-1,a))
  es.append((v-1,u-1,a))
  der.append((u-1,v-1,b))
  der.append((v-1,u-1,b))
  
es = tuple(es)
der = tuple(der)
def shortest_path(S,n,w,es): 
  d = [10**15] * n #d[i] : s→iの最短距離
  d[S] = 0
  while True:
    update = False
    for p,q,r in es: # e: 辺iについて [from,to,cost]
      if d[p] != 10**15 and d[q] > d[p] + r:
        d[q] = d[p] + r
        update = True       
    if not update:
      break
  return d

chk = [0]*(n+1)
ES = tuple(shortest_path(s-1,n,m*2,es))
DER = tuple(shortest_path(t-1,n,m*2,der))
for i in range(n-1,-1,-1):
  chk[i] = max(chk[i+1],10**15-ES[i]-DER[i])
  
chk = tuple(chk)
for i in range(n):
  print(chk[i])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n,m,s,t = [int(i) for i in input().split()]
es = []
der = []
for i in range(m):
  u,v,a,b = [int(i) for i in input().split()]
  es_append = es.append
  der_append = der.append
  es_append((u-1,v-1,a))
  es_append((v-1,u-1,a))
  der_append((u-1,v-1,b))
  der_append((v-1,u-1,b))
  
def shortest_path(S,n,w,es): 
  d = [10**15] * n #d[i] : s→iの最短距離
  d[S] = 0
  while True:
    update = False
    for p,q,r in es: # e: 辺iについて [from,to,cost]
      if d[p] != 10**15 and d[q] > d[p] + r:
        d[q] = d[p] + r
        update = True       
    if not update:
      break
  return d

chk = [0]*(n+1)
ES = tuple(shortest_path(s-1,n,m*2,es))
DER = tuple(shortest_path(t-1,n,m*2,der))
for i in range(n-1,-1,-1):
  chk[i] = max(chk[i+1],10**15-ES[i]-DER[i])
  
chk = tuple(chk)
for i in range(n):
  print(chk[i])

Submission status: Time Limit Exceeded

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

def dijkstra(n, graph, s, yen=True):
    dist = [10**18] * n
    queue = [(s, 0)]
    dist[s] = 0
    while queue:
        v, d = heapq.heappop(queue)
        if dist[v] < d:
            continue
        for child, costa, costb in graph[v]:
            if yen:
                cost = costa
            else:
                cost = costb
            if dist[v] + cost < dist[child]:
                dist[child] = dist[v] + cost
                heapq.heappush(queue, (child, dist[child]))
    return dist

def main():
    n, m, s, t = map(int, input().split())
    s -= 1
    t -= 1
    graph = [[] for _ in range(n)]
    for i in range(m):
        u, v, a, b = map(int, input().split())
        u -= 1
        v -= 1
        graph[u].append((v, a, b))
        graph[v].append((u, a, b))
    s_dist = dijkstra(n, graph, s, True)
    t_dist = dijkstra(n, graph, t, False)

    cost = 10 ** 18
    ans = [0] * n
    for i in range(n-1, -1, -1):
        cost = min(cost, s_dist[i] + t_dist[i])
        ans[i] = 10 ** 15 - cost
    print(*ans, sep="\n")


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def dijkstra(n, graph, s, yen=True):
    dist = [10**18] * n
    queue = [(s, 0)]
    dist[s] = 0
    while queue:
        v, d = heapq.heappop(queue)
        if dist[v] < d:
            continue
        for child, costa, costb in graph[v]:
            if yen:
                cost = costa
            else:
                cost = costb
            if dist[v] + cost < dist[child]:
                dist[child] = dist[v] + cost
                heapq.heappush(queue, (child, dist[child]))
    return dist

def main():
    n, m, s, t = map(int, input().split())
    s -= 1
    t -= 1
    s_graph = [[] for _ in range(n)]
    t_graph = [[] for _ in range(n)]
    for i in range(m):
        u, v, a, b = map(int, input().split())
        u -= 1
        v -= 1
        s_graph[u].append((v, a, b))
        s_graph[v].append((u, a, b))
        t_graph[u].append((v, a, b))
        t_graph[v].append((u, a, b))
    s_dist = dijkstra(n, s_graph, s, True)
    t_dist = dijkstra(n, t_graph, t, False)

    cost = 10 ** 18
    ans = []
    for i in range(n-1, -1, -1):
        cost = min(cost, s_dist[i] + t_dist[i])
        ans.append(10 ** 15 - cost)
    for x in reversed(ans):
        print(x)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import permutations,combinations
from collections import defaultdict,Counter
from pprint import pprint

def myinput():
    return map(int,input().split())

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col):
    data.sort(key=lambda x:x[col],reverse=False)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

n,m,s,t = myinput()
uvab = mylistinput(m)

# Dijkstra法(O(ElogV))
# edge[i] : iから出る道の[重み,行先]の配列
import heapq
def dijkstra_heap(n,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

# Dijkstra法(O(ElogV))
# edge[i] : iから出る道の[重み,行先]の配列
# 高速化版 
# import heapq
# def dijkstra_heap(n,s,edge):
#     #始点sから各頂点への最短距離
#     d = [10**20] * n
#     used = [True] * n #True:未確定
#     d[s] = 0
#     used[s] = False
#     edgelist = []
#     for a,b in edge[s]:
#         heapq.heappush(edgelist,a*(10**6)+b)
#     while len(edgelist):
#         minedge = heapq.heappop(edgelist)
#         #まだ使われてない頂点の中から最小の距離のものを探す
#         if not used[minedge%(10**6)]:
#             continue
#         v = minedge%(10**6)
#         d[v] = minedge//(10**6)
#         used[v] = False
#         for e in edge[v]:
#             if used[e[1]]:
#                 heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
#     return d

g1 = [ [] for _ in range(n) ]
g2 = [ [] for _ in range(n) ]
for i in range(m):
    u = uvab[i][0] - 1
    v = uvab[i][1] - 1
    a = uvab[i][2]
    b = uvab[i][3]
    g1[u].append([a,v])
    g1[v].append([a,u])
    g2[u].append([b,v])
    g2[v].append([b,u])
# print(g1)
# print(g2)

d1 = dijkstra_heap(n,s-1,g1)
d2 = dijkstra_heap(n,t-1,g2)
# print(d1)
# print(d2)

yen = 10**15
ans = -1*float("inf")
ls_ans = [0]*n
for i in reversed(range(n)):
    snuke = yen - d1[i] - d2[i] 
    ans = max(ans,snuke)
    ls_ans[i] = ans

for i in range(n):
    print(ls_ans[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import permutations,combinations
from collections import defaultdict,Counter
from pprint import pprint

def myinput():
    return map(int,input().split())

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col):
    data.sort(key=lambda x:x[col],reverse=False)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

n,m,s,t = myinput()
uvab = mylistinput(m)

# Dijkstra法(O(ElogV))
# edge[i] : iから出る道の[重み,行先]の配列
# import heapq
# def dijkstra_heap(n,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

# Dijkstra法(O(ElogV))
# edge[i] : iから出る道の[重み,行先]の配列
# 高速化版 
import heapq
def dijkstra_heap(n,s,edge):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

g1 = [ [] for _ in range(n) ]
g2 = [ [] for _ in range(n) ]
for i in range(m):
    u = uvab[i][0] - 1
    v = uvab[i][1] - 1
    a = uvab[i][2]
    b = uvab[i][3]
    g1[u].append([a,v])
    g1[v].append([a,u])
    g2[u].append([b,v])
    g2[v].append([b,u])
# print(g1)
# print(g2)

d1 = dijkstra_heap(n,s-1,g1)
d2 = dijkstra_heap(n,t-1,g2)
# print(d1)
# print(d2)

ls_snuke = []
for i in range(n):
    snuke = 10**15 - d1[i] - d2[i]   
    ls_snuke.append(snuke)
# print(ls_snuke)

for i in range(n):
    print(max(ls_snuke[i:]))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import permutations,combinations
from collections import defaultdict,Counter
from pprint import pprint

def myinput():
    return map(int,input().split())

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col):
    data.sort(key=lambda x:x[col],reverse=False)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

n,m,s,t = myinput()
uvab = mylistinput(m)

# Dijkstra法(O(ElogV))
# edge[i] : iから出る道の[重み,行先]の配列
import heapq
def dijkstra_heap(n,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

g1 = [ [] for _ in range(n) ]
g2 = [ [] for _ in range(n) ]
for i in range(m):
    u = uvab[i][0] - 1
    v = uvab[i][1] - 1
    a = uvab[i][2]
    b = uvab[i][3]
    g1[u].append([a,v])
    g1[v].append([a,u])
    g2[u].append([b,v])
    g2[v].append([b,u])
# print(g1)
# print(g2)

d1 = dijkstra_heap(n,s-1,g1)
d2 = dijkstra_heap(n,t-1,g2)
# print(d1)
# print(d2)

ls_snuke = []
for i in range(n):
    snuke = 10**15 - d1[i] - d2[i]   
    ls_snuke.append(snuke)
# print(ls_snuke)

for i in range(n):
    print(max(ls_snuke[i:]))