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:
    def dijkstra(self, adj, start, goal=None):

        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))

from collections import defaultdict
Ey = defaultdict(lambda: defaultdict(lambda: float("inf")))
Es = defaultdict(lambda: defaultdict(lambda: float("inf")))


N, M, S, T = map(int, input().split())
E = [list(map(int, input().split())) for i in range(M)]

for e in E:
    u, v, a, b = e
    Ey[u-1][v-1] = Ey[v-1][u-1] = a
    Es[u-1][v-1] = Es[v-1][u-1] = b

dj = Dijkstra()
Dy = dj.dijkstra(Ey, S-1)
Ds = dj.dijkstra(Es, T-1)
mi = float("inf")
Ans = [0] * N
for i in range(N-1, -1, -1):
    mi = min(mi, Dy[i]+Ds[i])
    Ans[i] = mi
for a in Ans:
    print(10**15-a)

Submission status: Time Limit Exceeded

Solution code:
import copy


def travel(_from: int, _to: int, _destination: list, _visited: list, _cost: list):

    if (_from, _to) in _visited:
        return

    visited = copy.deepcopy(_visited)
    visited.append((_from, _to))

    destination = copy.deepcopy(_destination)
    destination.append(_to)

    cost = copy.deepcopy(_cost)

    cost.append(costs[(_from, _to)])

    if _to == city_to:
        routes.append((destination, cost))
        return

    for to_city in lines[_to]:
        travel(_to, to_city, destination, visited, cost)


input_line = input().split()

num_cities = int(input_line[0])
num_lines = int(input_line[1])
city_from = int(input_line[2])
city_to = int(input_line[3])

lines = {}
costs = {}

for _ in range(0, num_lines):
    input_line = input().split()
    line_from = int(input_line[0])
    line_to = int(input_line[1])
    cost_yen = int(input_line[2])
    cost_snuuk = int(input_line[3])
    costs[(line_from, line_to)] = (cost_yen, cost_snuuk)
    costs[(line_to, line_from)] = (cost_yen, cost_snuuk)

    if line_from in lines.keys():
        lines[line_from].append(line_to)
    else:
        lines[line_from] = [line_to]

    if line_to in lines.keys():
        lines[line_to].append(line_from)
    else:
        lines[line_to] = [line_from]

routes = []

for first_destination in lines[city_from]:
    travel(city_from, first_destination, [city_from], [], [])

for year in range(0, num_cities):
    valid_routes = []
    maximum_cost = 10 ** 15 + 1

    for visited_list, cost_list in routes:
        for index, exchange_on in enumerate(visited_list):
            if exchange_on <= year:
                continue

            paid = 0
            for i in range(0, index):
                yen, snuuk = cost_list[i]
                paid += yen
            for i in range(index, len(cost_list)):
                yen, snuuk = cost_list[i]
                paid += snuuk
            if paid > maximum_cost:
                continue

            valid_routes.append((paid, index, visited_list))
            maximum_cost = paid

    print(str(10 ** 15 - maximum_cost))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from heapq import heapify, heappop
import heapq
n,m,s,t =list(map(int,input().split()))

MAX_VAL = 10**20
uvab =  [list(map(int,input().split())) for _ in range(m)]
jpy_cost = defaultdict(lambda :defaultdict(lambda :MAX_VAL))
snuke_cost = defaultdict(lambda :defaultdict(lambda :MAX_VAL))


for u,v,a,b in uvab:
    u=u-1
    v=v-1
    jpy_cost[u][v] = a
    jpy_cost[v][u] =a
    snuke_cost[u][v]=b
    snuke_cost[v][u]=b


# Dijktra's shortest path algorithm. Prints the path from source to target.


