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:
n,m,s,t=map(int,input().split())
TRAIN=[None]*m

for i in range(m):
    TRAIN[i]=list(map(int,input().split()))


YEN=[10**16]*(n+1)#sから国iまで行くときの最小円
SNOOK=[10**16]*(n+1)#国iからtまで行くときの最小スヌーク
YEN[s]=0
SNOOK[t]=0


TRAINMAP=[[] for i in range(n+1)]

for i in range(m):
    TRAINMAP[TRAIN[i][0]]+=[(TRAIN[i][1],TRAIN[i][2],TRAIN[i][3])]
    TRAINMAP[TRAIN[i][1]]+=[(TRAIN[i][0],TRAIN[i][2],TRAIN[i][3])]


checktown=s
checked=set()
alltown=set(list(range(1,n+1)))
checking=set()

while checked != alltown:
    for i in TRAINMAP[checktown]:
        if YEN[i[0]]>YEN[checktown]+i[1]:
            YEN[i[0]]=YEN[checktown]+i[1]
            checking=checking|{i[0]}


    checked=checked|{checktown}
    YENcheck=10**16

    for i in (checking - checked):
        if YENcheck>YEN[i]:
            YENcheck=YEN[i]
            checktown=i




checktown=t
checked=set()
alltown=set(list(range(1,n+1)))
checking=set()

while checked != alltown:
    for i in TRAINMAP[checktown]:
        if SNOOK[i[0]]>SNOOK[checktown]+i[2]:
            SNOOK[i[0]]=SNOOK[checktown]+i[2]
            checking=checking|{i[0]}


    checked=checked|{checktown}
    SNOOKcheck=10**16

    for i in (checking - checked):
        if SNOOKcheck>SNOOK[i]:
            SNOOKcheck=SNOOK[i]
            checktown=i



MONEY=[None]*(n+1)

for i in range(1,n+1):
    MONEY[i]=YEN[i]+SNOOK[i]


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

Submission status: Time Limit Exceeded

Solution code:
def gijkstra(n,E,key=1,s=1):
    T, Q = [[float('inf'), -1] for i in range(n+1)], list(range(1,n+1))
    T[s][0] = 0
    Q.sort(key=lambda x:-T[x][0])
    while Q:
        u = Q.pop()
        for e in E[u]:
            v = e[0]
            d = T[u][0] + e[key]
            if T[v][0] > d:
                T[v] = [d, u]
                Q.sort(key=lambda x:-T[x][0])
    return T

n, m, s, t =  map(int,input().split())
E = [[] for i in range(n+1)]
for i in range(m):
    e = tuple(map(int,input().split()))
    E[e[0]].append(e[1:2]+e[2:])
    E[e[1]].append(e[0:1]+e[2:])
T1 = gijkstra(n,E,key=1,s=s)
T2 = gijkstra(n,E,key=2,s=t)
T = [T1[v][0]+T2[v][0] for v in range(n+1)]
for i in range(n):
    print(10**15 - min(T[i+1:]))

Submission status: Time Limit Exceeded

Solution code:
def gijkstra(n,E,key=1,s=1):
    T, Q = [[float('inf'), -1] for i in range(n+1)], list(range(1,n+1))
    T[s][0] = 0
    while Q:
        u = min(Q, key=lambda x:T[x][0])
        Q.remove(u)
        for e in E[u]:
            v = e[0]
            d = T[u][0] + e[key]
            if T[v][0] > d:
                T[v] = [d, u]
    return T

n, m, s, t =  map(int,input().split())
E = [[] for i in range(n+1)]
for i in range(m):
    e = tuple(map(int,input().split()))
    E[e[0]].append(e[1:2]+e[2:])
    E[e[1]].append(e[0:1]+e[2:])
T1 = gijkstra(n,E,key=1,s=s)
T2 = gijkstra(n,E,key=2,s=t)
T = [T1[v][0]+T2[v][0] for v in range(n+1)]
for i in range(n):
    print(10**15 - min(T[i+1:]))

Submission status: Time Limit Exceeded

Solution code:
import heapq
initial = 10 ** 15

