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

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

class Dijkstra:
    def dijkstra(self, adj, start, goal=None):

        num = N  # グラフのノード数
        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

        for i in range(num-1):
            prov_cost, src = heapq.heappop(q)  # pop

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

            # 他の頂点の探索
            for dest, cost in adj[src].items():
                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")))


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:
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]]
    edge = [start]
    while len(confirmed) < n:
        candidate = []
        for i in range(len(edge)):
            for j in range(n):
                if root[edge[i] - 1][j] != 0:
                    for k in range(len(confirmed)):
                        if confirmed[k][0] == edge[i]:
                            candidate.append([j + 1, confirmed[k][1] + root[edge[i] - 1][j]])
                            break
        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)):
            edge.append(confirmed[i][0])
        exclude = []
        for i in range(len(edge)):
            flag = True
            for j in range(n):                
                if root[edge[i] - 1][j] != 0 and (j + 1) not in edge:
                    flag = False
                    break
            if flag == True:
                exclude.append(edge[i])
        edge = list(set(edge) - set(exclude))
    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:
import bisect
import heapq

n,m,s,t=[int(x) for x in raw_input().split()]
A=[[] for i in range(n+1)]
B=[[] for i in range(n+1)]
for k in range(m):
    u,v,a,b=[int(x) for x in raw_input().split()]
    A[u].append([v,a])
    A[v].append([u,a])
    B[u].append([v,b])
    B[v].append([u,b])
bignum=1e17
Da=[bignum for x in range(n+1)]
Db=[bignum for x in range(n+1)]
Ca=[0 for i in range(n+1)]
Cb=[0 for i in range(n+1)]

Da[s]=0
Ca[s]=1
tmpset=[(bignum,0)]
tmpp=s
for i in range(n):
    for p in A[tmpp]:
        rfrs=Da[tmpp]+p[1]
        if Da[p[0]] >rfrs:
            Da[p[0]]= rfrs
            bisect.insort(tmpset, (rfrs, p[0]) )
    kk=0
    while(1):
        p=tmpset[kk]
        if Ca[p[1]]==0:
            tmpp=p[1]
            break
        kk+=1
    Ca[tmpp]=1


Db[t]=0
Cb[t]=1
tmpset=[(bignum,0)]
tmpp=t
for i in range(n):
    for p in B[tmpp]:
        rfrs=Db[tmpp]+p[1]
        if Db[p[0]] >rfrs:
            Db[p[0]]= rfrs
            bisect.insort(tmpset, (rfrs, p[0]) )
    kk=0
    while(1):
        p=tmpset[kk]
        if Cb[p[1]]==0:
            tmpp=p[1]
            break
        kk+=1
    Cb[tmpp]=1

D = sorted ( [ (Da[i]+Db[i],i) for i in range(n+1)], key=lambda x:x[0] )
k=0
for i in range(n):
    while D[k][1]<=i:
        k+=1
    print 1000000000000000 - D[k][0]

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_solve(s):
  global Gy
  fixedy = {}
  q = queue.PriorityQueue()
  q.put((0,s))
  while q.empty() == False:
    w,x = q.get()
    if x in fixedy: continue;
    fixedy[x] = w
    for y in Gy[x]:
      if (y in fixedy) == False:
        q.put((w + Gy[x][y], y))
  return fixedy

def s_solve(s):
  global Gs
  fixeds = {}
  if t in fixeds:
    return fixeds[t]
  q = queue.PriorityQueue()
  q.put((0,s))
  while q.empty() == False:
    w,x = q.get()
    if x in fixeds: continue;
    fixeds[x] = w
    for y in Gs[x]:
      if (y in fixeds) == False:
        q.put((w + Gs[x][y], y))
  return fixeds

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
fixedy = y_solve(s-1)
fixeds = s_solve(t-1)

