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:
#!/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
    i, j = [uu-1 for uu in u], [vv-1 for vv in v]
    ymat = dijkstra(coo_matrix((a, (i, j)), shape=(n, n), dtype=np.int32), indices=s-1, directed=False)
    smat = dijkstra(coo_matrix((b, (i, j)), shape=(n, n), dtype=np.int32), indices=t-1, directed=False)    
    acc = list(accumulate(map(int, (ymat+smat)[::-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.int32), indices=s, directed=False, min_only=True)
    smat = dijkstra(coo_matrix((b, (u, v)), shape=(n+1, n+1), dtype=np.int32), indices=t, directed=False, min_only=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, csr_matrix
    from scipy.sparse.csgraph import dijkstra
    from itertools import accumulate
    ymat = dijkstra(csr_matrix((a, (u, v)), shape=(n+1, n+1), dtype=np.int32), indices=s, directed=False)
    smat = dijkstra(csr_matrix((b, (u, v)), shape=(n+1, n+1), dtype=np.int32), 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
    ymat = dijkstra(coo_matrix((a, (u, v)), shape=(n+1, n+1), dtype=np.int32).tocsr(), indices=s, directed=False)
    smat = dijkstra(coo_matrix((b, (u, v)), shape=(n+1, n+1), dtype=np.int32).tocsr(), 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:
import numpy as np
from heapq import heappush, heappop

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


def dijkstra(start, mode):
    INF = 10 ** 15
    dist = [INF] * (n+1)
    dist[start] = 0
    q = [(0, start)]
    while q:
        d, v = heappop(q)
        if dist[v] < d:
            continue
        for w, *a in G[v]:
            d1 = d + a[mode]
            if dist[w] > d1:
                dist[w] = d1
                heappush(q, (d1, w))
    return dist


d1 = np.array(dijkstra(s, 0))
d2 = np.array(dijkstra(t, 1))

# print(d1)

d = []
for i in range(n+1):
    d.append(d1[i]+d2[i])
for i in range(1, n+1):
    print(10**15-min(d[i:]))

Submission status: Time Limit Exceeded

Solution code:
# soundhound2018_summer_qual_d
import networkx as nx
n, m, s, t = map(int, input().split())


Gy = nx.Graph()   # Yen
Gy.add_nodes_from(range(1, n+1))

Gs = nx.Graph()   # Snuuk
Gs.add_nodes_from(range(1, n+1))


for _ in range(m):
    u, v, a, b = map(int, input().split())
    Gy.add_edge(u, v, weight=a)
    Gs.add_edge(u, v, weight=b)

shortest_length_from_s = nx.shortest_path_length(Gy, source=s, weight='weight')
shortest_length_to_t = nx.shortest_path_length(Gs, target=t, weight='weight')


dist = []
for i in range(n):
    dist.append(shortest_length_from_s[i+1]+shortest_length_to_t[i+1])


ans = []
B = 10**15
for i in range(n):
    B = min(B, dist[n-1-i])
    ans.append(B)
ans = ans[::-1]

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

Submission status: Time Limit Exceeded

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


# Python program for Dijkstra's single
# source shortest path algorithm. The program is
# for adjacency matrix representation of the graph

# Library for INT_MAX


class Graph():

    def __init__(self, vertices):
        self.V = vertices
        self.graph = [[0 for column in range(vertices)]
                      for row in range(vertices)]

    # A utility function to find the vertex with
    # minimum distance value, from the set of vertices
    # not yet included in shortest path tree
    def minDistance(self, dist, sptSet):

        # Initilaize minimum distance for next node
        min = sys.maxsize

        # Search not nearest vertex not in the
        # shortest path tree
        for v in range(self.V):
            if dist[v] < min and sptSet[v] == False:
                min = dist[v]
                min_index = v

        return min_index

    # Funtion that implements Dijkstra's single source
    # shortest path algorithm for a graph represented
    # using adjacency matrix representation
    def dijkstra(self, src):

        dist = [sys.maxsize] * self.V
        dist[src] = 0
        sptSet = [False] * self.V

        for cout in range(self.V):

            # Pick the minimum distance vertex from
            # the set of vertices not yet processed.
            # u is always equal to src in first iteration
            u = self.minDistance(dist, sptSet)

            # Put the minimum distance vertex in the
            # shotest path tree
            sptSet[u] = True

            # Update dist value of the adjacent vertices
            # of the picked vertex only if the current
            # distance is greater than new distance and
            # the vertex in not in the shotest path tree
            for v in range(self.V):
                if self.graph[u][v] > 0 and \
                        sptSet[v] == False and \
                        dist[v] > dist[u] + self.graph[u][v]:
                    dist[v] = dist[u] + self.graph[u][v]

        return dist


gy = [[0]*n for _ in range(n)]
gs = [[0]*n for _ in range(n)]

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

# Driver program
Gy = Graph(n)
Gy.graph = gy

Gs = Graph(n)
Gs.graph = gs


dy = Gy.dijkstra(s-1)
ds = Gs.dijkstra(t-1)
# print(dy)

dist = []
for i in range(n):
    dist.append(dy[i]+ds[i])

ans = []
B = 10**15
for i in range(n):
    B = min(B, dist[n-1-i])
    ans.append(B)
ans = ans[::-1]

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

Submission status: Time Limit Exceeded

Solution code:
# soundhound2018_summer_qual_d
import networkx as nx
n, m, s, t = map(int, input().split())


Gy = nx.Graph()   # Yen
Gy.add_nodes_from(range(1, n+1))

Gs = nx.Graph()   # Snuuk
Gs.add_nodes_from(range(1, n+1))


for _ in range(m):
    u, v, a, b = map(int, input().split())
    Gy.add_edge(u, v, weight=a)
    Gs.add_edge(u, v, weight=b)

shortest_length_from_s = nx.shortest_path_length(Gy, source=s, weight='weight')
shortest_length_to_t = nx.shortest_path_length(Gs, target=t, weight='weight')


dist = [-1]
for i in range(1, n+1):
    dist.append(shortest_length_from_s[i]+shortest_length_to_t[i])
# print(dist)

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

Submission status: Time Limit Exceeded

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


# Python program for Dijkstra's single
# source shortest path algorithm. The program is
# for adjacency matrix representation of the graph

# Library for INT_MAX


class Graph():

    def __init__(self, vertices):
        self.V = vertices
        self.graph = [[0 for column in range(vertices)]
                      for row in range(vertices)]

    # A utility function to find the vertex with
    # minimum distance value, from the set of vertices
    # not yet included in shortest path tree
    def minDistance(self, dist, sptSet):

        # Initilaize minimum distance for next node
        min = sys.maxsize

        # Search not nearest vertex not in the
        # shortest path tree
        for v in range(self.V):
            if dist[v] < min and sptSet[v] == False:
                min = dist[v]
                min_index = v

        return min_index

    # Funtion that implements Dijkstra's single source
    # shortest path algorithm for a graph represented
    # using adjacency matrix representation
    def dijkstra(self, src):

        dist = [sys.maxsize] * self.V
        dist[src] = 0
        sptSet = [False] * self.V

        for cout in range(self.V):

            # Pick the minimum distance vertex from
            # the set of vertices not yet processed.
            # u is always equal to src in first iteration
            u = self.minDistance(dist, sptSet)

            # Put the minimum distance vertex in the
            # shotest path tree
            sptSet[u] = True

            # Update dist value of the adjacent vertices
            # of the picked vertex only if the current
            # distance is greater than new distance and
            # the vertex in not in the shotest path tree
            for v in range(self.V):
                if self.graph[u][v] > 0 and \
                        sptSet[v] == False and \
                        dist[v] > dist[u] + self.graph[u][v]:
                    dist[v] = dist[u] + self.graph[u][v]

        return dist


gy = [[0]*n for _ in range(n)]
gs = [[0]*n for _ in range(n)]

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

# Driver program
Gy = Graph(n)
Gy.graph = gy

Gs = Graph(n)
Gs.graph = gs


dy = Gy.dijkstra(s-1)
ds = Gs.dijkstra(t-1)
# print(dy)

dist = []
for i in range(n):
    dist.append(dy[i]+ds[i])

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

Submission status: Time Limit Exceeded

Solution code:
# soundhound2018_summer_qual_d
import networkx as nx
n, m, s, t = map(int, input().split())


Gy = nx.Graph()   # Yen
# Gy.add_nodes_from(range(1, n+1))

Gs = nx.Graph()   # Snuuk
# Gs.add_nodes_from(range(1, n+1))


for _ in range(m):
    u, v, a, b = map(int, input().split())
    Gy.add_edge(u, v, weight=a)
    Gs.add_edge(u, v, weight=b)

shortest_length_from_s = nx.shortest_path_length(Gy, source=s, weight='weight')
shortest_length_to_t = nx.shortest_path_length(Gs, target=t, weight='weight')


dist = [-1]
for i in range(1, n+1):
    dist.append(shortest_length_from_s[i]+shortest_length_to_t[i])
# print(dist)

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

Submission status: Time Limit Exceeded

Solution code:
# soundhound2018_summer_qual_d
import networkx as nx
n, m, s, t = map(int, input().split())


Gy = nx.Graph()   # Yen
Gy.add_nodes_from(range(1, n+1))

Gs = nx.Graph()   # Snuuk
Gs.add_nodes_from(range(1, n+1))


for _ in range(m):
    u, v, a, b = map(int, input().split())
    Gy.add_edge(u, v, weight=a)
    Gs.add_edge(u, v, weight=b)

shortest_length_from_s = nx.shortest_path_length(Gy, source=s, weight='weight')
shortest_length_to_t = nx.shortest_path_length(Gs, target=t, weight='weight')


dist = [-1]
for i in range(1, n+1):
    dist.append(shortest_length_from_s[i]+shortest_length_to_t[i])
# print(dist)

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

Submission status: Time Limit Exceeded

Solution code:
import heapq

class SegmentTree(object):
    def __init__(self, A, dot, unit):
        n = 1 << (len(A) - 1).bit_length()
        tree = [unit] * (2 * n)
        for i, v in enumerate(A):
            tree[i + n] = v
        for i in range(n - 1, 0, -1):
            tree[i] = dot(tree[i << 1], tree[i << 1 | 1])
        self._n = n
        self._tree = tree
        self._dot = dot
        self._unit = unit

    def __getitem__(self, i):
        return self._tree[i + self._n]

    def update(self, i, v):
        i += self._n
        self._tree[i] = v
        while i != 1:
            i >>= 1
            self._tree[i] = self._dot(self._tree[i << 1], self._tree[i << 1 | 1])

    def add(self, i, v):
        self.update(i, self[i] + v)

    def sum(self, l, r):
        l += self._n
        r += self._n
        l_val = r_val = self._unit
        while l < r:
            if l & 1:
                l_val = self._dot(l_val, self._tree[l])
                l += 1
            if r & 1:
                r -= 1
                r_val = self._dot(self._tree[r], r_val)
            l >>= 1
            r >>= 1
        return self._dot(l_val, r_val)

INF = float("inf")
YEN = pow(10,15)
n,m,s,t = map(int,input().split())
s-=1;t-=1 #s,tを0index
yedge = [[] for _ in range(n)]
sedge = [[] for _ in range(n)]
for i in range(m):
  u,v,a,b = map(int,input().split())
  u-=1;v-=1
  yedge[u].append([a,v]);yedge[v].append([a,u])
  sedge[u].append([b,v]);sedge[v].append([b,u])

def dijkstra_heap(s,edge):
    #始点sから各頂点への最短距離
    d = [float("inf")] * n
    used = [True] * n #True:未確定。始点として探索されたか。というかdが更新されたか。
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中からスタートから最小の距離のものを探す
        if not used[minedge[1]]: #すでに探索済みの場合にはスキップして次のプライオリティーキューへ。
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False #ここで始点として探索済みにする。
        for e in edge[v]:
            if used[e[1]]: #行き先がすでに始点として探索済みでない場合には値を更新。
                heapq.heappush(edgelist,[e[0]+d[v],e[1]]) #重みをスタートからの最短重みにするため+d[v]
    return d ##始点sから各頂点への最短距離がアウトプットとなる。  
yto = dijkstra_heap(s,yedge)
sto = dijkstra_heap(s,sedge)
yot = dijkstra_heap(t,yedge)
sot = dijkstra_heap(t,sedge)
#print(yto)
#print(sto)
#print(yot)
#print(sot)
A = []
for i in range(n):
  if i == s:
    temp = sot[i]
  elif i == t:
    temp = yto[i]
  else:
    temp = yto[i]+sot[i]
  A.append(temp)
#print(A)
Tree = SegmentTree(A,min, INF)
for i in range(n):
  temp = Tree.sum(i,n)
  ans = YEN - temp
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
from collections import deque

INF = 10e10

def dijikstra(n,s,cost):

    d = [INF for i in range(n)] # 頂点sからの最短距離
    d[s] = 0
    used = [False for i in range(n)] # すでに使われたかのフラグ
    while True:
        v = -1
        # まだ使われていない頂点の内距離が最小のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1 or d[i] < d[v]):
                v = i

        if v == -1:
            break

        used[v] = True

        for i in range(n):
            d[i] = min(d[i], d[v] + cost[v][i])
    
    return d

def solve(n,s,t,costa,costb):
    dista = dijikstra(n,s,costa)
    distb = dijikstra(n,t,costb)

    d = [dista[i]+distb[i] for i in range(n)]
    
    minsnk = INF
    for i in range(n):
        tmp = d.pop()
        minsnk = min(minsnk,tmp)
        if i == 0:
            res = str(10**15-minsnk)
        else:
            res = str(10**15-minsnk) + '\n' + res

    print(res)



   


if __name__ == '__main__':
    n,m,s,t = map(int,input().split())
    costa = [[INF for j in range(n)] for i in range(n)]
    costb = [[INF for j in range(n)] for i in range(n)]
    for i in range(m):
        u,v,a,b = map(int,input().split())
        costa[u-1][v-1] = a
        costa[v-1][u-1] = a
        costb[u-1][v-1] = b
        costb[v-1][u-1] = b
    solve(n,s-1,t-1,costa,costb)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
from collections import deque

INF = 10e10

def dijikstra(n,s,cost):

    d = [INF for i in range(n)] # 頂点sからの最短距離
    d[s] = 0
    used = [False for i in range(n)] # すでに使われたかのフラグ
    while True:
        v = -1
        # まだ使われていない頂点の内距離が最小のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1 or d[i] < d[v]):
                v = i

        if v == -1:
            break

        used[v] = True

        for i in range(n):
            d[i] = min(d[i], d[v] + cost[v][i])
    
    return d

def solve(n,s,t,costa,costb):
    dista = dijikstra(n,s,costa)
    distb = dijikstra(n,t,costb)

    d = [dista[i]+distb[i] for i in range(n)]
    
    res = [0 for i in range(n)]
    minsnk = INF
    for i in range(n):
        tmp = d.pop()
        minsnk = min(minsnk,tmp)
        res[n-i-1] = minsnk

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



   


if __name__ == '__main__':
    n,m,s,t = map(int,input().split())
    costa = [[INF for j in range(n)] for i in range(n)]
    costb = [[INF for j in range(n)] for i in range(n)]
    for i in range(m):
        u,v,a,b = map(int,input().split())
        costa[u-1][v-1] = a
        costa[v-1][u-1] = a
        costb[u-1][v-1] = b
        costb[v-1][u-1] = b
    solve(n,s-1,t-1,costa,costb)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    n, m, s, t = map(int, input().split())
    yen = [[0]*n for _ in range(n)]
    snuke = [[0]*n for _ in range(n)]
    from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
    from scipy.sparse import csr_matrix

    for i in range(m):
        u, v, a, b = map(int, input().split())
        yen[u-1][v-1] = a
        yen[v-1][u-1] = a
        snuke[u-1][v-1] = b
        snuke[v-1][u-1] = b
    yen = csr_matrix(yen)
    snuke = csr_matrix(snuke)
    dy = dijkstra(yen)
    ds = dijkstra(snuke)
    cost = []
    for i in range(n):
        cost.append(int(dy[s-1][i] + ds[i][t-1]))

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

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra
import sys
input=sys.stdin.readline

def calc():
  n,m,s,t=map(int,input().split())
  s,t=s-1,t-1
  row=[]
  col=[]
  data1=[]
  data2=[]
  for _ in range(m):
    u,v,a,b=map(int,input().split())
    row.append(u-1)
    col.append(v-1)
    data1.append(a)
    data2.append(b)
  g1=csr_matrix((data1,(row,col)),shape=(n,n))
  g2=csr_matrix((data2,(row,col)),shape=(n,n))
  d1=dijkstra(g1,directed=False,indices=s)
  d2=dijkstra(g2,directed=False,indices=t)
  INF=10**15
  ans=[INF]*n
  ans[n-1]=int(d1[n-1]+d2[n-1])
  for i in range(n-2,-1,-1):
    tmp=int(d1[i]+d2[i])
    ans[i]=min(tmp,ans[i+1])
  for i in range(n):
    print(INF-ans[i])
calc()

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

n,m,s,t=map(int,input().split())
s,t=s-1,t-1
edges=[list(map(int,input().split())) for _ in range(m)]
row=[]
col=[]
data1=[]
data2=[]
for u,v,a,b in edges:
  row.append(u-1)
  col.append(v-1)
  data1.append(a)
  data2.append(b)
g1=csr_matrix((data1,(row,col)),shape=(n,n))
g2=csr_matrix((data2,(row,col)),shape=(n,n))
d1=dijkstra(g1,directed=False,indices=s)
d2=dijkstra(g2,directed=False,indices=t)
ans=[10**18]*n
for i in range(n-1,-1,-1):
  tmp=int(d1[i])+int(d2[i])
  ans[i]=min(tmp,ans[i])
  if i!=n-1:
    ans[i]=min(ans[i],ans[i+1])
maxs=10**15
for i in range(n):
  print(maxs-ans[i])

Submission status: Time Limit Exceeded

Solution code:
import heapq
import sys
input = sys.stdin.readline

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


class Dijkstra():
    class Edge():

        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):

        self.G = [[] for i in range(V+1)]
        self._E = 0
        self._V = V

    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加"""
        self.G[_from].append(self.Edge(_to, _cost))
        self._E += 1

    def s_path(self, s):
        """ 始点sから頂点iまでの最短路リスト 
        """
        que = []
        heapq.heapify(que)
        d = [10**15] * (self._V+1)
        d[s] = 0
        heapq.heappush(que, (0, s))
        while que:
            cost, v = heapq.heappop(que)
            if d[v] < cost:
                continue

            for e in self.G[v]:
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost
                    heapq.heappush(que, (d[e.to], e.to))
        return d
      
      
graph_snuke = Dijkstra(N)
graph_yen = Dijkstra(N)
for _ in range(M):
    u, v, a, b = map(int, input().split())
    graph_yen.add(u, v, a)
    graph_yen.add(v, u, a)
    graph_snuke.add(u, v, b)
    graph_snuke.add(v, u, b)

yen = graph_yen.s_path(S)
snuke = graph_snuke.s_path(T)
minimum_case = [10**15 for i in range(N+1)]
for i in range(N):
    minimum_case[1+i] -= (yen[i+1]+snuke[i+1])
for i in range(N-1, -1, -1):
    minimum_case[i] = max(minimum_case[i], minimum_case[i+1])
for i in range(1, N+1):
    print(minimum_case[i])

Submission status: Time Limit Exceeded

Solution code:
import heapq
import sys
input = sys.stdin.readline

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


class Edge():

    def __init__(self, _to, _cost):
        self.to = _to
        self.cost = _cost


class Dijkstra():
    def __init__(self, V):

        self.G = [[] for i in range(V+1)]
        self._E = 0
        self._V = V

    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加"""
        self.G[_from].append(Edge(_to, _cost))
        self._E += 1

    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路リスト 
        """
        que = []
        heapq.heapify(que)
        d = [10**15] * (self._V+1)
        d[s] = 0
        heapq.heappush(que, (0, s))  # 始点の(最短距離, 頂点番号)をヒープに追加

        while que:
            cost, v = heapq.heappop(que)
            if d[v] < cost:
                continue

            for e in self.G[v]:
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost
                    heapq.heappush(que, (d[e.to], e.to))
        return d


graph_snuke = Dijkstra(N)
graph_yen = Dijkstra(N)
for _ in range(M):
    u, v, a, b = map(int, input().split())
    graph_yen.add(u, v, a)
    graph_yen.add(v, u, a)
    graph_snuke.add(u, v, b)
    graph_snuke.add(v, u, b)

yen = graph_yen.shortest_path(S)
snuke = graph_snuke.shortest_path(T)
minimum_case = [10**15 for i in range(N+1)]
for i in range(N):
    minimum_case[1+i] -= (yen[i+1]+snuke[i+1])
for i in range(N-1, -1, -1):
    minimum_case[i] = max(minimum_case[i], minimum_case[i+1])
for i in range(1, N+1):
    print(minimum_case[i])

Submission status: Time Limit Exceeded

Solution code:
import heapq
import sys
input = sys.stdin.readline

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

import heapq


class Edge():
    """ 重み付き有向辺 """

    def __init__(self, _to, _cost):
        self.to = _to
        self.cost = _cost


class Dijkstra():
    def __init__(self, V):

        self.G = [[] for i in range(V+1)]
        self._E = 0
        self._V = V

    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加"""
        self.G[_from].append(Edge(_to, _cost))
        self._E += 1

    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路リスト 
        """
        que = []
        heapq.heapify(que)
        d = [float("inf")] * (self._V+1)
        d[s] = 0
        heapq.heappush(que, (0, s))  

        while len(que) != 0:
            cost, v = heapq.heappop(que)
            if d[v] < cost:
                continue

            for i in range(len(self.G[v])):
                e = self.G[v][i]  # vのi個目の隣接辺e
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost
                    heapq.heappush(que, (d[e.to], e.to))
        return d
graph_snuke = Dijkstra(N)
graph_yen = Dijkstra(N)
for _ in range(M):
    u, v, a, b = map(int, input().split())
    graph_yen.add(u, v, a)
    graph_yen.add(v, u, a)
    graph_snuke.add(u, v, b)
    graph_snuke.add(v, u, b)

yen = graph_yen.shortest_path(S)
snuke = graph_snuke.shortest_path(T)
minimum_case = [10**15 for i in range(N+1)]
for i in range(N):
    minimum_case[1+i] -= (yen[i+1]+snuke[i+1])
for i in range(N-1, -1, -1):
    minimum_case[i] = max(minimum_case[i], minimum_case[i+1])
for i in range(1, N+1):
    print(minimum_case[i])