def di(link_costs, s):
    costs = [initial] * n
    costs[s] = 0
    node_list = []
    serched_node = set()
    heapq.heappush(node_list, (0, s))
    
    while(len(node_list) != 0 and len(serched_node) != n):
        index = heapq.heappop(node_list)[1]
        if index in serched_node:
            continue
        serched_node.add(index)
        link = links[index]
        for j in link:
            if j in serched_node:
                continue
        
            cost = link_costs[index][j]
            newcost =  costs[index] + cost
            if newcost < costs[j]:
                costs[j] = newcost
                heapq.heappush(node_list, (newcost, j))
    return costs
    
n, m, s, t  = list(map(int, input().split()))
s -= 1
t -= 1
links = [set() for _ in range(n)]
links_cost_en = [[initial for _ in range(n)] for __ in range(n)]
links_cost_sn = [[initial for _ in range(n)] for __ in range(n)]

for _ in range(m):
    u, v, a, b  = list(map(int, input().split()))
    links[u-1].add(v-1)
    links[v-1].add(u-1)
    links_cost_en[u - 1][v - 1] = a
    links_cost_en[v - 1][u - 1] = a
    links_cost_sn[u - 1][v - 1] = b
    links_cost_sn[v - 1][u - 1] = b

cost_en_from_s = di(links_cost_en, s)
cost_sn_to_t = di(links_cost_sn, t)
cost_list = [cost_en_from_s[i] + cost_sn_to_t[i] for i in range(n)]
 
ans = [initial] * n
ans[-1] = cost_list[-1]
for i in list(range(n - 1))[::-1]:
    ans[i] = min(ans[i + 1], cost_list[i])
for i in range(n):
    print(initial - ans[i])

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush

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

GA = [[] for _ in range(N+1)]
GB = [[] for _ in range(N+1)]

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

costa = [10**16]*(N+1)
costb = [10**16]*(N+1)

costa[S] = 0
costb[T] = 0
Q = [[0, S]]


while Q:
    c, p = heappop(Q)
    if costa[p] < c:
        continue

    for q, a in GA[p]:
        if costa[q] > c+a:
            costa[q] = c+a
            heappush(Q, [c+a, q])

Q = [[0, T]]

while Q:
    c, p = heappop(Q)
    if costb[p] < c:
        continue

    for q, b in GB[p]:
        if costb[q] > c+b:
            costb[q] = c+b
            heappush(Q, [c+b, q])

ans = []
tmp = 10**16

for i in range(N, -1, -1):
    
    tmp = min(tmp, costa[i] + costb[i])
    ans.append(10**15 - tmp)

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

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify, heappush, heappop

class Rail:
  def __init__(self, f, t, y, s, c=0):
    self.from_city = f
    self.to_city = t
    self.yen = y
    self.sunuke = s
    self.cost = c

  def __lt__(self, other):
    return self.cost < other.cost

  def __str__(self):
    return str(self.cost)


N, M, Start, Goal = map(int, input().split())
Start -= 1
Goal -= 1
adj_list = [[] for _ in range(N)]
for i in range(M):
  u, v, yen, sunuke = map(int, input().split())
  u -= 1
  v -= 1
  adj_list[u].append(Rail(u, v, yen, sunuke))
  adj_list[v].append(Rail(v, u, yen, sunuke))

def dijkstra(start, changed):
  res = {}
  r = Rail(start, start, 0, 0)
  q = [r]
  heapify(q)
  visited = {}

  while len(q)>0:
    r = heappop(q)
    now_city = r.to_city
    if visited.get(now_city, False):
      continue
    visited[now_city] = True
    res[now_city] = r.cost

    #print([now_city+1, r.cost])

    for rr in adj_list[now_city]:
      if changed:
        rr.cost = r.cost + rr.sunuke
      else:
        rr.cost = r.cost + rr.yen
        
      heappush(q, rr)

  return res


min_yen_path = dijkstra(Start, False)
min_sunuke_path = dijkstra(Goal, True)

res = []
max_sunuke = 0
for i in reversed(range(N)):
  s = 10**15-min_yen_path[i]-min_sunuke_path[i]
  max_sunuke = max([s, max_sunuke]) 
  res.append(max_sunuke)
  
for i in reversed(res):
  print(i)

Submission status: Time Limit Exceeded

Solution code:

