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: Wrong Answer

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")
    d = [inf for f in range(num_v)]
    d[start] = 0;
    while True:
        update = False
        for e in edge:
            if d[e[0]] != inf and d[e[1]] > d[e[0]] + e[2]:
                d[e[1]] = d[e[0]] + e[2]
                update = True
        if not update:
            break
    return d
from collections import deque
ans = deque([])
tori = shortest_path(en,n,s-1)
for i in range(n-1,-1,-1):
  kae = shortest_path(su,n,i)[t-1]
  ans.append(kae+tori[i])
sai = float("inf")
for i in range(n):
  kon = ans[i]
  if sai < kon:
    ans[i] = sai
  else:
    sai = kon
moti = 10**15
for i in range(n):
  print(moti-ans[i])

Submission status: Wrong Answer

Solution code:
n, m, s, t = map(int, input().split())
U = []
V = []
A = []
B = []

def sarchR(S, T, U, V, I):
    print(S, T, U, V, I)
    for i in range(m):
        if U[i] == S and i != I:
            if V[i] != t:
                print(1)
                return U[i], sarchR(V[i], t, U, V, i)
            else:
                return t
                
        elif V[i] == S and i != I:
            if U[i] != t:
                print(2)
                return V[i], sarchR(U[i], t, U, V, i)
            else:
                return t
                
        

for i in range(m):
    u, v, a, b = map(int, input().split())
    U.append(u)
    V.append(v)
    A.append(a)
    B.append(b)

print(sarchR(s, t, U, V, -1))

for i in range(m):
    print(U[i], V[i], A[i], B[i])

Submission status: Wrong Answer

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

l = [[] for _ in range(n+1)]
for _ in range(m):
    u, v, a, b = map(int, input().split())
    l[u].append([v, a, b])
    l[v].append([u, a, b])

yen = 10 ** 15

for i in range(n):
    cost = yen

    for _ in range(500):
        tmp_cost = 0
        now = s
        exchanged = 0
        while now != t:
            if now > i and exchanged == 0:
                exchanged = random.randint(0, 1)
            next = random.choice(l[now])

            tmp_cost += next[exchanged+1]
            if tmp_cost > cost:
                break
            now = next[0]

        if now <= i and exchanged == 0:
            continue
        cost = min(cost, tmp_cost)

    print(yen - cost)

Submission status: Wrong Answer

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

l = [[] for _ in range(n+1)]
for _ in range(m):
    u, v, a, b = map(int, input().split())
    l[u].append([v, a, b])
    l[v].append([u, a, b])

yen = 10 ** 15

for i in range(n):
    cost = yen

    for _ in range(1000):
        tmp_cost = 0
        now = s
        exchanged = 0
        while now != t:
            if now > i and exchanged == 0:
                exchanged = random.randint(0, 1)
            next = random.choice(l[now])

            tmp_cost += next[exchanged+1]
            if tmp_cost > cost:
                break
            now = next[0]

        if now <= i and exchanged == 0:
            continue
        cost = min(cost, tmp_cost)

    print(yen - cost)

Submission status: Wrong Answer

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=[None]*(n+1)#sから国iまで行くときの最小円
SNOOK=[None]*(n+1)#国iからtまで行くときの最小スヌーク
YEN[s]=0
SNOOK[t]=0


YENTRAIN=sorted(TRAIN,key=lambda x:x[2])
SNOOKTRAIN=sorted(TRAIN,key=lambda x:x[3])

YENTOWN={s}


i=1
while i!=n:
    for j in YENTRAIN:

        if len({j[0],j[1]} & YENTOWN)==1:
            if j[0] in YENTOWN:
                YEN[j[1]]=YEN[j[0]]+j[2]
                YENTOWN=YENTOWN|{j[1]}

            elif j[1] in YENTOWN:
                YEN[j[0]]=YEN[j[1]]+j[2]
                YENTOWN=YENTOWN|{j[0]}

            break
    #print(YEN,YENTOWN)
    i+=1

SNOOKTOWN={t}

