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())
en = []
su = []
for i in range(m):
    x1,y1,z1,a1=[int(i) for i in input().split()]
    en.append([x1-1,y1-1,z1])
    en.append([y1-1,x1-1,z1])
    su.append([x1-1,y1-1,a1])
    su.append([y1-1,x1-1,a1])
def shortest_path(edge,num_v,start):
    inf = float("inf")
    cost = [[inf for i in range(num_v)] for j in range(num_v)]
    for e in edge: cost[e[0]][e[1]] = e[2]
    d = [inf for j in range(num_v)]
    q = []
    heapq.heappush(q, (0, start))
    d[start] = 0
    syou = inf
    while len(q) != 0:
      prov_cost, src = heapq.heappop(q)
      if prov_cost > syou:
        break
      if d[src] < prov_cost:
                continue
      for dest in range(num_v):
        you = cost[src][dest]
        if you != float('inf') and d[dest] > d[src] + you:
          d[dest] = d[src] + you
          heapq.heappush(q, (d[dest], dest))
          syou = max(d[dest],syou)
    return d


from collections import deque
ans = deque([])
tori = shortest_path(en,n,s-1)
kae = shortest_path(su,n,t-1)
sai = float("inf")
for i in range(n-1,-1,-1):
  kon = kae[i]+tori[i]
  if sai > kon:
     ans.appendleft(kon)
     sai = kon
  else:
    ans.appendleft(sai)
    
moti = 10**15
for i in range(n):
  print(moti-ans[i])

Submission status: Time Limit Exceeded

Solution code:
import heapq as hq

#0 input
INF = 10**16
OKANE = 10**15

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

graph_yen = [[] for _ in range(N+1)]
graph_snk = [[] for _ in range(N+1)]

for i in range(M):
    u, v, a, b = map(int, input().split())
    graph_yen[u].append((v, a))
    graph_yen[v].append((u, a))
    graph_snk[u].append((v, b))
    graph_snk[v].append((u, b))


def dijkstra(st, ryogae, graph):
    dist = [INF]*(N+1)
    hasVisited = [False]*(N+1)
    hasVisited[0] = True
    
    dist[st] = 0
    hasVisited[st] = True
    
    # ryogaeをvisitするまで続く
    cand_list = []
    cr_point = st
    while not hasVisited[ryogae]:
        # 次の候補をheapに入れる
        for neighb in graph[cr_point]:
            if not hasVisited[neighb[0]]:
                cand_list.append([dist[cr_point]+neighb[1], neighb[0]])
            
        #print("cand_list:{}".format(cand_list))
        # 次の候補を確定
        hq.heapify(cand_list)
        while 1:
            next_node = hq.heappop(cand_list)
            if not hasVisited[next_node[1]]:
                break
         
        #print(next_node)
        # distの更新
        cr_point = next_node[1]
        dist[cr_point] = next_node[0]
        hasVisited[cr_point] = True
        
        #print("dist:{}".format(dist))
    
    return dist[ryogae]


min_list = [INF]*(N+1)
for i in range(N-1,-1,-1):
    min_after_i = dijkstra(S,i+1,graph_yen) + dijkstra(T,i+1,graph_snk)
    min_list[i] = min(min_after_i,min_list[i+1])



for i in range(N):
    print(OKANE - min_list[i])

Submission status: Time Limit Exceeded

Solution code:
import heapq
n,m,s,t = map(int,input().split())
en = []
su = []
for i in range(m):
    x1,y1,z1,a1=[int(i) for i in input().split()]
    en.append([x1-1,y1-1,z1])
    en.append([y1-1,x1-1,z1])
    su.append([x1-1,y1-1,a1])
    su.append([y1-1,x1-1,a1])
def shortest_path(edge,num_v,start):
    inf = float("inf")
    cost = [[inf for i in range(num_v)] for j in range(num_v)]
    for e in edge: cost[e[0]][e[1]] = e[2]
    d = [inf for j in range(num_v)]
    q = []
    heapq.heappush(q, (0, start))
    d[start] = 0
    while len(q) != 0:
      prov_cost, src = heapq.heappop(q)
      if d[src] < prov_cost:
                continue
      for dest in range(num_v):
        you = cost[src][dest]
        if you != float('inf') and d[dest] > d[src] + you:
          d[dest] = d[src] + you
          heapq.heappush(q, (d[dest], dest))
    return d