import heapq
dif = 10 ** 6
initial = 10 ** 15

def di(links, s):
    costs = [initial] * n
    costs[s] = 0
    node_list = []
    serched_node = set()
    heapq.heappush(node_list, s)
    while(len(node_list) != 0 and len(serched_node) != n):
        index = heapq.heappop(node_list) % dif
        if index in serched_node:
            continue
        serched_node.add(index)
        link = links[index]
        for j in range(n):
            if j in serched_node or link[j] == -1:
                continue
        
            cost = link[j]
            newcost =  costs[index] + cost
            if newcost < costs[j]:
                costs[j] = newcost
                heapq.heappush(node_list, newcost * dif + j)
    return costs
    
n, m, s, t  = list(map(int, input().split()))
s -= 1
t -= 1
links_en = [[-1 for j in range(n)] for i in range(n)]
links_sn = [[-1 for j in range(n)] for i in range(n)]

for i in range(m):
    u, v, a, b  = list(map(int, input().split()))
    links_en[u - 1][v - 1] = a
    links_en[v - 1][u - 1] = a
    links_sn[v - 1][u - 1] = b
    links_sn[u - 1][v - 1] = b

cost_en_from_s = di(links_en, s)
cost_sn_to_t = di(links_sn, t)

trans = n - 1
costs = [0] * n
for i in range(n - 1, -1, -1):
    if i == n - 1:
        costs[n-1] = cost_en_from_s[n-1] + cost_sn_to_t[n-1]
        continue
    
    newcost = cost_en_from_s[i] + cost_sn_to_t[i]
    if newcost < costs[trans]:
        trans = i
        costs[i] = newcost
        continue
    
    costs[i] = costs[trans]
    
for cost in costs:
    print(initial - cost)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush,heappop
from sys import setrecursionlimit
setrecursionlimit(10**6)
N,M,s,t=map(int,input().split())
table=[[] for i in range(N)]
rtable=[[] for i in range(N)]
for i in range(M):
    u,v,a,b=map(int,input().split())
    u,v=u-1,v-1
    table[u].append([a,v])
    table[v].append([a,u])
    rtable[u].append([b,v])
    rtable[v].append([b,u])
mod=pow(10,15)
def dijk(s,table):
    dij=[]
    heappush(dij,[0,s])
    val=[mod]*N
    val[s]=0
    while len(dij)>0:
        q,x=heappop(dij)
        if val[x]<q:
            continue
        for d,y in table[x]:
            if val[y]>val[x]+d:
                val[y]=val[x]+d
                heappush(dij,[val[y],y])
    return val
val=dijk(s-1,table)
rval=dijk(t-1,rtable)
score=[0]*N
for i in range(N):
    score[i]=mod-(val[i]+rval[i])
amax=[mod]*N
amax[-1]=score[-1]
for i in range(N-2,-1,-1):
    amax[i]=max(amax[i+1],score[i])
for i in range(N):
    print(amax[i])

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush,heappop
from sys import setrecursionlimit
setrecursionlimit(10**6)
N,M,s,t=map(int,input().split())
table=[[] for i in range(N)]
rtable=[[] for i in range(N)]
for i in range(M):
    u,v,a,b=map(int,input().split())
    table[u-1].append([a,v-1])
    table[v-1].append([a,u-1])
    rtable[u-1].append([b,v-1])
    rtable[v-1].append([b,u-1])
mod=pow(10,15)
def dijk(s,table):
    dij=[]
    heappush(dij,[0,s])
    val=[mod]*N
    val[s]=0
    while len(dij)>0:
        q,x=heappop(dij)
        if val[x]<q:
            continue
        for d,y in table[x]:
            if val[y]>val[x]+d:
                val[y]=val[x]+d
                heappush(dij,[val[y],y])
    return val
val=dijk(s-1,table)
rval=dijk(t-1,rtable)
score=[0]*N
for i in range(N):
    score[i]=mod-(val[i]+rval[i])
amax=[mod]*N
amax[-1]=score[-1]
for i in range(N-2,-1,-1):
    amax[i]=max(amax[i+1],score[i])
for i in range(N):
    print(amax[i])

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush,heappop