i=1
while i!=n:
    for j in SNOOKTRAIN:
        if len({j[0],j[1]} & SNOOKTOWN)==1:
            if j[0] in SNOOKTOWN:
                SNOOK[j[1]]=SNOOK[j[0]]+j[3]
                SNOOKTOWN=SNOOKTOWN|{j[1]}

            elif j[1] in SNOOKTOWN:
                SNOOK[j[0]]=SNOOK[j[1]]+j[3]
                SNOOKTOWN=SNOOKTOWN|{j[0]}

            break
    i+=1



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: Wrong Answer

Solution code:
from collections import defaultdict
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


def dijkstra(glaph, start, goal,g_size):
    def get_path(start, goal, prev):
        path = []
        now = goal
        path.append(now)
        while True:
            path.append(prev[now])
            if prev[now] == start: break
            now = prev[now]
        path.reverse()
        return path
    #g_size = len(glaph)
    visited = [False] * g_size
    cost = [MAX_VAL] * g_size
    prev = [None] * g_size
    cost[start] = 0
    prev[start] = start
    now = start
    while True:
        min = MAX_VAL
        next = -1
        visited[now] = True
        #for i in range(g_size):
        for i in glaph[now]:
            if visited[i]: continue
            if glaph[now][i]:
                tmp_cost = glaph[now][i] + cost[now]
                if cost[i] > tmp_cost:
                    cost[i] = tmp_cost
                    prev[i] = now
            if min > cost[i]:
                min = cost[i]
                next = i
        if next == -1: break
        now = next

    return cost
    #return [get_path(start, goal, prev), cost[goal]]


jpy_dijk = (dijkstra(jpy_cost,s-1,0,n))
snuke_dijk = (dijkstra(snuke_cost,t-1,0,n))


#ord n
res = []
min_val = MAX_VAL
for i in reversed(range(n)):
    val = jpy_dijk[i]+ snuke_dijk[i]
    min_val=min(min_val,val)
    res.append(min_val)

#ord n
for x in reversed(res):
    print(10**15-  x)

Submission status: Wrong Answer

Solution code:
import scipy.sparse as ss

n,m,s,t = map(int,input().split())
s,t = s-1,t-1
Gs = ss.dok_matrix((n,n),dtype=int)
Gt = ss.dok_matrix((n,n),dtype=int)

for _ in range(m):
  u,v,a,b = map(int,input().split())
  u,v = u-1,v-1
  Gs[u,v] = a
  Gs[v,u] = a
  Gt[u,v] = b
  Gt[v,u] = b

Ds = ss.csgraph.dijkstra(Gs, indices = s)
Dt = ss.csgraph.dijkstra(Gt, indices = t)

D = (Ds+Dt).astype(int)
D = sorted(((cost, i) for i,cost in enumerate(D)), reverse=True)
print(D)
for i in range(n):
  while D[-1][1] < i:
    D.pop()
  print(int(10**15 - D[-1][0]))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
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


def dijkstra(glaph, start, goal,g_size):
    def get_path(start, goal, prev):
        path = []
        now = goal
        path.append(now)
        while True:
            path.append(prev[now])
            if prev[now] == start: break
            now = prev[now]
        path.reverse()
        return path
    #g_size = len(glaph)
    visited = [False] * g_size
    cost = [MAX_VAL] * g_size
    prev = [None] * g_size
    cost[start] = 0
    prev[start] = start
    now = start
    while True:
        min = MAX_VAL
        next = -1
        visited[now] = True
        #for i in range(g_size):
        for i in glaph[now]:
            if visited[i]: continue
            if glaph[now][i]:
                tmp_cost = glaph[now][i] + cost[now]
                if cost[i] > tmp_cost:
                    cost[i] = tmp_cost
                    prev[i] = now
            if min > cost[i]:
                min = cost[i]
                next = i
        if next == -1: break
        now = next

    return cost
    #return [get_path(start, goal, prev), cost[goal]]


jpy_dijk = (dijkstra(jpy_cost,s-1,0,n))
snuke_dijk = (dijkstra(snuke_cost,t-1,0,n))


#ord n
res = []
min_val = 1000000000000
for i in reversed(range(n)):
    val = jpy_dijk[i]+ snuke_dijk[i]
    min_val=min(min_val,val)
    res.append(min_val)

#ord n
for x in reversed(res):
    print(10**15-  x)