d = [0 for i in range(n)]
cur = 10**15
for i in range(n):
	tmp = fixedy[n-(i+1)] + fixeds[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:
import heapq
from collections import defaultdict

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

V=defaultdict(set)
V2=defaultdict(set)
for i in range(m):
  a,b,c,d=map(int,input().split())
  V[a-1].add((b-1,c))
  V[b-1].add((a-1,c))
  V2[a-1].add((b-1,d))
  V2[b-1].add((a-1,d))

def dijkstra(n,v,dedic):
  d=[float('inf')]*n
  d[v]=0
  
  hq=[(0,v)]
  
  while hq:
    u = heapq.heappop(hq)[1]
    for nv,c in dedic[u]:
      if d[nv]>d[u]+c:
        d[nv]=d[u]+c
        heapq.heappush(hq,(d[u]+c,nv))
        
  return d

ans=dijkstra(N,s-1,V)
ans2=dijkstra(N,t-1,V2)

ans3=[(ans[x]+ans2[x]) for x in range(N)]

for i in range(N):
  print(10**15-min(ans3[i:]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
np.warnings.filterwarnings('ignore')


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

trains = []
for _ in range(m):
  u, v, a_, b_ = map(int, input().split())
  u -= 1
  v -= 1
  trains.append([u, v, a_, b_])
  
for i in range(n):
  yensun = np.zeros((n, 2), dtype=np.int)
  yensun[s, 0] = 1e15
  if s >= i:
    yensun[s, 1] = 1e15
    
  while True:
    new_yensun = yensun.copy()
    
    for train in trains:
      new_yensun[train[0], 0] = max(new_yensun[train[1], 0] - train[2], new_yensun[train[0], 0])
      new_yensun[train[1], 0] = max(new_yensun[train[0], 0] - train[2], new_yensun[train[1], 0])
      new_yensun[train[0], 1] = max(new_yensun[train[1], 1] - train[3], new_yensun[train[0], 1])
      new_yensun[train[1], 1] = max(new_yensun[train[0], 1] - train[3], new_yensun[train[1], 1])
    for n_ in range(i, n):
      new_yensun[n_, 1] = max(new_yensun[n_, 1], new_yensun[n_, 0])
  
    if (new_yensun - yensun).any():
      yensun = new_yensun
    else:
      break
  
  print(yensun[t, 1].astype(np.int))

Submission status: Time Limit Exceeded

Solution code:
import bisect
import heapq

n,m,s,t=[int(x) for x in raw_input().split()]
A=[[] for i in range(n+1)]
B=[[] for i in range(n+1)]
for k in range(m):
    u,v,a,b=[int(x) for x in raw_input().split()]
    A[u].append([v,a])
    A[v].append([u,a])
    B[u].append([v,b])
    B[v].append([u,b])
bignum=1e17
Da=[bignum for x in range(n+1)]
Db=[bignum for x in range(n+1)]
Ca=[0 for i in range(n+1)]
Cb=[0 for i in range(n+1)]

Da[s]=0
Ca[s]=1
tmpset=[(bignum,0)]
tmpp=s
for i in range(n):
    for p in A[tmpp]:
        rfrs=Da[tmpp]+p[1]
        if Da[p[0]] >rfrs:
            Da[p[0]]= rfrs
            bisect.insort(tmpset, (rfrs, p[0]) )
    while(1):
        p=tmpset.pop(0)
        if Ca[p[1]]==0:
            tmpp=p[1]
            break
    Ca[tmpp]=1


Db[t]=0
Cb[t]=1
tmpset=[(bignum,0)]
tmpp=t
for i in range(n):
    for p in B[tmpp]:
        rfrs=Db[tmpp]+p[1]
        if Db[p[0]] >rfrs:
            Db[p[0]]= rfrs
            bisect.insort(tmpset, (rfrs, p[0]) )
    while(1):
        p=tmpset.pop(0)
        if Cb[p[1]]==0:
            tmpp=p[1]
            break
    Cb[tmpp]=1

D = sorted ( [ (Da[i]+Db[i],i) for i in range(n+1)], key=lambda x:x[0] )
k=0
for i in range(n):
    while D[k][1]<=i:
        k+=1
    print 1000000000000000 - D[k][0]

Submission status: Time Limit Exceeded

Solution code:
import heapq

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

class Dijkstra:
    def dijkstra(self, adj, start, goal=None):

        num = N  # グラフのノード数
        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

        for i in range(num-1):
            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")))


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 numpy as np
np.warnings.filterwarnings('ignore')

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

trains = []
for _ in range(m):
  u, v, a_, b_ = map(int, input().split())
  u -= 1
  v -= 1
  trains.append([u, v, a_, b_])
  
for i in range(n):
  yensun = np.zeros((n, 2)) - np.inf
  yensun[s, 0] = 1e15
  if s >= i:
    yensun[s, 1] = 1e15
    
  while True:
    new_yensun = yensun.copy()
    
    for train in trains:
      new_yensun[train[0], 0] = max(new_yensun[train[1], 0] - train[2], new_yensun[train[0], 0])
      new_yensun[train[1], 0] = max(new_yensun[train[0], 0] - train[2], new_yensun[train[1], 0])
      new_yensun[train[0], 1] = max(new_yensun[train[1], 1] - train[3], new_yensun[train[0], 1])
      new_yensun[train[1], 1] = max(new_yensun[train[0], 1] - train[3], new_yensun[train[1], 1])
    for n_ in range(i, n):
      new_yensun[n_, 1] = max(new_yensun[n_, 1], new_yensun[n_, 0])
  
    if (new_yensun - yensun).any():
      yensun = new_yensun
    else:
      break
  
  print(yensun[t, 1].astype(np.int))

Submission status: Time Limit Exceeded

Solution code:
import bisect
import heapq

n,m,s,t=[int(x) for x in raw_input().split()]
A=[[] for i in range(n+1)]
B=[[] for i in range(n+1)]
for k in range(m):
    u,v,a,b=[int(x) for x in raw_input().split()]
    A[u].append([v,a])
    A[v].append([u,a])
    B[u].append([v,b])
    B[v].append([u,b])
bignum=1e15
Da=[bignum for x in range(n+1)]
Db=[bignum for x in range(n+1)]
Ca=[0 for i in range(n+1)]
Cb=[0 for i in range(n+1)]

Da[s]=0
Ca[s]=1
tmpset=[(bignum,0)]
tmpp=s
for i in range(n):
    for p in A[tmpp]:
        rfrs=Da[tmpp]+p[1]
        if Da[p[0]] >rfrs:
            Da[p[0]]= rfrs
            bisect.insort(tmpset, (rfrs, p[0]) )
    while(1):
        p=tmpset.pop(0)
        if Ca[p[1]]==0:
            tmpp=p[1]
            break
    Ca[tmpp]=1


Db[t]=0
Cb[t]=1
tmpset=[(bignum,0)]
tmpp=t
for i in range(n):
    for p in B[tmpp]:
        rfrs=Db[tmpp]+p[1]
        if Db[p[0]] >rfrs:
            Db[p[0]]= rfrs
            bisect.insort(tmpset, (rfrs, p[0]) )
    while(1):
        p=tmpset.pop(0)
        if Cb[p[1]]==0:
            tmpp=p[1]
            break
    Ca[tmpp]=1

D = sorted ( [ (Da[i]+Db[i],i) for i in range(n+1)], key=lambda x:x[0] )
k=0
for i in range(n):
    while D[k][1]<=i:
        k+=1
    print 1000000000000000 - D[k][0]

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 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, (alt, v))
        return dist

    dist0 = d(s, 0)

    def find(i):
        c = 10**15
        costs = []
        for j in range(i+1, n+1):
            costs.append(d(j, 1)[t] + dist0[j])
        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:
n,m,s,t = map(int,input().split())
u = [0 for i in range(m)]
v = [0 for i in range(m)]
a = [0 for i in range(m)]
b = [0 for i in range(m)]
ys = [10**15 for i in range(n)]
ss = [10**15 for i in range(n)]
for i in range(m):
	u[i],v[i],a[i],b[i] = map(int,input().split())

ys[s-1] = 0
ss[t-1] = 0
flug = 0

for i in range(m**(2*m)):
	yp = ys
	sp = ss
	for j in range(n):
		for k in range(m):
			if u[k] == j+1:
				ys[j] = min(ys[j],ys[v[k]-1]+a[k])
				ss[j] = min(ss[j],ss[v[k]-1]+b[k])
			if v[k] == j+1:
				ys[j] = min(ys[j],ys[u[k]-1]+a[k])
				ss[j] = min(ss[j],ss[u[k]-1]+b[k])
	if yp == ys and sp == ss:
		flug = flug + 1

	if flug == 10:
		break
		

cost = [0 for i in range(n)]

for i in range(n):
	cost[i] = ys[i] + ss[i]

for i in range(n):
	out = 10**15 - min(cost[i:])
	print(out)

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

        for i in range(num-1):
            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:
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(dict)
snuke_cost = defaultdict(dict)


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 = MAX_VAL
    dist = [INF for x in range(n)]
    dist[source] = 0
    PQ = []
    heapq.heappush(PQ, [dist[source], source])

    while (PQ):
        u_dist,u_id = heapq.heappop(PQ)  # u is a tuple [u_dist, u_id]
        if u_dist == dist[u_id]:
            for v in adj[u_id]:
                w_uv = adj[u_id][v]
                if dist[u_id] + w_uv < dist[v]:
                    dist[v] = dist[u_id] + w_uv
                    heapq.heappush(PQ, [dist[v], v])
    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:
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] for i in range(n)]
A[s - 1][0] = 0
q_a = [s - 1]
while q_a:
  s_a = sorted([[A[q][0], q] for q in q_a], key=lambda x: x[0])[0][1]
  q_a.remove(s_a)
  A[s_a][1] = 1
  for e in E[s_a]:
    if A[e[0]][1] == 0:
      if A[s_a][0] + e[1] < A[e[0]][0]:
        A[e[0]][0] = A[s_a][0] + e[1]
        if e[0] not in q_a:
          q_a.append(e[0])