from collections import deque
ans = deque([])
tori = shortest_path(en,n,s-1)
kae = shortest_path(su,n,t-1)
sai = float("inf")
for i in range(n-1,-1,-1):
  kon = kae[i]+tori[i]
  if sai > kon:
     ans.appendleft(kon)
     sai = kon
  else:
    ans.appendleft(sai)
    
moti = 10**15
for i in range(n):
  print(moti-ans[i])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
from heapq import heappop, heappush
from itertools import accumulate


def dijkstra(n, edges, start, *, adj_matrix=False, default_value=float('inf')):

    inf = float('inf')
    costs = [inf] * n
    costs[start] = 0
    pq, rem = [(0, start)], n - 1

    while pq and rem:
        tmp_cost, tmp_node = heappop(pq)
        if costs[tmp_node] < tmp_cost:
            continue
        rem -= 1

        nxt_edges = ((node, cost) for node, cost in enumerate(edges[tmp_node]) if cost != default_value) \
                    if adj_matrix else edges[tmp_node]

        for nxt_node, nxt_cost in nxt_edges:
            new_cost = tmp_cost + nxt_cost
            if costs[nxt_node] > new_cost:
                costs[nxt_node] = new_cost
                heappush(pq, (new_cost, nxt_node))

    return costs


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

# yen_edges = [[] for _ in range(n)]
# snuke_edges = [[] for _ in range(n)]
# for l in sys.stdin.readlines():
#     u, v, yen, snuke = map(int, l.strip().split())
#     yen_edges[u - 1].append((v - 1, yen))
#     yen_edges[v - 1].append((u - 1, yen))
#     snuke_edges[u - 1].append((v - 1, snuke))
#     snuke_edges[v - 1].append((u - 1, snuke))

# yen_costs = dijkstra(n, yen_edges, s - 1)
# snuke_costs = dijkstra(n, snuke_edges, t - 1)

yen_edges = [[float('inf') if __ != _ else 0 for __ in range(n)]
             for _ in range(n)]
snuke_edges = [[float('inf') if __ != _ else 0 for __ in range(n)]
               for _ in range(n)]
for l in sys.stdin.readlines():
    u, v, yen, snuke = map(int, l.strip().split())
    yen_edges[u - 1][v - 1] = yen
    yen_edges[v - 1][u - 1] = yen
    snuke_edges[u - 1][v - 1] = snuke
    snuke_edges[v - 1][u - 1] = snuke

yen_costs = dijkstra(n, yen_edges, s - 1, adj_matrix=True)
snuke_costs = dijkstra(n, snuke_edges, t - 1, adj_matrix=True)

final_costs = list(
    accumulate([yen + snuke
                for yen, snuke in zip(yen_costs, snuke_costs)][::-1],
               min))[::-1]
asset = 10**15
for final_cost in final_costs:
    print(asset - final_cost)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
from heapq import heappop, heappush


def dijkstra(n, edges, start, *, adj_matrix=False, default_value=float('inf')):

    inf = float('inf')
    costs = [inf] * n
    costs[start] = 0
    pq, rem = [(0, start)], n - 1

    while pq and rem:
        tmp_cost, tmp_node = heappop(pq)
        if costs[tmp_node] < tmp_cost:
            continue
        rem -= 1

        nxt_edges = ((node, cost) for node, cost in enumerate(edges[tmp_node]) if cost != default_value) \
                    if adj_matrix else edges[tmp_node]

        for nxt_node, nxt_cost in nxt_edges:
            new_cost = tmp_cost + nxt_cost
            if costs[nxt_node] > new_cost:
                costs[nxt_node] = new_cost
                heappush(pq, (new_cost, nxt_node))

    return costs


# n, m, s, t = map(int, input().split())
# trains = [list(map(int, l.strip().split())) for l in sys.stdin.readlines()]