Submission status: Wrong Answer

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

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


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


def dijkstra(glaph, start, goal,g_size):
    def get_path(start, goal, prev):
        path = []
        now = goal
        path.append(now)
        while True:
            path.append(prev[now])
            if prev[now] == start: break
            now = prev[now]
        path.reverse()
        return path

    MAX_VAL = 0x1000000000000000
    #g_size = len(glaph)
    visited = [False] * g_size
    cost = [MAX_VAL] * g_size
    prev = [None] * g_size
    cost[start] = 0
    prev[start] = start
    now = start
    while True:
        min = MAX_VAL
        next = -1
        visited[now] = True
        #for i in range(g_size):
        for i in glaph[now]:
            if visited[i]: continue
            if glaph[now][i]:
                tmp_cost = glaph[now][i] + cost[now]
                if cost[i] > tmp_cost:
                    cost[i] = tmp_cost
                    prev[i] = now
            if min > cost[i]:
                min = cost[i]
                next = i
        if next == -1: break
        now = next

    return cost
    #return [get_path(start, goal, prev), cost[goal]]


jpy_dijk = (dijkstra(jpy_cost,s-1,0,n))
snuke_dijk = (dijkstra(snuke_cost,t-1,0,n))


#ord n
res = []
min_val = 1000000000000
for i in reversed(range(n)):
    val = jpy_dijk[i]+ snuke_dijk[i]
    min_val=min(min_val,val)
    res.append(min_val)

#ord n
for x in reversed(res):
    print(10**15-  x)

Submission status: Wrong Answer

Solution code:
import scipy.sparse as ss

n,m,s,t = map(int,input().split())
s,t = s-1,t-1
Gs = ss.dok_matrix((n,n),int)
Gt = ss.dok_matrix((n,n),int)

for _ in range(m):
  u,v,a,b = map(int,input().split())
  u,v = u-1,v-1
  Gs[u,v] = a
  Gs[v,u] = a
  Gt[u,v] = b
  Gt[v,u] = b

Ds = ss.csgraph.dijkstra(Gs, indices = s)
Dt = ss.csgraph.dijkstra(Gt, indices = t)

D = Ds+Dt
D = sorted(((cost, i) for i,cost in enumerate(D)), reverse=True)
print(D)
for i in range(n):
  while D[-1][1] < i:
    D.pop()
  print(int(10**15 - D[-1][0]))

Submission status: Time Limit Exceeded

Solution code:
from networkx import*
(N,M,*S),*t=[map(int,t.split())for t in open(0)]
G=Graph()
for*u,a,b in t:G.add_edge(*u,y=a,s=b)
b=m=10**15
y,s,*r=map(eval(dir()[761]),(G,G),S,(m,m),'ys')
while N:b=min(b,y[N]+s[N]);r+=m-b,;N-=1
print(*r[::-1])

Submission status: Time Limit Exceeded

Solution code:
import networkx as nx

MAX = 10 ** 15
N, M, S, T = map(int, input().split())

G = nx.Graph()
G.add_nodes_from(range(1, N + 1))
for _ in range(M):
    u, v, a, b = map(int, input().split())
    G.add_edge(u, v, yen=a, snuuk=b)

yen_path = nx.single_source_dijkstra_path_length(G, S, weight='yen')
snuuk_path = nx.single_source_dijkstra_path_length(G, T, weight='snuuk')

ans = [MAX] * (N + 1)
for i in range(N, 0, -1):
    ans[i - 1] = min(ans[i], yen_path[i] + snuuk_path[i])
for x in ans[:N]:
    print(MAX - x)

Submission status: Time Limit Exceeded

Solution code:
import heapq
n,m,s,t = map(int, input().split())
edge1 = [list() for _ in range(n)]
edge2 = [list() for _ in range(n)]
for _ in range(m):
    u,v,a,b = map(int, input().split())
    edge1[u-1].append((v-1,a))
    edge2[u-1].append((v-1,b))
    edge1[v-1].append((u-1,a))
    edge2[v-1].append((u-1,b))