def dijkstra(adj, source):
    INF = ((1 << 63) - 1) // 2
    pred = {x: x for x in range(n)}
    dist = {x: INF for x in range(n)}
    dist[source] = 0
    PQ = []
    heapq.heappush(PQ, [dist[source], source])

    while (PQ):
        u = heapq.heappop(PQ)  # u is a tuple [u_dist, u_id]
        u_dist = u[0]
        u_id = u[1]
        if u_dist == dist[u_id]:
            # if u_id == target:
            #    break
            for v in adj[u_id]:
                v_id = v
                w_uv = adj[u_id][v]
                if dist[u_id] + w_uv < dist[v_id]:
                    dist[v_id] = dist[u_id] + w_uv
                    heapq.heappush(PQ, [dist[v_id], v_id])
                    pred[v_id] = u_id

    return dist


jpy_dijk =  dijkstra(jpy_cost,s-1)
snuke_dijk = dijkstra(snuke_cost,t-1)
#
# print(s,t)
# print(jpy_dijk)
# print(snuke_dijk)
# print([jpy_dijk[i]+snuke_dijk[i] for i in range(n)])

#ord n
res = []
min_val = MAX_VAL
for i in reversed(range(n)):
    #都市  i で両替
    val = jpy_dijk[i]+ snuke_dijk[i]
    assert val < MAX_VAL
    min_val=min(min_val,val)
    res.append(min_val)
#ord n
for x in reversed(res):
    print(10**15-  x)

Submission status: Time Limit Exceeded

Solution code:

from heapq import *
from collections import defaultdict

def Dijkstra(s, V, E):
    # https://ja.wikipedia.org/wiki/%E3%83%80%E3%82%A4%E3%82%AF%E3%82%B9%E3%83%88%E3%83%A9%E6%B3%95
    d = defaultdict(lambda:10**30)
    d[s] = 0
    Q = []
    for v in V:
        heappush(Q, (d[v], v))
    while Q:
        x, u = heappop(Q)
        for v, y in E[u].items():
            alt = d[u] + y
            if d[v] > alt:
                d[v] = alt
                heappush(Q, (alt, v))
    return d

N, M, S, T = [int(_) for _ in input().split()]
UVAB = [[int(_) for _ in input().split()] for i in range(M)]

Ea = defaultdict(dict)
Eb = defaultdict(dict)

for u, v, a, b in UVAB:
    Ea[u][v] = a
    Ea[v][u] = a
    Eb[u][v] = b
    Eb[v][u] = b
    
V = list(range(1, N + 1))

Da = Dijkstra(S, V, Ea)
Db = Dijkstra(T, V, Eb)

T = [None] * (N + 1)
t = 10**30

for i in range(N, 0, -1):
    r = Da[i] + Db[i]
    t = min(t, r)
    T[i] = t

ST = 10**15

for i in range(1, N + 1):
    print(ST-T[i])

Submission status: Time Limit Exceeded

Solution code:
# encoding:utf-8
from collections import defaultdict

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

	cost_yen = defaultdict(lambda: 10 ** 10)
	cost_snook = defaultdict(lambda: 10 ** 10)
	for train in trains:
		cost_yen[(train[0]-1, train[1]-1)] = train[2]
		cost_yen[(train[1]-1, train[0]-1)] = train[2]
		cost_snook[(train[0]-1, train[1]-1)] = train[3]
		cost_snook[(train[1]-1, train[0]-1)] = train[3]

	d_yen = calc_distanc(cost_yen, s-1, n)
	d_snook = calc_distanc(cost_snook, t-1, n)

	d = {}
	for i in range(n):
		d[i] = 10 ** 15 - d_yen[i] - d_snook[i]


	max_year = -1
	for year in range(0, n):
		if max_year >= year:
			print(tmp_max)
		else:
			tmp_max = 0
			for i in range(year, n):
				if d[i] > tmp_max:
					tmp_max = d[i]
					max_year = i
			print(tmp_max)

def calc_distanc(cost, frm, n):
	d = defaultdict(lambda: 10 ** 6)

	for i in range(n):
		d[i] = cost[(i, frm)]

	d[frm] = 0
	unsearched_node = [i for i in range(n)]
	unsearched_node.remove(frm)

	while True:
		tmp_node = -1
		for v in unsearched_node:
			if tmp_node == -1:
				tmp_node = v
			elif d[v] < d[tmp_node]:
				tmp_node = v
		
		if tmp_node == -1:
			break

		unsearched_node.remove(tmp_node)

		for i in range(n):
			d[i] = min(d[i], d[tmp_node] + cost[(i, tmp_node)])

	return d

	