N,M,s,t=map(int,input().split())
table=[[] for i in range(N)]
rtable=[[] for i in range(N)]
for i in range(M):
    u,v,a,b=map(int,input().split())
    table[u-1].append([a,v-1])
    table[v-1].append([a,u-1])
    rtable[u-1].append([b,v-1])
    rtable[v-1].append([b,u-1])
mod=pow(10,15)
def dijk(s,table):
    dij=[]
    heappush(dij,[0,s])
    val=[mod]*N
    val[s]=0
    while len(dij)>0:
        q,x=heappop(dij)
        if val[x]<q:
            continue
        for d,y in table[x]:
            if val[y]>val[x]+d:
                val[y]=val[x]+d
                heappush(dij,[val[y],y])
    return val
val=dijk(s-1,table)
rval=dijk(t-1,rtable)
score=[0]*N
for i in range(N):
    score[i]=mod-(val[i]+rval[i])
amax=[mod]*N
amax[-1]=score[-1]
for i in range(N-2,-1,-1):
    amax[i]=max(amax[i+1],score[i])
for i in range(N):
    print(amax[i])

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush,heappop

N,M,s,t=map(int,input().split())
table=[[] for i in range(N)]
rtable=[[] for i in range(N)]
for i in range(M):
    u,v,a,b=map(int,input().split())
    table[u-1].append([a,v-1])
    table[v-1].append([a,u-1])
    rtable[u-1].append([b,v-1])
    rtable[v-1].append([b,u-1])
mod=pow(10,15)
def dijk(s,table):
    dij=[]
    heappush(dij,[0,s])
    val=[mod]*N
    val[s]=0
    while dij:
        q,x=heappop(dij)
        if val[x]<q:
            continue
        for d,y in table[x]:
            if val[y]>val[x]+d:
                val[y]=val[x]+d
                heappush(dij,[val[y],y])
    return val
val=dijk(s-1,table)
rval=dijk(t-1,rtable)
score=[0]*N
for i in range(N):
    score[i]=mod-(val[i]+rval[i])
amax=[mod]*N
amax[-1]=score[-1]
for i in range(N-2,-1,-1):
    amax[i]=max(amax[i+1],score[i])