def Dijkstra(x,y,edge):
    # x -> y でルートはedge
    memo = [float("inf")]*n
    memo[x] = 0
    hq = [(0,x)]
    heapq.heapify(hq)
    while hq:
        cost,step = heapq.heappop(hq)
        if step == y:
            return memo[step]
        if cost > memo[step]:
            continue
        for nxt, dist in edge[step]:
            if memo[step] + dist < memo[nxt]:
                memo[nxt] = memo[step] + dist
                heapq.heappush(hq,(memo[nxt], nxt))
    return memo[y]

ans = []
M = float("inf")
for i in range(n):
    # 都市 i で両替するとする
    # 都市 s から都市 i までの最短経路　＋　都市 i から都市 t までの最短経路
    C = Dijkstra(s-1, n-1-i, edge1) + Dijkstra(n-1-i, t-1, edge2)
    M = min(M,C)
    ans.append(M)

for j in ans[::-1]:
    print(10**15-j)

Submission status: Time Limit Exceeded

Solution code:
import heapq
n,m,s,t = map(int, input().split())
edge1 = [list() for _ in range(n)]
edge2 = [list() for _ in range(n)]
for _ in range(m):
    u,v,a,b = map(int, input().split())
    edge1[u-1].append((v-1,a))
    edge2[u-1].append((v-1,b))
    edge1[v-1].append((u-1,a))
    edge2[v-1].append((u-1,b))

def Dijkstra(x,y,edge):
    # x -> y でルートはedge
    memo = [float("inf")]*n
    memo[x] = 0
    hq = [(0,x)]
    heapq.heapify(hq)
    while hq:
        cost,step = heapq.heappop(hq)
        # step == y の場合にbreak検討せず
        if cost > memo[step]:
            continue
        for nxt, dist in edge[step]:
            if memo[step] + dist < memo[nxt]:
                memo[nxt] = memo[step] + dist
                heapq.heappush(hq,(memo[nxt], nxt))
    return memo[y]

ans = []
M = float("inf")
for i in range(n):
    # 都市 i で両替するとする
    # 都市 s から都市 i までの最短経路　＋　都市 i から都市 t までの最短経路
    C = Dijkstra(s-1, n-1-i, edge1) + Dijkstra(n-1-i, t-1, edge2)
    M = min(M,C)
    ans.append(M)

for j in ans[::-1]:
    print(10**15-j)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

input = sys.stdin.buffer.readline

N, M, S, T = map(int, input().split())
S -= 1
T -= 1
UVAB = np.array([tuple(map(int, input().split())) for _ in range(M)]).T
UVAB[:2] -= 1

yen_matrix = csr_matrix((UVAB[2], (UVAB[0], UVAB[1])), shape=(N, N))
yen_path = dijkstra(yen_matrix, indices=S, directed=False).astype(int)

snuuk_matrix = csr_matrix((UVAB[3], (UVAB[0], UVAB[1])), shape=(N, N))
snuuk_path = dijkstra(snuuk_matrix, indices=T, directed=False).astype(int)

path = yen_path + snuuk_path
path_acc = np.minimum.accumulate(path[::-1])[::-1]
print(*(10 ** 15 - path_acc), sep='\n')

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

input = sys.stdin.buffer.readline

N, M, S, T = map(int, input().split())
S -= 1
T -= 1
UVAB = np.array([tuple(map(int, input().split())) for _ in range(M)])
UVAB[:, :2] -= 1

yen_matrix = csr_matrix((UVAB[:, 2], (UVAB[:, 0], UVAB[:, 1])), shape=(N, N))
yen_path = dijkstra(yen_matrix, indices=S, directed=False).astype(int)

snuke_matrix = csr_matrix((UVAB[:, 3], (UVAB[:, 0], UVAB[:, 1])), shape=(N, N))
snuke_path = dijkstra(snuke_matrix, indices=T, directed=False).astype(int)

path = yen_path + snuke_path
path_acc = np.minimum.accumulate(path[::-1])[::-1]
print(*(10 ** 15 - path_acc), sep='\n')

Submission status: Time Limit Exceeded

Solution code:
n,m,s,t=map(int,input().split())
yen=[[]*n for i in range(n)]
sunuke=[[]*n for i in range(n)]
for i in range(m):
  u,v,a,b=map(int,input().split())
  yen[u-1].append((a,v-1))
  yen[v-1].append((a,u-1))
  sunuke[u-1].append((b,v-1))
  sunuke[v-1].append((b,u-1))
  