# yen_edges = [[float('inf') if __ != _ else 0 for __ in range(n)]
#              for _ in range(n)]
# snuke_edges = [[float('inf') if __ != _ else 0 for __ in range(n)]
#                for _ in range(n)]
# for i, j, yen, snuke in trains:
#     yen_edges[i - 1][j - 1] = yen
#     yen_edges[j - 1][i - 1] = yen
#     snuke_edges[i - 1][j - 1] = snuke
#     snuke_edges[j - 1][i - 1] = snuke

# yen_cost = dijkstra(n, yen_edges, s - 1, adj_matrix=True)
# snuke_cost = dijkstra(n, snuke_edges, t - 1, adj_matrix=True)
# costs = [yen + snuke for yen, snuke in zip(yen_cost, snuke_cost)]

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

yen_edges = [[] for _ in range(n)]
snuke_edges = [[] for _ in range(n)]
for l in sys.stdin.readlines():
    u, v, yen, snuke = map(int, l.strip().split())
    yen_edges[u - 1].append((v - 1, yen))
    yen_edges[v - 1].append((u - 1, yen))
    snuke_edges[u - 1].append((v - 1, snuke))
    snuke_edges[v - 1].append((u - 1, snuke))

yen_cost = dijkstra(n, yen_edges, s - 1)
snuke_cost = dijkstra(n, snuke_edges, t - 1)
costs = [yen + snuke for yen, snuke in zip(yen_cost, snuke_cost)]

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
from heapq import heappop, heappush


def dijkstra(n, edges, start, *, adj_matrix=False, default_value=float('inf')):

    inf = float('inf')
    costs = [inf] * n
    costs[start] = 0
    pq, rem = [(0, start)], n - 1

    while pq and rem:
        tmp_cost, tmp_node = heappop(pq)
        if costs[tmp_node] < tmp_cost:
            continue
        rem -= 1

        nxt_edges = ((node, cost) for node, cost in enumerate(edges[tmp_node]) if cost != default_value) \
                    if adj_matrix else edges[tmp_node]

        for nxt_node, nxt_cost in nxt_edges:
            new_cost = tmp_cost + nxt_cost
            if costs[nxt_node] > new_cost:
                costs[nxt_node] = new_cost
                heappush(pq, (new_cost, nxt_node))

    return costs


n, m, s, t = map(int, input().split())
trains = [list(map(int, l.strip().split())) for l in sys.stdin.readlines()]

yen_edges = [[float('inf') if __ != _ else 0 for __ in range(n)]
             for _ in range(n)]
snuke_edges = [[float('inf') if __ != _ else 0 for __ in range(n)]
               for _ in range(n)]
for i, j, yen, snuke in trains:
    yen_edges[i - 1][j - 1] = yen
    yen_edges[j - 1][i - 1] = yen
    snuke_edges[i - 1][j - 1] = snuke
    snuke_edges[j - 1][i - 1] = snuke

yen_cost = dijkstra(n, yen_edges, s - 1, adj_matrix=True)
snuke_cost = dijkstra(n, snuke_edges, t - 1, adj_matrix=True)
costs = [yen + snuke for yen, snuke in zip(yen_cost, snuke_cost)]

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
from heapq import heapify, heappop, heappush
INF = 10**15


def pq_replace(pq, item):
    target_val, target_id = item
    for j, (v, i) in enumerate(pq):
        if i == target_id:
            pq[j] = ((target_val, target_id))
            heapify(pq)
            return


def dijkstra(graph, start=0, inf=INF):

    num = len(graph)
    dists = [inf if node != start else 0 for node in range(num)]
    priority_queue = [(dist, node) for node, dist in zip(range(num), dists)]
    heapify(priority_queue)

    while priority_queue:
        min_dist, min_node = heappop(priority_queue)

        target_edges = graph[min_node]
        for node, dist in enumerate(target_edges):
            if dist != 0:
                dist_from_edge = dists[min_node] + dist
                if dists[node] > dist_from_edge:
                    dists[node] = dist_from_edge
                    pq_replace(priority_queue, (dist_from_edge, node))

    return dists


def fast_dijkstra(graph, start=0, inf=INF):

    num = len(graph)
    dists = [inf if node != start else 0 for node in range(num)]
    priority_queue = [(0, start)]

    for _ in range(num):

        if not priority_queue:
            break

        min_dist, min_node = heappop(priority_queue)

        target_edges = graph[min_node]
        for node, dist in enumerate(target_edges):
            if dist != 0:
                dist_from_edge = dists[min_node] + dist
                if dists[node] > dist_from_edge:
                    dists[node] = dist_from_edge
                    heappush(priority_queue, (dist_from_edge, node))

    return dists