if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict 
import sys
import heapq

sys.setrecursionlimit(10**8)

#N:頂点数   M:辺数
N,M,s,t = map(int,input().split())


#root[n] -> nからいけるlist
root_yen = defaultdict(set)
root_snu = defaultdict(set)


#cost[a][b] = a -> b のコスト
cost_yen = [[0 for i in range(N+1)] for j in range(N+1)]
cost_snu = [[0 for i in range(N+1)] for j in range(N+1)]


#weight[a] = start -> a のコスト 未探索->-1
weight_yen = [-1 for i in range(N+1)]
weight_snu = [-1 for i in range(N+1)]
weight_yen[s] = 0
weight_snu[t] = 0


#q = 次に探索する(確定する)もの q[0]=[w,n]
q_yen = [[0,s]]
q_snu = [[0,t]]
heapq.heapify(q_yen)
heapq.heapify(q_snu)


for i in range(M):
	u,v,a,b = list(map(int,input().split())) #
	
	root_yen[u].add(v)
	root_yen[v].add(u)
	
	root_snu[u].add(v)
	root_snu[v].add(u)
	
	cost_yen[u][v] = a
	cost_yen[v][u] = a
	cost_snu[u][v] = b
	cost_snu[v][u] = b
	
	
def search_yen (n,w_0): #nから更新 w_0:確定コスト
	global cost_yen
	global weight_yen
	global q_yen
		
	for i in list(root_yen[n]):
		w = w_0 + cost_yen[n][i]
		if weight_yen[i] == -1 or weight_yen[i] > w: #未探索orより小さい
			heapq.heappush(q_yen, [w,i])
			weight_yen[i] = w
			
def search_snu (n,w_0): #nから更新 w_0:確定コスト
	global cost_snu
	global weight_snu
	global q_snu
		
	for i in list(root_snu[n]):
		w = w_0 + cost_snu[n][i]
		if weight_snu[i] == -1 or weight_snu[i] > w: #未探索orより小さい
			heapq.heappush(q_snu, [w,i])
			weight_snu[i] = w			
			
while q_yen:
	w,n = heapq.heappop(q_yen)
	search_yen(n,w)
	
while q_snu:
	w,n = heapq.heappop(q_snu)
	search_snu(n,w)
	

finalans = float('inf')
ans_li = []

for i in range(0,N):
	ans = weight_yen[N-i] + weight_snu[N-i]
	finalans = min(finalans, ans)
	ans_li.append(finalans)
	
for i in range(N):
	print(10**15 - ans_li[N-i-1])

Submission status: Time Limit Exceeded

Solution code:
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])

import heapq