#ダイクストラ法
#n:頂点数　s:始点　es:隣接リスト表現
import heapq
def dijkstra(n,s,es):
  d=[float("INF")]*n
  d[s]=0
  used=[False]*n
  used[s]=True
  edgelist=[]
  for to in es[s]:
    heapq.heappush(edgelist,to)
  while len(edgelist)>0:
    minedge=heapq.heappop(edgelist)
    v=minedge[1]
    if used[v]:
      continue
    used[v]=True
    d[v]=minedge[0]
    for to in es[v]:
      heapq.heappush(edgelist,(d[v]+to[0],to[1]))
  return d

ans=[0]*n
d_yen=dijkstra(n,s-1,yen)
d_sunuke=dijkstra(n,t-1,sunuke)

for i in range(n):
  ans[i]=d_yen[i]+d_sunuke[i]
  

for j in range(n):
  print(10**15-min(ans[j:]))

Submission status: Time Limit Exceeded

Solution code:
n,m,s,t=map(int,input().split())
yen=[[]*n for i in range(n)]
sunuke=[[]*n for i in range(n)]
for i in range(m):
  u,v,a,b=map(int,input().split())
  yen[u-1].append((a,v-1))
  yen[v-1].append((a,u-1))
  sunuke[u-1].append((b,v-1))
  sunuke[v-1].append((b,u-1))
  


#ダイクストラ法
#n:頂点数　s:始点　es:隣接リスト表現
import heapq
def dijkstra(n,s,es):
  d=[float("INF")]*n
  d[s]=0
  used=[False]*n
  used[s]=True
  edgelist=[]
  for to in es[s]:
    heapq.heappush(edgelist,to)
  while len(edgelist)>0:
    minedge=heapq.heappop(edgelist)
    v=minedge[1]
    if used[v]:
      continue
    used[v]=True
    d[v]=minedge[0]
    for to in es[v]:
      heapq.heappush(edgelist,(d[v]+to[0],to[1]))
  return d

ans=[0]*n
d_yen=dijkstra(n,s-1,yen)
d_sunuke=dijkstra(n,t-1,sunuke)
for i in range(n):
  ans[i]=d_yen[i]+d_sunuke[i]
  

for j in range(n):
  print(10**15-min(ans[j:]))

Submission status: Time Limit Exceeded

Solution code:
n,m,s,t=map(int,input().split())
yen=[[]*n for i in range(n)]
sunuke=[[]*n for i in range(n)]
for i in range(m):
  u,v,a,b=map(int,input().split())
  yen[u-1].append((a,v-1))
  yen[v-1].append((a,u-1))
  sunuke[u-1].append((b,v-1))
  sunuke[v-1].append((b,u-1))


#ダイクストラ法
#n:頂点数　s:始点　es:隣接リスト表現
import heapq
def dijkstra(n,s,es):
  d=[float("INF")]*n
  d[s]=0
  used=[False]*n
  used[s]=True
  edgelist=[]
  for to in es[s]:
    heapq.heappush(edgelist,to)
  while len(edgelist)>0:
    minedge=heapq.heappop(edgelist)
    v=minedge[1]
    if used[v]:
      continue
    used[v]=True
    d[v]=minedge[0]
    for to in es[v]:
      heapq.heappush(edgelist,(d[v]+to[0],to[1]))
  return d

ans=[0]*n
d_yen=dijkstra(n,s-1,yen)
d_sunuke=dijkstra(n,t-1,sunuke)
for i in range(n):
  ans[i]=d_yen[i]+d_sunuke[i]

for j in range(n):
  print(10**15-min(ans[j:n]))

Submission status: Time Limit Exceeded

Solution code:
n,m,s,t=map(int,input().split())
yen=[[]*n for i in range(n)]
sunuke=[[]*n for i in range(n)]
for i in range(m):
  u,v,a,b=map(int,input().split())
  yen[u-1].append((a,v-1))
  yen[v-1].append((a,u-1))
  sunuke[u-1].append((b,v-1))
  sunuke[v-1].append((b,u-1))