n, m, s, t = map(int, input().split())
trains = [list(map(int, l.strip().split())) for l in sys.stdin.readlines()]
# for l in sys.stdin.readlines():
#     u, v, a, b = map(int, l.strip().split())
#     trains = []
# trains = [list(map(int, input().split())) for i in range(m)]

yen_graph = [[0] * n for _ in range(n)]
snuke_graph = [[0] * n for _ in range(n)]
for i, j, yen, snuke in trains:
    yen_graph[i - 1][j - 1] = yen
    yen_graph[j - 1][i - 1] = yen
    snuke_graph[i - 1][j - 1] = snuke
    snuke_graph[j - 1][i - 1] = snuke

yen_cost = dijkstra(yen_graph, start=s - 1)
snuke_cost = dijkstra(snuke_graph, start=t - 1)
costs = [yen + snuke for yen, snuke in zip(yen_cost, snuke_cost)]

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import heapq
n,m,s,t=list(map(int, input().strip().split()))
links_y=defaultdict(list)
links_s=defaultdict(list)
for i in range(m):
    u,v,a,b=list(map(int, input().strip().split()))
    links_y[u-1].append((v-1,a))
    links_y[v-1].append((u-1,a))
    links_s[u-1].append((v-1,b))
    links_s[v-1].append((u-1,b))

def dijkstra(frm, links):
    dist=[float('inf')]*n
    dist[frm]=0
    Q=[(0,frm)]
    heapq.heapify(Q)
    while Q:
        d,u = heapq.heappop(Q)
        for v,dd in links[u]:
            if dist[v]> d+dd:
                dist[v]=dd+d
                heapq.heappush(Q,(dist[v],v))
    return dist
yen_cost=dijkstra(s-1,links_y)
snk_cost=dijkstra(t-1,links_s)
sumyensnk=[i+j for i,j in zip(yen_cost,snk_cost)]
min_snk=[float('inf')]*n
tmp=float('inf')
for i in range(n)[::-1]:
    min_snk[i] = min(sumyensnk[i],tmp)
    tmp = min_snk[i]
money=10**15
for sumsnk in min_snk:
    print(money-sumsnk)

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

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


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

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




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

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


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

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



MONEY=[10**16]*(n+1)
MONEY[n]=YEN[n]+SNOOK[n]

for i in range(n-1,0,-1):
    if YEN[i]+SNOOK[i]<MONEY[i+1]:
        MONEY[i]=YEN[i]+SNOOK[i]
    else:
        MONEY[i]=MONEY[i+1]


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

Submission status: Time Limit Exceeded

Solution code:
import heapq

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



checking=[(0,s)]

while checking:

    cost,checktown=heapq.heappop(checking)
    
    for i in TRAINMAP[checktown]:
        if YEN[i[0]]>cost+i[1]:
            YEN[i[0]]=cost+i[1]
            heapq.heappush(checking,(cost+i[1],i[0]))

checking=[(0,t)]

while checking:

    cost,checktown=heapq.heappop(checking)
   
    for i in TRAINMAP[checktown]:
        if SNOOK[i[0]]>cost+i[2]:
            SNOOK[i[0]]=cost+i[2]
            heapq.heappush(checking,(cost+i[2],i[0]))



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:
import sys
import heapq
import operator as op

inf = float("inf")

def dijkstra(graph, start):
    dist = [inf for _ in range(len(graph))]
    dist[start] = 0
    prev = [None for _ in range(len(graph))]
    q = [(0, start)]
    rem = len(graph) - 1

    while q != [] and rem > 0:
        du, u = heapq.heappop(q)
        if dist[u] < du:
            continue
        rem -= 1

        for v, d in filter(lambda x: x[1] < inf, enumerate(graph[u])):
            if dist[v] > du + d:
                dist[v] = du + d
                prev[v] = u
                heapq.heappush(q, (dist[v], v))

    return dist, prev

n, m, s, t = map(int, next(sys.stdin).split(" "))