B = [[10 ** 15, 0] for i in range(n)]
B[t - 1][0] = 0
q_b = [t - 1]
while q_b:
  s_b = sorted([[B[q][0], q] for q in q_b], key=lambda x: x[0])[0][1]
  q_b.remove(s_b)
  B[s_b][1] = 1
  for e in E[s_b]:
    if B[e[0]][1] == 0:
      if B[s_b][0] + e[2] < B[e[0]][0]:
        B[e[0]][0] = B[s_b][0] + e[2]
        if e[0] not in q_b:
          q_b.append(e[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:
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 = MAX_VAL
    dist = [INF for x in range(n)]
    dist[source] = 0
    PQ = []
    heapq.heappush(PQ, [dist[source], source])

    while (PQ):
        u_dist,u_id = heapq.heappop(PQ)  # u is a tuple [u_dist, u_id]
        if u_dist == dist[u_id]:
            for v in adj[u_id]:
                w_uv = adj[u_id][v]
                if dist[u_id] + w_uv < dist[v]:
                    dist[v] = dist[u_id] + w_uv
                    heapq.heappush(PQ, [dist[v], v])
    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 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 = MAX_VAL
    dist = [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])

    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 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 = MAX_VAL
    pred = [x for x in range(n)]
    dist = [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:
# 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 = {}
	cost_snook = {}
	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 = {}

	for i in range(n):
		if (i, frm) in cost:
			d[i] = cost[(i, frm)]
		else:
			d[i] = 10 ** 10

	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):
			if (i, tmp_node) in cost:
				d[i] = min(d[i], d[tmp_node] + cost[(i, tmp_node)])

	return d

	


if __name__ == '__main__':
	main()