#ダイクストラ法
#n:頂点数　s:始点　es:隣接リスト表現
import heapq
def dijkstra(n,s,es):
  d=[float("INF")]*n
  d[s]=0
  used=[False]*n
  used[s]=True
  edgelist=[]
  for to in es[s]:
    heapq.heappush(edgelist,to)
  while len(edgelist)>0:
    minedge=heapq.heappop(edgelist)
    v=minedge[1]
    if used[v]:
      continue
    used[v]=True
    d[v]=minedge[0]
    for to in es[v]:
      heapq.heappush(edgelist,(d[v]+to[0],to[1]))
  return d

ans=[]
d_yen=dijkstra(n,s-1,yen)
d_sunuke=dijkstra(n,t-1,sunuke)
for i in range(n):
  ans.append(d_yen[i]+d_sunuke[i])

for j in range(n):
  print(10**15-min(ans[j:n]))

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop

n,m,s,t = map(int,input().split())
e = [[] for i in range(n+1)]
for i in range(m):
    u,v,a,b = map(int,input().split())
    e[u].append((v,a,b))
    e[v].append((u,a,b))

S = [float("INF")]*(n+1)
S[s] = 0
h = []
heappush(h,[s,0])
while h:
    now,d = heappop(h)
    for nex,a,b in e[now]:
        if d+a < S[nex]:
            S[nex] = d+a
            heappush(h,[nex,d+a])
T = [float("INF")]*(n+1)
T[t] = 0
h = []
heappush(h,[t,0])
while h:
    now,d = heappop(h)
    for nex,a,b in e[now]:
        if d+b < T[nex]:
            T[nex] = d+b
            heappush(h,[nex,d+b])

ans = [0]*(n+1)
cost = 10**15
now = 0
for i in range(n,0,-1):
    now = max(now,cost-S[i]-T[i])
    ans[i] = now
for i in ans[1:]:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

import heapq


class PriorityQueue:
    class Reverse:
        def __init__(self, val):
            self.val = val

        def __lt__(self, other):
            return self.val > other.val

        def __repr__(self):
            return repr(self.val)

    def __init__(self, x=None, desc=False):
        if not x:
            x = []
        if desc:
            for i in range(len(x)):
                x[i] = self.Reverse(x[i])
        self._desc = desc
        self._container = x
        heapq.heapify(self._container)

    @property
    def is_empty(self):
        return not self._container

    def pop(self):
        if self._desc:
            return heapq.heappop(self._container).val
        else:
            return heapq.heappop(self._container)

    def push(self, item):
        if self._desc:
            heapq.heappush(self._container, self.Reverse(item))
        else:
            heapq.heappush(self._container, item)

    def top(self):
        if self._desc:
            return self._container[0].val
        else:
            return self._container[0]

    def sum(self):
        return sum(self._container)

    def __len__(self):
        return len(self._container)


def main():
    from collections import defaultdict
    n, m, s, t = map(int, readline().split())

    edge = defaultdict(list)

    for _ in range(m):
        u, v, a, b = map(int, readline().split())
        edge[u].append((v, a, b))
        edge[v].append((u, a, b))

    dist_s = defaultdict(lambda: float("INF"))
    dist_t = defaultdict(lambda: float("INF"))

    dist_s[s] = 0
    dist_t[t] = 0

    pq = PriorityQueue()
    pq.push((s, 0))

    while pq:
        cur, cost = pq.pop()
        for nx, a, _ in edge[cur]:
            nc = cost + a
            if nc < dist_s[nx]:
                dist_s[nx] = nc
                pq.push((nx, nc))

    pq.push((t, 0))
    while pq:
        cur, cost = pq.pop()
        for nx, _, b in edge[cur]:
            nc = cost + b
            if nc < dist_t[nx]:
                dist_t[nx] = nc
                pq.push((nx, nc))

    res = [0] * (n + 1)
    for i in range(n - 1, -1, -1):
        res[i] = max(res[i + 1], 10 ** 15 - (dist_s[i+1] + dist_t[i+1]))

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys


def solve(n: int, m: int, s: int, t: int, u: "List[int]", v: "List[int]", a: "List[int]", b: "List[int]"):
    import numpy as np
    from scipy.sparse import coo_matrix
    from scipy.sparse.csgraph import dijkstra, shortest_path
    from itertools import accumulate
    ymat = shortest_path(coo_matrix((a, (u, v)), shape=(n+1, n+1), dtype=np.int64), indices=s, directed=False)    
    # ymat = dijkstra(coo_matrix((a, (u, v)), shape=(n+1, n+1), dtype=np.int64), indices=s, directed=False)
    smat = shortest_path(coo_matrix((b, (u, v)), shape=(n+1, n+1), dtype=np.int64), indices=t, directed=False)        
    # smat = dijkstra(coo_matrix((b, (u, v)), shape=(n+1, n+1), dtype=np.int64), indices=t, directed=False)
    acc = list(accumulate(map(int, (ymat+smat)[-1:0:-1].tolist()), min))
    return (10 ** 15 - a for a in reversed(acc))

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    n = int(next(tokens))  # type: int
    m = int(next(tokens))  # type: int
    s = int(next(tokens))  # type: int
    t = int(next(tokens))  # type: int
    u = [int()] * (m)  # type: "List[int]"
    v = [int()] * (m)  # type: "List[int]"
    a = [int()] * (m)  # type: "List[int]"
    b = [int()] * (m)  # type: "List[int]"
    for i in range(m):
        u[i] = int(next(tokens))
        v[i] = int(next(tokens))
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    print(*solve(n, m, s, t, u, v, a, b), sep="\n")

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys


def solve(n: int, m: int, s: int, t: int, u: "List[int]", v: "List[int]", a: "List[int]", b: "List[int]"):
    import numpy as np
    from scipy.sparse import coo_matrix
    from scipy.sparse.csgraph import dijkstra
    from itertools import accumulate
    u, v, a, b = u + v, v + u, a + a, b + b
    ymat = dijkstra(coo_matrix((a, (u, v)), shape=(n+1, n+1), dtype=np.int64), indices=s, directed=True)
    smat = dijkstra(coo_matrix((b, (u, v)), shape=(n+1, n+1), dtype=np.int64), indices=t, directed=True)    
    acc = list(accumulate(map(int, (ymat+smat)[-1:0:-1].tolist()), min))
    return (10 ** 15 - a for a in reversed(acc))

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    n = int(next(tokens))  # type: int
    m = int(next(tokens))  # type: int
    s = int(next(tokens))  # type: int
    t = int(next(tokens))  # type: int
    u = [int()] * (m)  # type: "List[int]"
    v = [int()] * (m)  # type: "List[int]"
    a = [int()] * (m)  # type: "List[int]"
    b = [int()] * (m)  # type: "List[int]"
    for i in range(m):
        u[i] = int(next(tokens))
        v[i] = int(next(tokens))
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    print(*solve(n, m, s, t, u, v, a, b), sep="\n")

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys


def solve(n: int, m: int, s: int, t: int, u: "List[int]", v: "List[int]", a: "List[int]", b: "List[int]"):
    import numpy as np
    from scipy.sparse import coo_matrix
    from scipy.sparse.csgraph import dijkstra
    from itertools import accumulate
    ymat = dijkstra(coo_matrix((a, (u, v)), shape=(n+1, n+1), dtype=np.int64), indices=s, directed=False)
    smat = dijkstra(coo_matrix((b, (u, v)), shape=(n+1, n+1), dtype=np.int64), indices=t, directed=False)    
    acc = list(accumulate(map(int, (ymat+smat)[-1:0:-1].tolist()), min))
    return (10 ** 15 - a for a in reversed(acc))

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    n = int(next(tokens))  # type: int
    m = int(next(tokens))  # type: int
    s = int(next(tokens))  # type: int
    t = int(next(tokens))  # type: int
    u = [int()] * (m)  # type: "List[int]"
    v = [int()] * (m)  # type: "List[int]"
    a = [int()] * (m)  # type: "List[int]"
    b = [int()] * (m)  # type: "List[int]"
    for i in range(m):
        u[i] = int(next(tokens))
        v[i] = int(next(tokens))
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    print(*solve(n, m, s, t, u, v, a, b), sep="\n")

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()