yen_graph = [[inf for _ in range(n)] for _ in range(n)]
snuke_graph = [[inf for _ in range(n)] for _ in range(n)]

for i in range(m):
    u, v, a, b = map(int, next(sys.stdin).split(" "))
    yen_graph[u-1][v-1] = yen_graph[v-1][u-1] = a
    snuke_graph[u-1][v-1] = snuke_graph[v-1][u-1] = b

yen_costs, _ = dijkstra(yen_graph, s-1)
snuke_costs, _ = dijkstra(snuke_graph, t-1)
total_costs = list(map(op.add, yen_costs, snuke_costs))

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from heapq import heapify, heappop, heappush
INF = 10**15


def pq_replace(pq, item):
    target_val, target_id = item
    for j, (v, i) in enumerate(pq):
        if i == target_id:
            pq[j] = ((target_val, target_id))
            heapify(pq)
            return


def dijkstra(graph, start=0, inf=INF):

    num = len(graph)
    dists = [inf if node != start else 0 for node in range(num)]
    priority_queue = [(dist, node) for node, dist in zip(range(num), dists)]
    heapify(priority_queue)

    while priority_queue:
        min_dist, min_node = heappop(priority_queue)

        target_edges = graph[min_node]
        for node, dist in enumerate(target_edges):
            if dist != 0:
                dist_from_edge = dists[min_node] + dist
                if dists[node] > dist_from_edge:
                    dists[node] = dist_from_edge
                    pq_replace(priority_queue, (dist_from_edge, node))

    return dists


def fast_dijkstra(graph, start=0, inf=INF):

    num = len(graph)
    dists = [inf if node != start else 0 for node in range(num)]
    priority_queue = [(0, start)]

    for _ in range(num):

        if not priority_queue:
            break

        min_dist, min_node = heappop(priority_queue)

        target_edges = graph[min_node]
        for node, dist in enumerate(target_edges):
            if dist != 0:
                dist_from_edge = dists[min_node] + dist
                if dists[node] > dist_from_edge:
                    dists[node] = dist_from_edge
                    heappush(priority_queue, (dist_from_edge, node))

    return dists


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

yen_graph = [[0] * n for _ in range(n)]
snuke_graph = [[0] * n for _ in range(n)]
for i, j, yen, snuke in trains:
    yen_graph[i - 1][j - 1] = yen
    yen_graph[j - 1][i - 1] = yen
    snuke_graph[i - 1][j - 1] = snuke
    snuke_graph[j - 1][i - 1] = snuke

yen_cost = dijkstra(yen_graph, start=s - 1)
snuke_cost = dijkstra(snuke_graph, start=t - 1)
costs = [yen + snuke for yen, snuke in zip(yen_cost, snuke_cost)]

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

Submission status: Time Limit Exceeded

Solution code:
from __future__ import print_function
import sys,numpy
from scipy.sparse import*
f=lambda*z:map(int,sys.stdin.readline().split())
v,e,s,t=f();a,b,c,d=zip(*map(f,[0]*e))
x,y=[csgraph.dijkstra(coo_matrix((numpy.array(c,dtype=numpy.float64),(a,b)),[v+1]*2),0,s)for(c,s)in[(c,s),(d,t)]]
r=[0]*(v+1)
for i in xrange(v-1,-1,-1):r[i]=max(r[i+1],10**15-int(x[i+1]+y[i+1]))
r.pop()
print(*r,sep='\n')

Submission status: Time Limit Exceeded

Solution code:
from __future__ import print_function
from cStringIO import StringIO
import sys,numpy
from scipy.sparse import*
f=lambda*z:map(int,sys.stdin.readline().split())
v,e,s,t=f();a,b,c,d=zip(*map(f,[0]*e))
x,y=[csgraph.dijkstra(csr_matrix((c,(a,b)),[v+1]*2),0,s)for(c,s)in[(c,s),(d,t)]]
r=[0]*(v+1)
for i in xrange(v-1,-1,-1):r[i]=max(r[i+1],10**15-int(x[i+1]+y[i+1]))
r.pop()
#print(*r,sep='\n')
buf = StringIO()
for e in r:
	buf.write(str(e))
	buf.write('\n')
