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 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(csr_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(csr_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:
from scipy.sparse import*
f=lambda*z:map(int,raw_input().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=[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:
# -*- coding: utf-8 -*-
INF = 10**15

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

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

#     while remains:
#         min_index = min(remains, key=lambda x: dists[x])
#         remains.remove(min_index)

#         target_edges = graph[min_index]
#         for index, dist in enumerate(target_edges):
#             if dist != 0:
#                 dist_from_edge = dists[min_index] + dist
#                 if dists[index] > dist_from_edge:
#                     dists[index] = dist_from_edge

#     return dists


def dijkstra(graph, start=0, inf=INF):
    num = len(graph)
    dists = [inf if node != start else 0 for node in range(num)]
    remains = dists[:]

    for _ in range(num):
        min_index = remains.index(min(remains))
        remains[min_index] = inf

        target_edges = graph[min_index]
        for index, dist in enumerate(target_edges):
            if dist != 0:
                dist_from_edge = dists[min_index] + dist
                if dists[index] > dist_from_edge:
                    dists[index] = dist_from_edge
                    remains[index] = dist_from_edge

    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:
import sys
if sys.version_info[0]>=3: raw_input=input

from scipy.sparse import*
f=lambda*z:list(map(int,raw_input().split()))
v,e,s,t=f();a,b,c,d=list(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=[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 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 checked != alltown:

    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 checked != alltown:

    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:
# -*- coding: utf-8 -*-
INF = 10**15


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

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

    while remains:
        min_index = min(remains, key=lambda x: dists[x])
        remains.remove(min_index)

        target_edges = graph[min_index]
        for index, dist in enumerate(target_edges):
            if dist != 0:
                dist_from_edge = dists[min_index] + dist
                if dists[index] > dist_from_edge:
                    dists[index] = dist_from_edge

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

dyen = defaultdict(lambda:float("INF"))
dsnuuk = defaultdict(lambda:float("INF"))
dyen[s] = 0
dsnuuk[t] = 0

def dijkstra(s, m):
  used = defaultdict(bool)
  q = []
  heappush(q, (0, s))

  while len(q):
    v = heappop(q)
    cost, cur = v[0], v[1]

    if used[v]:
      continue
    used[v]=True

    for to, a, b in graph[cur]:
      if m==0 and dyen[to]>cost+a:
        dyen[to] = cost+a
        heappush(q, (cost+a, to))
      elif m==1 and dsnuuk[to]>cost+b:
        dsnuuk[to] = cost+b
        heappush(q, (cost+b, to))

dijkstra(s, 0)
dijkstra(t, 1)

for i in range(n):
  ans = float("INF")
  for j in range(i+1, n+1):
    ans = min(ans, dyen[j]+dsnuuk[j])
  print(c-ans)

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

dyen = defaultdict(lambda:float("INF"))
dsnuuk = defaultdict(lambda:float("INF"))
dyen[s] = 0
dsnuuk[t] = 0

def dijkstra(s, m):
  q = []
  heappush(q, (0, s))

  while len(q):
    cost, cur = heappop(q)
    used = defaultdict(bool)

    if used[v]:
      continue
    used[v]=True

    for to, a, b in graph[cur]:
      if m==0 and dyen[to]>cost+a:
        dyen[to] = cost+a
        heappush(q, (cost+a, to))
      elif m==1 and dsnuuk[to]>cost+b:
        dsnuuk[to] = cost+b
        heappush(q, (cost+b, to))

dijkstra(s, 0)
dijkstra(t, 1)

for i in range(n):
  ans = float("INF")
  for j in range(i+1, n+1):
    ans = min(ans, dyen[j]+dsnuuk[j])
  print(c-ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import heapq

def dijkstra(G, s):
    dist = [float('inf')] * len(G.keys())
    dist[s] = 0
    q = [(dist[v], v) for v in G.keys()]
    heapq.heapify(q)
    while True:
        try:
            _, u = heapq.heappop(q)
        except IndexError:
            break
        for v, d in G[u]:
            tmp = dist[u] + d
            if dist[v] > tmp:
                dist[v] = tmp
                heapq.heappush(q, (tmp, v))
    return dist

n, m, s, t = map(int, input().split())
G1 = defaultdict(list)
G2 = defaultdict(list)

for i in range(m):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    G1[u].append((v, a))
    G1[v].append((u, a))
    G2[u].append((v, b))
    G2[v].append((u, b))

dist1 = dijkstra(G1, s-1)
dist2 = dijkstra(G2, t-1)

mv = 0
ans = []
for i in range(n-1, -1, -1):
    mv = max(mv, 10**15 - dist1[i] - dist2[i])
    ans.append(mv)

ans.reverse()
for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import heapq

def dijkstra(G, s):
    prev = [None] * len(G.keys())
    dist = [float('inf')] * len(G.keys())
    dist[s] = 0
    q = [(dist[v], v) for v in G.keys()]
    heapq.heapify(q)
    while True:
        try:
            _, u = heapq.heappop(q)
        except:
            break
        for v, d in G[u]:
            tmp = dist[u] + d
            if dist[v] > tmp:
                dist[v] = tmp
                prev[v] = u
                heapq.heappush(q, (tmp, v))
    return dist

n, m, s, t = map(int, input().split())
G1 = defaultdict(list)
G2 = defaultdict(list)

for i in range(m):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    G1[u].append((v, a))
    G1[v].append((u, a))
    G2[u].append((v, b))
    G2[v].append((u, b))

dist1 = dijkstra(G1, s-1)
dist2 = dijkstra(G2, t-1)

mv = 0
ans = []
for i in range(n-1, -1, -1):
    mv = max(mv, 10**15 - dist1[i] - dist2[i])
    ans.append(mv)

ans.reverse()
for a in ans:
    print(a)

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])
    su.append([x1-1,y1-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
            elif d[e[1]] != inf and d[e[0]] > d[e[1]] + e[2]:
                d[e[0]] = d[e[1]] + e[2]
                update = True
        if not update:
            break
    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:
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)
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:
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)
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:
from collections import defaultdict
import heapq

def dijkstra(G, s):
    q = []
    heapq.heapify(q)
    prev = [None] * len(G.keys())
    dist = [float('inf')] * len(G.keys())
    dist[s] = 0
    for v in sorted(G.keys()):
        heapq.heappush(q, (dist[v],v))
    while True:
        try:
            _, u = heapq.heappop(q)
        except:
            break
        for v, d in G[u]:
            tmp = dist[u] + d
            if dist[v] > tmp:
                dist[v] = tmp
                prev[v] = u
                heapq.heappush(q, (tmp, v))
    return dist

n, m, s, t = map(int, input().split())
G1 = defaultdict(list)
G2 = defaultdict(list)

for i in range(m):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    G1[u].append((v, a))
    G1[v].append((u, a))
    G2[u].append((v, b))
    G2[v].append((u, b))

dist1 = dijkstra(G1, s-1)
dist2 = dijkstra(G2, t-1)

mv = 0
ans = []
for i in range(n-1, -1, -1):
    mv = max(mv, 10**15 - dist1[i] - dist2[i])
    ans.append(mv)

ans.reverse()
for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from queue import PriorityQueue

def dijkstra(G, s):
    q = PriorityQueue()
    prev = [None] * len(G.keys())
    dist = [float('inf')] * len(G.keys())
    dist[s] = 0
    for v in sorted(G.keys()):
        q.put((dist[v],v))
    while not q.empty():
        _, u = q.get()
        for v, d in G[u]:
            tmp = dist[u] + d
            if dist[v] > tmp:
                dist[v] = tmp
                prev[v] = u
                q.put((tmp, v))
    return dist

n, m, s, t = map(int, input().split())
G1 = defaultdict(list)
G2 = defaultdict(list)

for i in range(m):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    G1[u].append((v, a))
    G1[v].append((u, a))
    G2[u].append((v, b))
    G2[v].append((u, b))

dist1 = dijkstra(G1, s-1)
dist2 = dijkstra(G2, t-1)

mv = 0
ans = []
for i in range(n-1, -1, -1):
    mv = max(mv, 10**15 - dist1[i] - dist2[i])
    ans.append(mv)

ans.reverse()
for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
from collections import defaultdict

n, m, s, t = map(int, input().split())
y = 10**15


class Graph(object):
    def __init__(self):
        self.graph = defaultdict(list)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))


class Dijkstra(object):
    def __init__(self, graph, start):
        self.g = graph.graph

        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    heappush(self.Q, (alt, v))


yen_g = Graph()
sno_g = Graph()
for _ in range(m):
    u, v, a, b = map(int, input().split())
    yen_g.add_edge(u, v, a)
    yen_g.add_edge(v, u, a)
    sno_g.add_edge(u, v, b)
    sno_g.add_edge(v, u, b)

cost = [0] * n
yen_d = Dijkstra(yen_g, s)
sno_d = Dijkstra(sno_g, t)
for i in range(1, n + 1):
    cost[i - 1] = yen_d.dist[i] + sno_d.dist[i]

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

Submission status: Time Limit Exceeded

Solution code:
import heapq
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 Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

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

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0
        self.prev = defaultdict(lambda: None)

        self.Q = []
        heapq.heappush(self.Q, (self.dist[start], start))

        while self.Q:
            dist_u, u = heapq.heappop(self.Q)
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heapq.heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        return self.dist[goal]

    def shortest_path(self, goal):
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]


cost = [0] * n

g = Graph()
for u, v, a, b in X:
    g.add_edge(u, v, a)
    g.add_edge(v, u, a)
d = Dijkstra(g, s)
for i in range(1, n + 1):
    cost[i - 1] += d.shortest_distance(i)

g = Graph()
for u, v, a, b in X:
    g.add_edge(u, v, b)
    g.add_edge(v, u, b)
d = Dijkstra(g, t)
for i in range(1, n + 1):
    cost[i - 1] += d.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, 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([u, v, yen, sunuke])
  adj_list[v].append([v, u, yen, sunuke])

def dijkstra(start, changed):
  res = [ -1 for _ in range(N) ]
  q = [[0, start]]
  visited = {}

  while len(q)>0:
    money, city = heappop(q)
    if res[city]>=0:
      continue
    res[city] = money

    for from_city, to_city, yen, sunuke  in adj_list[city]:
      cost = sunuke if changed else yen
      heappush(q, [money+cost, to_city])
        

  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:
from heapq import heappush, heappop

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([u, v, yen, sunuke])
  adj_list[v].append([v, u, yen, sunuke])

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

  while len(q)>0:
    money, city = heappop(q)
    if city in res:
      continue
    res[city] = money

    for from_city, to_city, yen, sunuke  in adj_list[city]:
      if changed:
        heappush(q, [money+sunuke, to_city])
      else:
        heappush(q, [money+yen, to_city])
        

  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 as hq
from collections import deque
n,m,s,t=map(int,input().split())
yenLinks={}
snkLinks={}
for _ in range(m):
    u,v,a,b=map(int,input().split())
    if u not in yenLinks:
        yenLinks[u]=[(v,a)]
        snkLinks[u]=[(v,b)]
    else:
        yenLinks[u].append((v,a))
        snkLinks[u].append((v,b))
    if v not in yenLinks:
        yenLinks[v]=[(u,a)]
        snkLinks[v]=[(u,b)]
    else:
        yenLinks[v].append((u,a))
        snkLinks[v].append((u,b))
#Dijkstra
INF=100000000000001
for i in range(1,n+1):
    yenDijk=[[INF,0] for _ in range(n+1)] #Distance,Determined index0 never used#
    snkDijk=[[INF,0] for _ in range(n+1)]

#yen route
pQueue=[(0,s)]
yenDijk[s]=[0,0]
hq.heapify(pQueue)

while pQueue:
    d,v = hq.heappop(pQueue)
    if yenDijk[v][1]:
        continue
    else:
        yenDijk[v][1] = 1
    for (w,D) in yenLinks[v]:
        if yenDijk[w][1]:
            continue
        else:
            if yenDijk[w][0]>yenDijk[v][0]+D:
                yenDijk[w][0] = yenDijk[v][0]+D
                hq.heappush(pQueue,(yenDijk[w][0],w))

#snuuk route
pQueue=[(0,t)]
snkDijk[t]=[0,0]
hq.heapify(pQueue)

while pQueue:
    d,v = hq.heappop(pQueue)
    if snkDijk[v][1]:
        continue
    else:
        snkDijk[v][1] = 1
    for (w,D) in snkLinks[v]:
        if snkDijk[w][1]:
            continue
        else:
            if snkDijk[w][0]>snkDijk[v][0]+D:
                snkDijk[w][0] = snkDijk[v][0]+D
                hq.heappush(pQueue,(snkDijk[w][0],w))
#OUTPUT
i = n
ans = INF
answers=[]
while i>0:
    ans = min(ans,yenDijk[i][0]+snkDijk[i][0])
    answers.append(1000000000000000-ans)
    i-=1
answers.reverse()
for ans in answers:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
from collections import defaultdict
def gijkstra(n,E,s=1):
    d = [float('inf')]*(n+1)
    p = [-1]*(n+1)
    hq = [(0,s)]
    d[s] = 0
    while hq:
        u = heapq.heappop(hq)[1]
        for v, c in E[u]:
            if d[v] > d[u] + c:
                d[v], p[v] = d[u]+c, u
                heapq.heappush(hq, (d[u]+c, v))
    return d, p

n, m, s, t =  map(int,input().split())
E1 = defaultdict(set)
E2 = defaultdict(set)

for i in range(m):
    u,v,a,b = tuple(map(int,input().split()))
    E1[u].add((v,a))
    E1[v].add((u,a))
    E2[u].add((v,b))
    E2[v].add((u,b))
d1, _ = gijkstra(n,E1,s=s)
d2, _ = gijkstra(n,E2,s=t)
d = [d1[-1] + d2[-1],]
for i in range(n-1,0,-1):
    d = [min(d[0],d1[i]+d2[i])] + d
[print(10**15-c) for c in d]

Submission status: Time Limit Exceeded

Solution code:
import heapq
from collections import defaultdict
def gijkstra(n,E,key=1,s=1):
    d = [float('inf')]*(n+1)
    d[s] = 0
    hq = [(0,s)]
    while hq:
        u = heapq.heappop(hq)[1]
        for e in E[u]:
            c, v = d[u] + e[key], e[0]
            if d[v] > c:
                d[v] = c
                heapq.heappush(hq,(c,v))
    return d

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

for i in range(m):
    u,v,a,b = tuple(map(int,input().split()))
    E[u].add((v,a,b))
    E[v].add((u,a,b))
d1 = gijkstra(n,E,key=1,s=s)
d2 = gijkstra(n,E,key=2,s=t)
d = [d1[-1] + d2[-1],]
for i in range(n-1,0,-1):
    d = [min(d[0],d1[i]+d2[i])] + d
[print(10**15-c) for c in d]

Submission status: Time Limit Exceeded

Solution code:
import heapq
from collections import defaultdict
def gijkstra(n,E,key=1,s=1):
    d = [float('inf')]*(n+1)
    p = [-1]*(n+1)
    hq = [(0,s)]
    d[s] = 0
    while hq:
        u = heapq.heappop(hq)[1]
        for e in E[u]:
            c, v = d[u] + e[key], e[0]
            if d[v] > c:
                d[v] = c
                p[v] = u
                heapq.heappush(hq,(c,v))
    return d, p

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

for i in range(m):
    u,v,a,b = tuple(map(int,input().split()))
    E[u].add((v,a,b))
    E[v].add((u,a,b))
d1, _ = gijkstra(n,E,key=1,s=s)
d2, _ = gijkstra(n,E,key=2,s=t)
d = [10**15 - d1[-1] -d2[-1]]
for i in range(n-1,0,-1):
    d = [max(d[0], 10**15 - d1[i] -d2[i])] + d
[print(c) for c in d]

Submission status: Time Limit Exceeded

Solution code:
import heapq
from collections import defaultdict
def gijkstra(n,E,key=1,s=1):
    d = [float('inf')]*(n+1)
    p = [-1]*(n+1)
    hq = [(0,s)]
    d[s] = 0
    while hq:
        u = heapq.heappop(hq)[1]
        for e in E[u]:
            c, v = d[u] + e[key], e[0]
            if d[v] > c:
                d[v] = c
                p[v] = u
                heapq.heappush(hq,(c,v))
    return d, p

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

for i in range(m):
    u,v,a,b = tuple(map(int,input().split()))
    E[u].add((v,a,b))
    E[v].add((u,a,b))
d1, _ = gijkstra(n,E,key=1,s=s)
d2, _ = gijkstra(n,E,key=2,s=t)
d = [d1[v]+d2[v] for v in range(n+1)]
for i in range(n):
    print(10**15 - min(d[i+1:]))

Submission status: Time Limit Exceeded

Solution code:
import heapq
from collections import defaultdict
def gijkstra(n,E,key=1,s=1):
    d = {i:float('inf') for i in range(1,n+1)}
    p = {i:-1 for i in range(1,n+1)}
    hq = [(0,s)]
    d[s] = 0
    while hq:
        u = heapq.heappop(hq)[1]
        for e in E[u]:
            c, v = d[u] + e[key], e[0]
            if d[v] > c:
                d[v] = c
                p[v] = u
                heapq.heappush(hq,(c,v))
    return d, p

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

for i in range(m):
    u,v,a,b = tuple(map(int,input().split()))
    E[u].add((v,a,b))
    E[v].add((u,a,b))
d1, _ = gijkstra(n,E,key=1,s=s)
d2, _ = gijkstra(n,E,key=2,s=t)
d = [d1[v]+d2[v] for v in range(1,n+1)]
for i in range(n):
    print(10**15 - min(d[i:]))

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=[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 heapq
def gijkstra(n,E,key=1,s=1):
    T, HQ = [[float('inf'), -1] for i in range(n+1)], [(0,s)]
    T[s][0] = 0
    while HQ:
        u = heapq.heappop(HQ)[1]
        for e in E[u]:
            d, v = T[u][0] + e[key], e[0]
            if T[v][0] > d:
                T[v] = [d, u]
                heapq.heappush(HQ,(d,v))
    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:]))