for i in range(N):
    print(amax[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

n, m, s, t = map(int, input().split())
X = [tuple(map(int, input().split())) for _ in range(m)]
y = 10 ** 15


class DijkstraAlgorithm(object):
    def __init__(self, edges, directed=False, start_node=0):
        self.nodes = self.edge_to_node(edges, directed)
        self.nodes[start_node]['cost'] = 0

    def run(self):
        while True:
            # 確定ノードを探索
            doneNode = None
            for node in self.nodes.values():
                if node['done'] or node['cost'] < 0:
                    continue
                if doneNode is None or node['cost'] < doneNode['cost']:
                    doneNode = node
            if doneNode is None:
                break

            doneNode['done'] = True

            # 接続先ノードの情報更新
            for i in range(len(doneNode['edges_to'])):
                to = doneNode['edges_to'][i]
                cost = doneNode['cost'] + doneNode['edges_cost'][i]
                self.nodes[to]['cost'] = min(self.nodes[to]['cost'], cost)

    def shortest_distance(self, goal_node):
        self.run()
        return self.nodes[goal_node]['cost']

    def edge_to_node(self, edges, directed):
        nodes = defaultdict(
            lambda: {'edges_to': [], 'edges_cost': [], 'done': False, 'cost': float('inf')})
        for i, j, k in edges:
            nodes[i]['edges_to'].append(j)
            nodes[i]['edges_cost'].append(k)

            if not directed:
                nodes[j]['edges_to'].append(i)
                nodes[j]['edges_cost'].append(k)
        return nodes


cost = [0] * n

edges = [(u, v, a) for u, v, a, b in X]
da = DijkstraAlgorithm(edges, start_node=s)
for i in range(1, n + 1):
    cost[i - 1] += da.shortest_distance(i)

edges = [(u, v, b) for u, v, a, b in X]
da = DijkstraAlgorithm(edges, start_node=t)
for i in range(1, n + 1):
    cost[i - 1] += da.shortest_distance(i)

for i in range(n):
    print(y - min(cost[i:]))

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush,heappop

N,M,s,t=map(int,input().split())
table=[[] for i in range(N)]
rtable=[[] for i in range(N)]
for i in range(M):
    u,v,a,b=map(int,input().split())
    table[u-1].append([a,v-1])
    table[v-1].append([a,u-1])
    rtable[u-1].append([b,v-1])
    rtable[v-1].append([b,u-1])

def dijk(s,table):
    dij=[]
    heappush(dij,[0,s])
    val=[10**16]*N
    val[s]=0
    while dij:
        q,x=heappop(dij)
        if val[x]<q:
            continue
        for d,y in table[x]:
            if val[y]>val[x]+d:
                val[y]=val[x]+d
                heappush(dij,[val[y],y])
    return val
val=dijk(s-1,table)
rval=dijk(t-1,rtable)
score=[0]*N
mod=pow(10,15)
for i in range(N):
    score[i]=mod-(val[i]+rval[i])
amax=[mod]*N
amax[-1]=score[-1]
for i in range(N-2,-1,-1):
    amax[i]=max(amax[i+1],score[i])
for i in range(N):
    print(amax[i])

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush,heappop

N,M,s,t=map(int,input().split())
table=[[] for i in range(N)]
rtable=[[] for i in range(N)]
for i in range(M):
    u,v,a,b=map(int,input().split())
    table[u-1].append([a,v-1])
    table[v-1].append([a,u-1])
    rtable[u-1].append([b,v-1])
    rtable[v-1].append([b,u-1])
dij=[]
heappush(dij,[0,s-1])
val=[10**16]*N
val[s-1]=0
while dij:
    q,x=heappop(dij)
    if val[x]<q:
        continue
    for d,y in table[x]:
        if val[y]>val[x]+d:
            val[y]=val[x]+d
            heappush(dij,[val[y],y])
rdij=[]
heappush(rdij,[0,t-1])
rval=[10**16]*N
rval[t-1]=0
while rdij:
    q,x=heappop(rdij)
    if rval[x]<q:
        continue
    for d,y in rtable[x]:
        if rval[y]>rval[x]+d:
            rval[y]=rval[x]+d
            heappush(rdij,[rval[y],y])
score=[0]*N
mod=pow(10,15)
for i in range(N):
    score[i]=mod-(val[i]+rval[i])
amax=[mod]*N
amax[-1]=score[-1]
for i in range(N-2,-1,-1):
    amax[i]=max(amax[i+1],score[i])
for i in range(N):
    print(amax[i])

Submission status: Time Limit Exceeded

Solution code:

import heapq
dif = 10 ** 6
initial = 10 ** 15

def di(links, s):
    costs = [initial] * n
    costs[s] = 0
    node_list = []
    serched_node = set()
    heapq.heappush(node_list, s)
    while(node_list != []):
        index = heapq.heappop(node_list) % dif
        if index in serched_node:
            continue
        serched_node.add(index)
        link = links[index]
        for j in range(n):
            if j in serched_node or link[j] == -1:
                continue
        
            cost = link[j]
            newcost =  costs[index] + cost
            if newcost < costs[j]:
                costs[j] = newcost
                heapq.heappush(node_list, newcost * dif + j)
    return costs
    
n, m, s, t  = list(map(int, input().split()))
s -= 1
t -= 1
links_en = [[-1 for j in range(n)] for i in range(n)]
links_sn = [[-1 for j in range(n)] for i in range(n)]

for i in range(m):
    u, v, a, b  = list(map(int, input().split()))
    links_en[u - 1][v - 1] = a
    links_en[v - 1][u - 1] = a
    links_sn[v - 1][u - 1] = b
    links_sn[u - 1][v - 1] = b

cost_en_from_s = di(links_en, s)
cost_sn_to_t = di(links_sn, t)

trans = n - 1
costs = [0] * n
for i in range(n - 1, -1, -1):
    if i == n - 1:
        costs[n-1] = cost_en_from_s[n-1] + cost_sn_to_t[n-1]
        continue
    
    newcost = cost_en_from_s[i] + cost_sn_to_t[i]
    if newcost < costs[trans]:
        trans = i
        costs[i] = newcost
        continue
    
    costs[i] = costs[trans]
    
for cost in costs:
    print(initial - 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]) )
    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:
from collections import defaultdict
from heapq import heappop, heappush

n, m, s, t = map(int, input().split())
c = 10**15
graph = defaultdict(list)
for _ in range(m):
  u, v, a, b = map(int, input().split())
  graph[u].append((v, a, b))
  graph[v].append((u, a, b))

def dijkstra(s, year):
  d = defaultdict(lambda:float("INF"))
  d[(s, 0)] = 0
  q = []
  heappush(q, (0, (s, 0)))

  while len(q):
    #print(q)
    cost, v = heappop(q)
    cur, m = v[0], v[1]
    used = defaultdict(bool)

    if cur==t and m==1:
      return cost
    if used[v]:
      continue
    used[v]=True

    for to, a, b in graph[cur]:
      if cur>year and m==0 and d[(cur, 1)]>cost:
        d[(cur, 1)]=cost
        heappush(q, (cost, (cur, 1)))
      if m == 0:
        if d[(to, 0)]>cost+a:
          d[(to, 0)]=cost+a
          heappush(q, (cost+a, (to, 0)))
      else:
        if d[(to, 1)]>cost+b:
          d[(to, 1)]=cost+b
          heappush(q, (cost+b, (to, 1)))
  
  return d[(t, 1)]

for i in range(n):
  tt = dijkstra(s, i)
  print(c-tt)

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:
# -*- 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:
            c, u = heapq.heappop(q)
            if dist[u] > c:
                continue
            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)
    dist1 = d(t, 1)

    def find(i):
        c = 10**15
        costs = []
        for j in range(i+1, n+1):
            costs.append(dist1[j] + 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:
# coding: utf-8
# Your code here!

import heapq
dif = 10 ** 5

n, m, s, t  = list(map(int, input().split()))
links_en = [[-1 for j in range(n)] for i in range(n)]
links_sn = [[-1 for j in range(n)] for i in range(n)]

for i in range(m):
    u, v, a, b  = list(map(int, input().split()))
    links_en[u - 1][v - 1] = a
    links_en[v - 1][u - 1] = a
    links_sn[v - 1][u - 1] = b
    links_sn[u - 1][v - 1] = b

s -= 1
t -= 1

cost_en_from_s = [10 ** 20] * n
cost_sn_to_t = [10 ** 20] * n

path_en = [-1] * n
path_sn = [-1] * n

cost_en_from_s[s] = 0
node_list = []
serched_node = set()
heapq.heappush(node_list, s)
while(node_list != []):
    index = heapq.heappop(node_list) % dif
    serched_node.add(index)
    link = links_en[index]
    for j in range(n):
        if j in serched_node:
            continue
    
        cost = link[j]
        if cost == -1:
            continue
    
        newcost =  cost_en_from_s[index] + cost
        if newcost < cost_en_from_s[j]:
            cost_en_from_s[j] = newcost
            heapq.heappush(node_list, newcost * dif + j)
            path_en[j] = index    


cost_sn_to_t[t] = 0
node_list = []
serched_node = set()
heapq.heappush(node_list, t)
while(node_list != []):
    index = heapq.heappop(node_list) % dif
    serched_node.add(index)
    link = links_sn[index]
    for j in range(n):
        if j in serched_node:
            continue
    
        cost = link[j]
        if cost == -1:
            continue
    
        newcost =  cost_sn_to_t[index] + cost
        if newcost < cost_sn_to_t[j]:
            cost_sn_to_t[j] = newcost
            heapq.heappush(node_list, newcost * dif + j)
            path_sn[j] = index 
    
trans = n - 1
costs = [0] * n
for i in range(n - 1, -1, -1):
    if i == n - 1:
        costs[n-1] = cost_en_from_s[n-1] + cost_sn_to_t[n-1]
        continue
    
    newcost = cost_en_from_s[i] + cost_sn_to_t[i]
    if newcost < costs[trans]:
        trans = i
        costs[i] = newcost
        continue
    
    costs[i] = costs[trans]
    
for cost in costs:
    print(10**15 - cost)

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)
    dist1 = d(t, 1)

    def find(i):
        c = 10**15
        costs = []
        for j in range(i+1, n+1):
            costs.append(dist1[j] + 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()