sys.stdout.write(buf.getvalue())

Submission status: Time Limit Exceeded

Solution code:
n,m,s,t = map(int,input().split())
en = []
su = []
for i in range(m):
    x1,y1,z1,a1=[int(i) for i in input().split()]
    en.append([x1-1,y1-1,z1])
    en.append([y1-1,x1-1,z1])
    su.append([x1-1,y1-1,a1])
    su.append([y1-1,x1-1,a1])
def shortest_path(edge,num_v,start):
    inf = float("inf")
    cost = [[inf for i in range(num_v)] for j in range(num_v)]
    for e in edge: cost[e[0]][e[1]] = e[2]
    used = [False for i in range(num_v)]
    d = [inf for j in range(num_v)]

    d[start] = 0;
    while True:
        v = -1
        for u in range(num_v):
            if (not used[u]) and (v == -1 or d[u] < d[v]):
                v = u
        if v == -1: break
        used[v] = True
        for x in range(num_v):
            d[x] = d[x] if d[x] < d[v] + cost[v][x] else d[v] + cost[v][x]
    return d

from collections import deque
ans = deque([])
tori = shortest_path(en,n,s-1)
kae = shortest_path(su,n,t-1)
sai = float("inf")
for i in range(n-1,-1,-1):
  kon = kae[i]+tori[i]
  if sai > kon:
     ans.appendleft(kon)
     sai = kon
  else:
    ans.appendleft(sai)
    
moti = 10**15
for i in range(n):
  print(moti-ans[i])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from heapq import heapify, heappop, heappush
INF = 10**15


def pq_replace(pq, item):
    target_val, target_id = item
    for j, (v, i) in enumerate(pq):
        if i == target_id:
            pq.remove((v, i))
            heappush(pq, (target_val, target_id))
            break


def dijkstra(graph, start=0, inf=INF):

    num = len(graph)
    dists = [inf if node != start else 0 for node in range(num)]
    priority_queue = [(dist, node) for node, dist in zip(range(num), dists)]
    heapify(priority_queue)

    while priority_queue:
        min_dist, min_node = heappop(priority_queue)

        target_edges = graph[min_node]
        for node, dist in enumerate(target_edges):
            if dist != 0:
                dist_from_edge = dists[min_node] + dist
                if dists[node] > dist_from_edge:
                    dists[node] = dist_from_edge
                    pq_replace(priority_queue, (dist_from_edge, node))

    return dists


def fast_dijkstra(graph, start=0, inf=INF):

    num = len(graph)
    dists = [inf if node != start else 0 for node in range(num)]
    priority_queue = [(0, start)]

    for _ in range(num):

        if not priority_queue:
            break

        min_dist, min_node = heappop(priority_queue)

        target_edges = graph[min_node]
        for node, dist in enumerate(target_edges):
            if dist != 0:
                dist_from_edge = dists[min_node] + dist
                if dists[node] > dist_from_edge:
                    dists[node] = dist_from_edge
                    heappush(priority_queue, (dist_from_edge, node))

    return dists


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

yen_graph = [[0] * n for _ in range(n)]
snuke_graph = [[0] * n for _ in range(n)]
for i, j, yen, snuke in trains:
    yen_graph[i - 1][j - 1] = yen
    yen_graph[j - 1][i - 1] = yen
    snuke_graph[i - 1][j - 1] = snuke
    snuke_graph[j - 1][i - 1] = snuke

yen_cost = fast_dijkstra(yen_graph, start=s - 1)
snuke_cost = fast_dijkstra(snuke_graph, start=t - 1)
costs = [yen + snuke for yen, snuke in zip(yen_cost, snuke_cost)]

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
import operator as op

def dijkstra(graph, start):
    dist = [float("inf") for _ in range(len(graph))]
    dist[start] = 0
    prev = [None for _ in range(len(graph))]
    q = list(zip(dist, range(len(graph))))
    heapq.heapify(q)

    while q != []:
        du, u = heapq.heappop(q)
        for v, d in filter(lambda x: x[1] < float("inf"), zip(range(len(graph)), graph[u])):
            if dist[v] > du + d:
                dist[v] = du + d
                prev[v] = u
                heapq.heappush(q, (dist[v], v))

    return dist, prev