class Dijkstra(object):
    def dijkstra(self, lst, start, goal=None):
        '''
        ダイクストラアルゴリズムによる最短経路を求めるメソッド
        入力
        adj: adj[i][j]の値が頂点iから頂点jまでの距離(頂点iから頂点jに枝がない場合，値はfloat('inf'))となるような2次元リスト(正方行列)
        start: 始点のID
        lst: 隣接リスト
        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(lst)         # グラフのノード数
        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):
            for dest in lst[src]:
                # cost = adj[src][dest]
                cost = dest[1]
                # if dist[dest] > dist[src] + cost:
                if dist[dest[0]] > dist[src] + cost:
                	# dist[dest] = dist[src] + cost # distの更新
                	dist[dest[0]] = dist[src] + cost
                    # heapq.heappush(q, (dist[dest], dest)) # キューに新たな仮の距離の情報をpush
                	heapq.heappush(q, (dist[dest[0]], dest[0]))
                    # prev[dest] = src                      # 前の頂点を記録
                	prev[dest[0]] = src
         
        # 以下は経路を返すプログラム           
        # if goal is not None:
        #     return self.get_path(goal, prev)
        if goal is not None:
        	return dist[goal]

        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))

d = Dijkstra()
yen = d.dijkstra(yen_edge, s - 1)
snuke = d.dijkstra(snuke_edge, t - 1)
ans_list = []

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

# print(yen)
# print(snuke)
# print(ans_list)
ans = [None for _ in range(n)]

ans[n - 1] = 10 ** 15 - ans_list[n - 1]

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

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

Submission status: Time Limit Exceeded

Solution code:
import queue

Gy = [{}]
Gs = [{}]

def y_setNode(n):
  global Gy
  Gy = [{} for i in range(n)]
def s_setNode(n):
  global Gs
  Gs = [{} for i in range(n)]
def y_addEdge(s,t,w):
  global Gy
  Gy[s][t]=w
def s_addEdge(s,t,w):
  global Gs
  Gs[s][t]=w
def y_solve(s,t):
  global Gy
  fixed = {}
  q = queue.PriorityQueue()
  q.put((0,s))
  while q.empty() == False:
    w,x = q.get()
    if x == t: return w
    if x in fixed: continue;
    fixed[x] = w
    for y in Gy[x]:
      if (y in fixed) == False:
        q.put((w + Gy[x][y], y))
  return None
def s_solve(s,t):
  global Gs
  fixed = {}
  q = queue.PriorityQueue()
  q.put((0,s))
  while q.empty() == False:
    w,x = q.get()
    if x == t: return w
    if x in fixed: continue;
    fixed[x] = w
    for y in Gs[x]:
      if (y in fixed) == False:
        q.put((w + Gs[x][y], y))
  return None

n, m, s, t = map(int,input().split())
y_setNode(n)
s_setNode(n)
for i in range(m):
	u,v,a,b = map(int,input().split())
	Gy[u-1][v-1] = a
	Gy[v-1][u-1] = a
	Gs[u-1][v-1] = b
	Gs[v-1][u-1] = b

#
d = [0 for i in range(n)]
cur = 10**15
for i in range(n):
	tmp = y_solve(s-1,n-(i+1)) + s_solve(t-1,n-(i+1))
	if cur >= tmp:
		cur = tmp
	d[i] = 10**15-cur

for i in range(n):
	print(d[n-(i+1)])

Submission status: Time Limit Exceeded

Solution code:

from heapq import *
from collections import defaultdict

def Dijkstra(s, V, E):
    # https://ja.wikipedia.org/wiki/%E3%83%80%E3%82%A4%E3%82%AF%E3%82%B9%E3%83%88%E3%83%A9%E6%B3%95
    d = defaultdict(lambda:10**20)
    d[s] = 0
    Q = []
    for v in V:
        heappush(Q, (d[v], v))
    while Q:
        x, u = heappop(Q)
        for v, y in E[u].items():
            alt = d[u] + y
            if d[v] > alt:
                d[v] = alt
                heappush(Q, (alt, v))
    return d

N, M, S, T = [int(_) for _ in input().split()]
UVAB = [[int(_) for _ in input().split()] for i in range(M)]

Ea = defaultdict(dict)
Eb = defaultdict(dict)

for u, v, a, b in UVAB:
    Ea[u][v] = a
    Ea[v][u] = a
    Eb[u][v] = b
    Eb[v][u] = b
    
V = list(range(1, N + 1))

Da = Dijkstra(S, V, Ea)
Db = Dijkstra(T, V, Eb)

T = [None] * (N + 1)
t = 10**30

for i in range(N, 0, -1):
    r = Da[i] + Db[i]
    t = min(t, r)
    T[i] = t

ST = 10**15

for i in range(1, N + 1):
    print(ST-T[i])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(n, m, s, t, UVAB):
    g = defaultdict(dict)
    for u, v, a, b in UVAB:
        g[u][v] = (a, b)
        g[v][u] = (a, b)

    def find(i):
        c = 10**15
        def d(s, ck):
            dist = [0 if s == i else sys.maxsize for i in range(n+1)]
            # p = [None for i in range(n+1)]
            q =[]
            heapq.heappush(q, (dist[s], s))
            while q:
                __, u = heapq.heappop(q)
                for v, cost in g[u].items():
                    alt = dist[u] + cost[ck]
                    if dist[v] > alt:
                        dist[v] = alt
                        heapq.heappush(q, (alt, v))
            return dist

        dist0 = d(s, 0)
        costs = []
        # print('--')
        for j in range(i+1, n+1):
            costs.append(d(j, 1)[t] + dist0[j])
        #     print( d(j, 1), d(j, 1)[t],dist0[j], t)
        # print(costs)
        return c - min(costs)
    ans = []
    for i in range(n):
        ans.append(find(i))

    
    return '\n'.join(map(str, ans))


def main():
    n, m, s, t = read_int_n()
    UVAB = [read_int_n() for _ in range(m)]

    
    print(slv(n, m, s, t, UVAB))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

from heapq import *
from collections import defaultdict

def Dijkstra(s, V, E):
    # https://ja.wikipedia.org/wiki/%E3%83%80%E3%82%A4%E3%82%AF%E3%82%B9%E3%83%88%E3%83%A9%E6%B3%95
    d = defaultdict(lambda:10**20)
    prev = defaultdict(lambda:None)
    d[s] = 0
    Q = []
    for v in V:
        heappush(Q, (d[v], v))
    while Q:
        x, u = heappop(Q)
        for v, y in E[u].items():
            alt = d[u] + y
            if d[v] > alt:
                d[v] = alt
                prev[v] = u
                heappush(Q, (alt, v))
    return d, prev

N, M, S, T = [int(_) for _ in input().split()]
UVAB = [[int(_) for _ in input().split()] for i in range(M)]

Ea = defaultdict(dict)
Eb = defaultdict(dict)

for u, v, a, b in UVAB:
    Ea[u][v] = a
    Ea[v][u] = a
    Eb[u][v] = b
    Eb[v][u] = b
    
V = list(range(1, N + 1))

Da = Dijkstra(S, V, Ea)[0]
Db = Dijkstra(T, V, Eb)[0]

T = [None] * (N + 1)
t = 10**30

for i in range(N, 0, -1):
    r = Da[i] + Db[i]
    t = min(t, r)
    T[i] = t

ST = 10**15

for i in range(1, N + 1):
    print(ST-T[i])

Submission status: Time Limit Exceeded

Solution code:
# encoding:utf-8
from collections import defaultdict

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

	cost_yen = defaultdict(lambda: 10 ** 10)
	cost_snook = defaultdict(lambda: 10 ** 10)
	for train in trains:
		cost_yen[(train[0]-1, train[1]-1)] = train[2]
		cost_yen[(train[1]-1, train[0]-1)] = train[2]
		cost_snook[(train[0]-1, train[1]-1)] = train[3]
		cost_snook[(train[1]-1, train[0]-1)] = train[3]

	d_yen = calc_distanc(cost_yen, s-1, n)
	d_snook = calc_distanc(cost_snook, t-1, n)

	max_year = -1
	for year in range(0, n):
		if max_year >= year:
			print(tmp_max)
		else:
			tmp_max = 0
			for i in range(year, n):
				if 10 ** 15 - d_yen[i] - d_snook[i] > tmp_max:
					tmp_max = 10 ** 15 - d_yen[i] - d_snook[i]
					max_year = i
			print(tmp_max)

def calc_distanc(cost, frm, n):
	d = defaultdict(lambda: 10 ** 10)

	for i in range(n):
		d[i] = cost[(i, frm)]

	d[frm] = 0
	searched_node = [frm]

	while True:
		tmp_node = -1
		for v in range(n):
			if v not in searched_node:
				if tmp_node == -1:
					tmp_node = v
				elif d[v] < d[tmp_node]:
					tmp_node = v
		
		if tmp_node == -1:
			break

		searched_node.append(tmp_node)

		for i in range(n):
			d[i] = min(d[i], d[tmp_node] + cost[(i, tmp_node)])

	return d

	


if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
n, m, s, t = map(int, input().split())
E = [[] for i in range(n)]
for i in range(m):
  u, v, a, b = map(int, input().split())
  E[u - 1].append([v - 1, a, b])
  E[v - 1].append([u - 1, a, b])
A = [[10 ** 15, 0, i] for i in range(n)]
q_a = [a for a in A if (a[1] == 0)]
A[s - 1][0] = 0
while q_a:
  s_a = sorted(q_a, key=lambda x: x[0])[0][2]
  A[s_a][1] = 1
  for e in E[s_a]:
    if A[e[0]][1] == 0:
      A[e[0]][0] = min(A[s_a][0] + e[1], A[e[0]][0])
  q_a = [a for a in A if (a[1] == 0)]
B = [[10 ** 15, 0, i] for i in range(n)]
q_b = [b for b in B if (b[1] == 0)]
B[t - 1][0] = 0
while q_b:
  s_b = sorted(q_b, key=lambda x: x[0])[0][2]
  B[s_b][1] = 1
  for e in E[s_b]:
    if B[e[0]][1] == 0:
      B[e[0]][0] = min(B[s_b][0] + e[2], B[e[0]][0])
  q_b = [b for b in B if (b[1] == 0)]
C = [A[i][0] + B[i][0] for i in range(n)]
for i in range(n):
  print(10 ** 15 - min(C[i:]))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(n, m, s, t, UVAB):
    g = defaultdict(dict)
    for u, v, a, b in UVAB:
        g[u][v] = (a, b)
        g[v][u] = (a, b)

    def find(i):
        c = 10**15
        def d(s, ck):
            dist = [0 if s == i else sys.maxsize for i in range(n+1)]
            # p = [None for i in range(n+1)]
            q =[]
            heapq.heappush(q, (dist[s], s))
            while q:
                __, u = heapq.heappop(q)
                for v, cost in g[u].items():
                    alt = dist[u] + cost[ck]
                    if dist[v] > alt:
                        dist[v] = alt
                        # p[v] = u
                        heapq.heappush(q, (dist[u], v))
            return dist

        dist0 = d(s, 0)
        costs = []
        # print('--')
        for j in range(i+1, n+1):
            costs.append(d(j, 1)[t] + dist0[j])
        #     print( d(j, 1), d(j, 1)[t],dist0[j], t)
        # print(costs)
        return c - min(costs)
    ans = []
    for i in range(n):
        ans.append(find(i))

    
    return '\n'.join(map(str, ans))


def main():
    n, m, s, t = read_int_n()
    UVAB = [read_int_n() for _ in range(m)]

    
    print(slv(n, m, s, t, UVAB))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import queue

G1 = [{}]
G2 = [{}]
COST =  [0.0 for i in range(100000)]
def setNode(n):
  global G1,G2
  G1 = [{} for i in range(n)]
  G2 = [{} for i in range(n)]
def addEdge(s,t,w):
  global G1
  G1[s][t]=w
def solve(s,t):
  global G1
  fixed = {}
  q = queue.PriorityQueue()
  q.put((0,s))
  while q.empty() == False:
    w,x = q.get()
    if x == t: return w
    if x in fixed: continue;
    fixed[x] = w
    for y in G1[x]:
      if (y in fixed) == False:
        q.put((w + G1[x][y], y))
  return None
def solve2(s,t):
  global G2
  fixed = {}
  q = queue.PriorityQueue()
  q.put((0,s))
  while q.empty() == False:
    w,x = q.get()
    if x == t: return w
    if x in fixed: continue;
    fixed[x] = w
    for y in G2[x]:
      if (y in fixed) == False:
        q.put((w + G2[x][y], y))
  return None

n,m,src,dst = map(int,input().split())
setNode(n+1)
for i in range(m):
  s,t,w,w2 = map(int,input().split())
  G1[s][t] = w
  G1[t][s] = w
  G2[s][t] = w2
  G2[t][s] = w2
  
  COST[0] = solve(src,dst)
  	
for i in range(1,n+1):
	COST[i] = 10**15 - solve(src,i)- solve2(i,dst)
for i in range(n):
	print(max(COST[i+1:n+1]))

Submission status: Time Limit Exceeded

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

root1 = []
for i in range(n):
    root1_ = [0] * n
    root1.append(root1_)
root2 = []
for i in range(n):
    root2_ = [0] * n
    root2.append(root2_)
    
for i in range(m):
    root = list(map(int, input().split()))
    root1[root[0] - 1][root[1] - 1] = root[2]
    root1[root[1] - 1][root[0] - 1] = root[2]
    root2[root[0] - 1][root[1] - 1] = root[3]
    root2[root[1] - 1][root[0] - 1] = root[3]

def min_cost(start, end, root):
    confirmed = [[start, 0]]
    while len(confirmed) < n:
        candidate = []
        for i in range(len(confirmed)):
            for j in range(n):
                if root[confirmed[i][0] - 1][j] != 0:
                    candidate.append([j + 1, confirmed[i][1] + root[confirmed[i][0] - 1][j]])
        candidate.sort(key = lambda x: x[1])
        for i in range(len(candidate)):
            if candidate[i][0] in [confirmed[i][0] for i in range(len(confirmed))]:
                continue
            else:
                confirmed.append(candidate[i])
                break       
    for i in range(len(confirmed)):
        if confirmed[i][0] == end:
            return confirmed[i][1]

cost = []
for i in range(n):
    cost1 = min_cost(s, i + 1, root1)
    cost2 = min_cost(i + 1, t, root2)
    cost.append(cost1 + cost2)
for i in range(n):
    new_cost = cost[i:]
    print(10 ** 15 - min(new_cost))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict 
import sys
import heapq

sys.setrecursionlimit(10**8)

#N:頂点数   M:辺数
N,M,s,t = map(int,input().split())


#root[n] -> nからいけるlist
root_yen = defaultdict(set)
root_snu = defaultdict(set)


#cost[a][b] = a -> b のコスト
cost_yen = [[0 for i in range(N+1)] for j in range(N+1)]
cost_snu = [[0 for i in range(N+1)] for j in range(N+1)]


#weight[a] = start -> a のコスト 未探索->-1
weight_yen = [-1 for i in range(N+1)]
weight_snu = [-1 for i in range(N+1)]
weight_yen[s] = 0
weight_snu[t] = 0


#q = 次に探索する(確定する)もの q[0]=[w,n]
q_yen = [[0,s]]
q_snu = [[0,t]]
heapq.heapify(q_yen)
heapq.heapify(q_snu)


for i in range(M):
	u,v,a,b = list(map(int,input().split())) #
	
	root_yen[u].add(v)
	root_yen[v].add(u)
	
	root_snu[u].add(v)
	root_snu[v].add(u)
	
	cost_yen[u][v] = a
	cost_yen[v][u] = a
	cost_snu[u][v] = b
	cost_snu[v][u] = b
	
	


def search_yen (n,w_0): #nから更新 w_0:確定コスト
	global cost_yen
	global weight_yen
	global q_yen
		
	for i in list(root_yen[n]):
		w = w_0 + cost_yen[n][i]
		if weight_yen[i] == -1 or weight_yen[i] > w: #未探索orより小さい
			heapq.heappush(q_yen, [w,i])
			weight_yen[i] = w
			
def search_snu (n,w_0): #nから更新 w_0:確定コスト
	global cost_snu
	global weight_snu
	global q_snu
		
	for i in list(root_snu[n]):
		w = w_0 + cost_snu[n][i]
		if weight_snu[i] == -1 or weight_snu[i] > w: #未探索orより小さい
			heapq.heappush(q_snu, [w,i])
			weight_snu[i] = w			
			

while q_yen:
	w,n = heapq.heappop(q_yen)
	search_yen(n,w)
	
while q_snu:
	w,n = heapq.heappop(q_snu)
	search_snu(n,w)
	

finalans = float('inf')
ans_li = []

for i in range(0,N):
	ans = weight_yen[N-i] + weight_snu[N-i]
	finalans = min(finalans, ans)
	ans_li.append(finalans)
	
ans_li.reverse()
syozikin = 10**15


for i in ans_li:
	print(syozikin - i)