n, m, s, t = map(int, next(sys.stdin).split(" "))

u = [0 for _ in range(m)]
v = [0 for _ in range(m)]
a = [0 for _ in range(m)]
b = [0 for _ in range(m)]
matrix = [[None for _ in range(n)] for _ in range(n)]

yen_graph = [[float("inf") for _ in range(n)] for _ in range(n)]
snuke_graph = [[float("inf") for _ in range(n)] for _ in range(n)]

for i in range(m):
    u, v, a, b = map(int, next(sys.stdin).split(" "))
    yen_graph[u-1][v-1] = yen_graph[v-1][u-1] = a
    snuke_graph[u-1][v-1] = snuke_graph[v-1][u-1] = b

yen_costs, _ = dijkstra(yen_graph, s-1)
snuke_costs, _ = dijkstra(snuke_graph, t-1)
remain = list(map(op.add, yen_costs, snuke_costs))

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

Submission status: Time Limit Exceeded

Solution code:
from __future__ import print_function
import sys,numpy
from scipy.sparse import*
f=lambda*z:map(int,sys.stdin.readline().split())
v,e,s,t=f();a,b,c,d=zip(*map(f,[0]*e))
x,y=[csgraph.dijkstra(csr_matrix((c,(a,b)),[v+1]*2),0,s)for(c,s)in[(c,s),(d,t)]]
r=[0]*(v+1)
for i in xrange(v-1,-1,-1):r[i]=max(r[i+1],10**15-int(x[i+1]+y[i+1]))
r.pop()
print(*r,sep='\n')

Submission status: Time Limit Exceeded

Solution code:
from __future__ import print_function
import sys,numpy
from scipy.sparse import*
f=lambda*z:map(int,sys.stdin.readline().split())
v,e,s,t=f();a,b,c,d=zip(*map(f,[0]*e))
x,y=[csgraph.dijkstra(csr_matrix((numpy.array(c,dtype=numpy.float64),(a,b)),[v+1]*2),0,s)for(c,s)in[(c,s),(d,t)]]
r=[0]*(v+1)
for i in xrange(v-1,-1,-1):r[i]=max(r[i+1],10**15-int(x[i+1]+y[i+1]))
r.pop()
print(*r,sep='\n')

Submission status: Time Limit Exceeded

Solution code:
import heapq

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=[(0,s)]

while checking:

    checktown=heapq.heappop(checking)[1]
    
    for i in TRAINMAP[checktown]:
        if YEN[i[0]]>YEN[checktown]+i[1]:
            YEN[i[0]]=YEN[checktown]+i[1]
            heapq.heappush(checking,(i[1],i[0]))


    checked=checked|{checktown}
    

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

while checking:

    checktown=heapq.heappop(checking)[1]
   
    for i in TRAINMAP[checktown]:
        if SNOOK[i[0]]>SNOOK[checktown]+i[2]:
            SNOOK[i[0]]=SNOOK[checktown]+i[2]
            heapq.heappush(checking,(i[2],i[0]))

    checked=checked|{checktown}
    


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:
import sys
from scipy.sparse import*
f=lambda*z:map(int,sys.stdin.readline().split())
v,e,s,t=f();a,b,c,d=zip(*map(f,[0]*e))
x,y=[csgraph.dijkstra(csc_matrix((c,(a,b)),[v+1]*2),0,s)for(c,s)in[(c,s),(d,t)]]
r=[10**15]*(v+1)
for i in range(v-1,-1,-1):r[i]=min(r[i+1],int(x[i+1]+y[i+1]))
r.pop()
for e in r:print(10**15-e)

Submission status: Time Limit Exceeded

Solution code:
import sys
from scipy.sparse import*
f=lambda*z:map(int,sys.stdin.readline().split())
v,e,s,t=f();a,b,c,d=zip(*map(f,[0]*e))
x,y=[csgraph.dijkstra(coo_matrix((c,(a,b)),[v+1]*2),0,s)for(c,s)in[(c,s),(d,t)]]
r=[10**15]*(v+1)
for i in range(v-1,-1,-1):r[i]=min(r[i+1],int(x[i+1]+y[i+1]))
r.pop()
for e in r:print(10**15-e)