Problem:


Score : 400 points

Problem Statement

Kenkoooo is planning a trip in Republic of Snuke.
In this country, there are n cities and m trains running.
The cities are numbered 1 through n, and the i-th train connects City u_i and v_i bidirectionally.
Any city can be reached from any city by changing trains.

Two currencies are used in the country: yen and snuuk.
Any train fare can be paid by both yen and snuuk.
The fare of the i-th train is a_i yen if paid in yen, and b_i snuuk if paid in snuuk.

In a city with a money exchange office, you can change 1 yen into 1 snuuk.
However, when you do a money exchange, you have to change all your yen into snuuk.
That is, if Kenkoooo does a money exchange when he has X yen, he will then have X snuuk.
Currently, there is a money exchange office in every city, but the office in City i will shut down in i years and can never be used in and after that year.

Kenkoooo is planning to depart City s with 10^{15} yen in his pocket and head for City t, and change his yen into snuuk in some city while traveling.
It is acceptable to do the exchange in City s or City t.

Kenkoooo would like to have as much snuuk as possible when he reaches City t by making the optimal choices for the route to travel and the city to do the exchange.
For each i=0,...,n-1, find the maximum amount of snuuk that Kenkoooo has when he reaches City t if he goes on a trip from City s to City t after i years.
You can assume that the trip finishes within the year.

Constraints

2 \leq n \leq 10^5

1 \leq m \leq 10^5

1 \leq s,t \leq n

s \neq t

1 \leq u_i < v_i \leq n

1 \leq a_i,b_i \leq 10^9

If i\neq j, then u_i \neq u_j  or v_i \neq v_j.

Any city can be reached from any city by changing trains.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

n m s t
u_1 v_1 a_1 b_1
:
u_m v_m a_m b_m

Output

Print n lines.
In the i-th line, print the maximum amount of snuuk that Kenkoooo has when he reaches City t if he goes on a trip from City s to City t after i-1 years.

Sample Input 1

4 3 2 3
1 4 1 100
1 2 1 10
1 3 20 1

Sample Output 1

999999999999998
999999999999989
999999999999979
999999999999897

After 0 years, it is optimal to do the exchange in City 1.

After 1 years, it is optimal to do the exchange in City 2.

Note that City 1 can still be visited even after the exchange office is closed.
Also note that, if it was allowed to keep 1 yen when do the exchange in City 2 and change the remaining yen into snuuk, we could reach City 3 with 999999999999998 snuuk, but this is NOT allowed.

After 2 years, it is optimal to do the exchange in City 3.

After 3 years, it is optimal to do the exchange in City 4.
Note that the same train can be used multiple times.

Sample Input 2

8 12 3 8
2 8 685087149 857180777
6 7 298270585 209942236
2 4 346080035 234079976
2 5 131857300 22507157
4 8 30723332 173476334
2 6 480845267 448565596
1 4 181424400 548830121
4 5 57429995 195056405
7 8 160277628 479932440
1 6 475692952 203530153
3 5 336869679 160714712
2 7 389775999 199123879

Sample Output 2

999999574976994
999999574976994
999999574976994
999999574976994
999999574976994
999999574976994
999999574976994
999999574976994



Sample input:
4 3 2 3
1 4 1 100
1 2 1 10
1 3 20 1


Sample output:
999999999999998
999999999999989
999999999999979
999999999999897

Submission status: Time Limit Exceeded

Solution code:
import heapq

n, m, s, t = map(int, input().split())
D = {}
DM, DS = {}, {}
for i in range(m):
  u, v, a, b = map(int, input().split())
  if u-1 in D:
    D[u-1].append(v-1)
  else:
    D[u-1] = [v-1]
  if v-1 in D:
    D[v-1].append(u-1)
  else:
    D[v-1] = [u-1]
  DM[(u-1)*n+v-1], DM[(v-1)*n+u-1] = a, a
  DS[(u-1)*n+v-1], DS[(v-1)*n+u-1] = b, b
dm, ds = [int(1e18) for _ in range(n)], [int(1e18) for _ in range(n)]
dm[s-1] = 0
ds[t-1] = 0
prevm, prevs = [-1 for _ in range(n)], [-1 for _ in range(n)]
pqm, pqs = [], []
for i in range(n):
  heapq.heappush(pqm, (dm[i], i))
  heapq.heappush(pqs, (ds[i], i))
while pqm != []:
  m = heapq.heappop(pqm)
  r = m[1]
  for i in D[r]:
    if dm[i] > dm[r] + DM[r*n+i]:
      dm[i] = dm[r] + DM[r*n+i]
      prevm[i] = r
      heapq.heappush(pqm, (dm[i], i))
while pqs != []:
  s = heapq.heappop(pqs)
  r = s[1]
  for i in D[r]:
    if ds[i] > ds[r] + DS[r*n+i]:
      ds[i] = ds[r] + DS[r*n+i]
      prevs[i] = r
      heapq.heappush(pqs, (ds[i], i))
X = [dm[i] + ds[i] for i in range(n)]
Y = [int(1e17) for _ in range(n)]
m = int(1e17)
for i in range(n):
  if m > X[n-1-i]:
    m = X[n-1-i]
  Y[i] = m
for i in range(n, 0, -1):
  print(int(1e15) - Y[i-1])

Submission status: Time Limit Exceeded

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

YEN = 10**15
INF = float('inf')


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

    def add_edge(self, source, destination, cost):
        self.__graph[source].append((destination, cost))
        self.__graph[destination].append((source, cost))

    @property
    def graph(self):
        return self.__graph


class Dijkstra:
    def __init__(self, graph, source):
        self.__costs = defaultdict(lambda: INF)
        costs = self.__costs
        costs[source] = 0
        g = graph.graph
        q = []
        heappush(q, (costs[source], source))

        while q:
            cp, p = heappop(q)
            if costs[p] < cp:
                continue
            for dst, cost in g[p]:
                alternative = cp + cost
                if costs[dst] > alternative:
                    costs[dst] = alternative
                    heappush(q, (alternative, dst))

    def minimum_cost(self, destination):
        return self.__costs[destination]


def spline(func_=int, iter_=None):
    if iter_ is None:
        iter_ = input().split()
    return map(func_, iter_)


def main():
    n, m, s, t = spline()
    g_yen = Graph()
    g_snuuk = Graph()
    for _ in range(m):
        u, v, a, b = spline()
        g_yen.add_edge(u, v, a)
        g_snuuk.add_edge(u, v, b)
    d_s = Dijkstra(g_yen, s)
    d_t = Dijkstra(g_snuuk, t)
    bestplace = 0
    max_snuuk = 0
    for i in range(1, n + 1):
        if bestplace < i:
            max_snuuk = 0
            for j in range(bestplace + 1, n + 1):
                snuuk = YEN - d_s.minimum_cost(j)
                snuuk -= d_t.minimum_cost(j)
                if snuuk > max_snuuk:
                    bestplace = j
                    max_snuuk = snuuk
        print(max_snuuk)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

YEN = 10**15
INF = float('inf')


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

    def add_edge(self, source, destination, cost):
        self.__graph[source].append((destination, cost))
        self.__graph[destination].append((source, cost))

    @property
    def graph(self):
        return self.__graph


class Dijkstra:
    def __init__(self, graph, source):
        self.__costs = defaultdict(lambda: INF)
        costs = self.__costs
        costs[source] = 0
        g = graph.graph
        q = []
        heappush(q, (costs[source], source))

        while q:
            cp, p = heappop(q)
            if costs[p] < cp:
                continue
            for dst, cost in g[p]:
                alternative = cp + cost
                if costs[dst] > alternative:
                    costs[dst] = alternative
                    heappush(q, (alternative, dst))

    def minimum_cost(self, destination):
        return self.__costs[destination]


def spline(func_=int, iter_=None):
    if iter_ is None:
        iter_ = input().split()
    return map(func_, iter_)


def main():
    n, m, s, t = spline()
    g_yen = Graph()
    g_snuuk = Graph()
    for _ in range(m):
        u, v, a, b = spline()
        g_yen.add_edge(u, v, a)
        g_snuuk.add_edge(u, v, b)
    d_s = Dijkstra(g_yen, s)
    d_t = Dijkstra(g_snuuk, t)
    for i in range(1, n + 1):
        max_snuuk = 0
        for j in range(1, n + 1):
            if i > j:
                continue
            snuuk = YEN - d_s.minimum_cost(j)
            snuuk -= d_t.minimum_cost(j)
            max_snuuk = max(max_snuuk, snuuk)
        print(max_snuuk)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

row = []
col = []
data_e = []
data_s = []
for _ in range(m):
    u,v,a,b = map(int, input().split())
    row.append(u)
    # row.append(v)
    col.append(v)
    # col.append(u)
    data_e.append(a)
    # data_e.append(a)
    data_s.append(b)
    # data_s.append(b)

graph_e = csr_matrix((data_e, (row,col)), shape=(n+1, n+1))
graph_s = csr_matrix((data_s, (row,col)), shape=(n+1, n+1))

d_e = dijkstra(csgraph=graph_e, directed=False, indices=s)
d_s = dijkstra(csgraph=graph_s, directed=False, indices=t)

ans = [0] * (n+1)
min_cost = 10**15
for i in range(n,0,-1):
    min_cost = min(min_cost, d_e[i]+d_s[i])
    ans[i] = min_cost

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

Submission status: Time Limit Exceeded

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

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

row = []
col = []
data_e = []
data_s = []
for _ in range(m):
    u,v,a,b = map(int, input().split())
    row.append(u)
    row.append(v)
    col.append(v)
    col.append(u)
    data_e.append(a)
    data_e.append(a)
    data_s.append(b)
    data_s.append(b)

graph_e = csr_matrix((data_e, (row,col)), shape=(n+1, n+1))
graph_s = csr_matrix((data_s, (row,col)), shape=(n+1, n+1))

d_e = dijkstra(csgraph=graph_e, directed=False, indices=s)
d_s = dijkstra(csgraph=graph_s, directed=False, indices=t)

ans = [0] * (n+1)
min_cost = 10**15
for i in range(n,0,-1):
    min_cost = min(min_cost, d_e[i]+d_s[i])
    ans[i] = min_cost

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

Submission status: Time Limit Exceeded

Solution code:

from collections import defaultdict
from heapq import heappop, heappush


class Graph():

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

    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 = []
        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
                    self.prev[v] = u
                    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]

ga=Graph()
gb=Graph()
n,m,s,t=map(int,input().split())
for _ in range(m):
    u,v,a,b=map(int,input().split())
    ga.add_edge(u,v,a)
    ga.add_edge(v,u,a)
    gb.add_edge(u,v,b)
    gb.add_edge(v,u,b)

da = Dijkstra(ga,s)
db = Dijkstra(gb,t)
x=[]
for i in range(1,n+1):
    x.append(da.shortest_distance(i)+db.shortest_distance(i))
for i in range(n):
    print(10**15-min(x[i:]))

Submission status: Time Limit Exceeded

Solution code:
n,m,s,t = map(int,input().split())
uvab = [list(map(int,input().split())) for _ in range(m)]

# import
from scipy.sparse.csgraph import csgraph_from_dense,dijkstra

cost_e = [[0] * n for _ in range(n)]
cost_s = [[0] * n for _ in range(n)]

for i in uvab:
    u,v,a,b = i
    cost_e[u-1][v-1] = a
    cost_s[u-1][v-1] = b
    cost_e[v-1][u-1] = a
    cost_s[v-1][u-1] = b

csr_e = csgraph_from_dense(cost_e)
csr_s = csgraph_from_dense(cost_s)

en = dijkstra(csr_e, indices=s-1)
sn = dijkstra(csr_s, indices=t-1)


ans = [10**15] * n
min_ = en[n-1] + sn[n-1]
for i in range(n-1, -1, -1):
    tmp = en[i] + sn[i]
    min_ = min(min_, tmp)
    ans[i] -= min_

for i in ans:
    print(int(i))

Submission status: Time Limit Exceeded

Solution code:
#ダイクストラ法
#O(ElogV)
import heapq
def dijkstra_heap(s,edge):
  #始点sから各頂点への最短距離
  d = [float("inf")] * (n+1)
  used = [False] * (n+1)
  d[s] = 0
  used[s] = True
  edgelist = []
  #edgelist : [sからの暫定(未確定)最短距離,頂点]のリスト
  #edge[s] : sから出る枝の[重み,終点]の配列
  for e in edge[s]:
    heapq.heappush(edgelist,e) #sの隣の点は枝の重さがそのまま暫定最短距離となる
  while len(edgelist):
    #まだ使われてない頂点の中から最小の距離のものを探す→確定させる
    minedge = heapq.heappop(edgelist)
    #minedge : [sからの(確定)最短距離,頂点]
    v = minedge[1]
    if used[v]:
      continue
    d[v] = minedge[0]
    used[v] = True
    for e in edge[v]:
      if not used[e[1]]:
        heapq.heappush(edgelist,[d[v]+e[0],e[1]])
  return d

################################
n,m,s,t = map(int,input().split()) #n:頂点数　w:辺の数

edge_yen = [[] for _ in range(n+1)]
edge_snuke = [[] for _ in range(n+1)]

for i in range(m):
  u,v,a,b = map(int, input().split())
  edge_yen[u].append([a,v])
  edge_yen[v].append([a,u])
  edge_snuke[u].append([b,v])
  edge_snuke[v].append([b,u])

d_yen = dijkstra_heap(s,edge_yen)
d_snuke = dijkstra_heap(t,edge_snuke)
ans = [0]*(n)
m = float("inf")
for i in range(n,0,-1):
  m = min(d_yen[i]+d_snuke[i],m)
  ans[i-1]=10**15-m
print(*ans,sep='\n')

Submission status: Time Limit Exceeded

Solution code:
import bisect
import collections
from collections import defaultdict
import sys

sys.setrecursionlimit(100000)
input = sys.stdin.readline
ACMOD = 1000000007
INF = 1 << 32


def lmi():
    return list(map(int, input().split()))


def llmi(n):
    return [lmi() for _ in range(n)]


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

MAX_VAL = 10 ** 20
uvab = llmi(m)
jpy_cost = defaultdict(dict)
snuke_cost = defaultdict(dict)


def dijkstra2_scipy(adj, start, n=None, limit=None):
    """
    caution!  add 10**-10 to avoid 0 cost
    """
    from scipy.sparse import csr_matrix
    from scipy.sparse.csgraph._shortest_path import dijkstra
    if limit:
        limit += 0.5
    cost, row_ind, col_ind = [], [], []
    for k1, _v in adj.items():
        for k2, _cost in _v.items():
            row_ind.append(k1)
            col_ind.append(k2)
            cost.append(_cost + 10 ** -10)
    cost_matrix = csr_matrix((cost, (row_ind, col_ind)))
    return dijkstra(cost_matrix, indices=[start])[0]


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

jpy_dijk = dijkstra2_scipy(jpy_cost, start=s - 1)
snuke_dijk = dijkstra2_scipy(snuke_cost, start=t - 1)
res = []
min_val = MAX_VAL
for i in reversed(range(n)):
    # 都市  i で両替
    val = jpy_dijk[i] + snuke_dijk[i]
    assert val < MAX_VAL
    min_val = min(min_val, val)
    res.append(min_val)
for x in reversed(res):
    print(10 ** 15 - int(x))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from collections import Counter
from itertools import product, permutations,combinations
from operator import itemgetter
from heapq import heappop, heappush
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix
import numpy as np
import math
import sys
input = sys.stdin.readline
#文字列のときはうまく行かないのでコメントアウトすること
sys.setrecursionlimit(2147483647)

def main():
  n, m, s, t = map(int, input().split())
  start = s-1
  goal = t-1
  yen = [[0 for i in range(n)] for j in range(n)]
  sunuk = [[0 for i in range(n)] for j in range(n)]
  for _ in range(m):
    u, v, a, b = map(int, input().split())
    u = u-1
    v = v-1
    yen[u][v]=a
    yen[v][u]=a
    sunuk[v][u]=b
    sunuk[u][v]=b
  yen_csr = csr_matrix(yen)
  sunuk_csr = csr_matrix(sunuk)
  cost_yen = dijkstra(yen_csr)
  cost_sunuk = dijkstra(sunuk_csr)
  cost = [0]*n
  for i in range(n):
    cost[i] = cost_yen[start][i] + cost_sunuk[goal][i]
  for i in range(n):
    print(10**15 - int(min(cost[i:])))
  
if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
#入力高速化 + 再帰回数制限解除
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10000000)
#ダイクストラ
#単一始点最短経路(正の辺のみ)
#s=始点 n=頂点数 edgeは隣接リスト(edge=[[[1,2],[2,4]],[[2,1]],[]])
#0-indexed
from heapq import heappop,heappush
def dijkstra(s,n,edge):
  inf=10**18
  ans=[inf]*n
  ans[s]=0
  h=[[0,s]]
  while h:
    c,v=heappop(h)
    if ans[v]<c:continue
    for u,t in edge[v]:
      if c+t<ans[u]:
        ans[u]=c+t
        heappush(h,[c+t,u])
  return ans
#solve
n,m,s,t=map(int,input().split())
s-=1
t-=1
yen_edge=[[]for _ in range(n)]
snuuk_edge=[[]for _ in range(n)]
for _ in range(m):
  u,v,a,b=map(int,input().split())
  u-=1
  v-=1
  yen_edge[u].append([v,a])
  yen_edge[v].append([u,a])
  snuuk_edge[u].append([v,b])
  snuuk_edge[v].append([u,b])
yen=dijkstra(s,n,yen_edge)
snuuk=dijkstra(t,n,snuuk_edge)
ans=[10**15-(yen[i]+snuuk[i])for i in range(n)]
for i in range(n-2,-1,-1):ans[i]=max(ans[i],ans[i+1])
for i in ans:print(i)

Submission status: Time Limit Exceeded

Solution code:
#入力高速化 + 再帰回数制限解除
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10000000)
#ダイクストラ
#単一始点最短経路(正の辺のみ)
#s=始点 n=頂点数 edgeは隣接リスト(edge=[[[1,2],[2,4]],[[2,1]],[]])
#0-indexed
from heapq import heappop,heappush
def dijkstra(s,n,edge):
  inf=10**16
  ans=[inf]*n
  ans[s]=0
  h=[[0,s]]
  while h:
    c,v=heappop(h)
    if ans[v]<c:continue
    for u,t in edge[v]:
      if c+t<ans[u]:
        ans[u]=c+t
        heappush(h,[c+t,u])
  return ans
#solve
n,m,s,t=map(int,input().split())
s-=1
t-=1
yen_edge=[[]for _ in range(n)]
snuuk_edge=[[]for _ in range(n)]
for _ in range(m):
  u,v,a,b=map(int,input().split())
  u-=1
  v-=1
  yen_edge[u].append([v,a])
  yen_edge[v].append([u,a])
  snuuk_edge[u].append([v,b])
  snuuk_edge[v].append([u,b])
yen=dijkstra(s,n,yen_edge)
snuuk=dijkstra(t,n,snuuk_edge)
ans=[yen[i]+snuuk[i] for i in range(n)]
for i in range(n-1,0,-1):ans[i-1]=min(ans[i],ans[i-1])
for i in ans:print(10**15-i)

Submission status: Time Limit Exceeded

Solution code:

import heapq
n, m, s, t = map(int, input().split())
money = 10**15 
graph = [[] for _ in range(n)]

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

def dijkstra(s, y):
  dist = [float('inf')]*n 
  dist[s] = 0
  q = [[0, s]]
  heapq.heapify(q)
  while q:
    cost, u = heapq.heappop(q)
    for v, yen, snuuk in graph[u]:
      if y:
        if dist[u] + yen < dist[v]:
          dist[v] = dist[u] + yen 
          heapq.heappush(q, [dist[v], v])
      else:
        if dist[u] + snuuk < dist[v]:
          dist[v] = dist[u] + snuuk 
          heapq.heappush(q, [dist[v], v])
  return dist

y_result = dijkstra(s-1, True)
s_result = dijkstra(t-1, False)

result = [y_result[i]+s_result[i] for i in range(n)]
for i in range(n):
  print(money-min(result[i:]))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

n, m, s, t = list(map(int, input().split()))
graph = [0] + [[] for _ in range(n)]
for _ in range(m):
    u, v, a, b = list(map(int, input().split()))
    # (cost, dest)
    graph[u].append(({'yen': a, 'sunuke': b}, v))
    graph[v].append(({'yen': a, 'sunuke': b}, u))

import heapq

def dijkstra(graph, queue, dist, cost_type):
    while queue:
        d, n = heapq.heappop(queue)
        if dist[n] != -1 and dist[n] < d:
            continue
        for cost, next_n in graph[n]:
            cost_with_type = cost[cost_type]
            if dist[next_n] > d + cost_with_type:
                dist[next_n] = d + cost_with_type
                queue.append((dist[next_n], next_n))

queue = [(0, s)]
dist_yen = [10 ** 16] + [10 ** 16] * n
dist_yen[s] = 0
dijkstra(graph, queue, dist_yen, 'yen')

queue = [(0, t)]
dist_sunuke = [10 ** 16] + [10 ** 16] * n
dist_sunuke[t] = 0
dijkstra(graph, queue, dist_sunuke, 'sunuke')

# FYI: https://atcoder.jp/contests/soundhound2018-summer-qual/submissions/10738125
answer = [0] + [0] * n
for i in range(n, 0, -1):
    answer[i - 1] = max(answer[i], 10 ** 15 - (dist_yen[i] + dist_sunuke[i]))
for i in range(n):
    print(answer[i])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

n, m, s, t = list(map(int, input().split()))
graph = [0] + [[] for _ in range(n)]
for _ in range(m):
    u, v, a, b = list(map(int, input().split()))
    # (cost, dest)
    graph[u].append(({'yen': a, 'sunuke': b}, v))
    graph[v].append(({'yen': a, 'sunuke': b}, u))

import heapq

def dijkstra(graph, queue, dist, cost_type):
    while queue:
        d, n = heapq.heappop(queue)
        if dist[n] != -1 and dist[n] < d:
            continue
        for cost, next_n in graph[n]:
            cost_with_type = cost[cost_type]
            if dist[next_n] > d + cost_with_type:
                dist[next_n] = d + cost_with_type
                queue.append((dist[next_n], next_n))

queue = [(0, s)]
dist_yen = [10 ** 16] + [10 ** 16] * n
dist_yen[s] = 0
dijkstra(graph, queue, dist_yen, 'yen')

queue = [(0, t)]
dist_sunuke = [10 ** 16] + [10 ** 16] * n
dist_sunuke[t] = 0
dijkstra(graph, queue, dist_sunuke, 'sunuke')

import collections
answer = collections.deque()
for i in range(1, n + 1):
    answer.append(10 ** 15 - (dist_yen[i] + dist_sunuke[i]))
for i in range(n):
    print(max(answer))
    answer.popleft()

Submission status: Time Limit Exceeded

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

read = sys.stdin.read
readline = sys.stdin.readline

n, m, s, t, *uvab = map(int, read().split())
if m == 1:
    from heapq import heappush, heappop

    N, M, S, T = n, m, s, t
    graph = [[] for _ in range(N + 1)]
    for u, v, a, b in zip(*[iter(uvab)] * 4):
        graph[u].append((v, a, b))
        graph[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 graph[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))

    d1 += d2
    answer = 10 ** 15 - np.minimum.accumulate(d1[::-1])[::-1][1:]
    print('\n'.join(answer.astype(str)))
    exit()

s -= 1
t -= 1
u = np.array(uvab[::4], np.int64) - 1
v = np.array(uvab[1::4], np.int64) - 1
a = np.array(uvab[2::4], np.int64)
b = np.array(uvab[3::4], np.int64)

yen_matrix = coo_matrix((a, (u, v)), shape=(n, n))
snuuk_matrix = coo_matrix((b, (u, v)), shape=(n, n))

yen = dijkstra(yen_matrix, directed=False, indices=s)
snuuk = dijkstra(snuuk_matrix, directed=False, indices=t)

costs = (yen + snuuk).astype(int)
answer = 10 ** 15 - np.minimum.accumulate(costs[::-1])[::-1]
print(*answer.tolist(), 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

read = sys.stdin.read
readline = sys.stdin.readline

n, m, s, t, *uvab = map(int, read().split())
s -= 1
t -= 1
u = np.array(uvab[::4], np.int64) - 1
v = np.array(uvab[1::4], np.int64) - 1
a = np.array(uvab[2::4], np.float_)
b = np.array(uvab[3::4], np.float_)

yen_matrix = csr_matrix((a, (u, v)), shape=(n, n))
snuuk_matrix = csr_matrix((b, (u, v)), shape=(n, n))

yen = dijkstra(yen_matrix, directed=False, indices=s)
snuuk = dijkstra(snuuk_matrix, directed=False, indices=t)

costs = (yen + snuuk).astype(int)
answer = 10 ** 15 - np.minimum.accumulate(costs[::-1])[::-1]
print(*answer.tolist(), 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

read = sys.stdin.read
readline = sys.stdin.readline

n, m, s, t, *uvab = map(int, read().split())
s -= 1
t -= 1
u = np.array(uvab[::4], np.int64) - 1
v = np.array(uvab[1::4], np.int64) - 1
a = np.array(uvab[2::4], np.int64)
b = np.array(uvab[3::4], np.int64)

yen_matrix = csr_matrix((a, (u, v)), shape=(n, n))
snuuk_matrix = csr_matrix((b, (u, v)), shape=(n, n))

yen = dijkstra(yen_matrix, directed=False, indices=s)
snuuk = dijkstra(snuuk_matrix, directed=False, indices=t)

costs = (yen + snuuk).astype(int)
answer = 10 ** 15 - np.minimum.accumulate(costs[::-1])[::-1]
print(*answer.tolist(), 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

read = sys.stdin.read
readline = sys.stdin.readline

n, m, s, t, *uvab = map(int, read().split())
u = np.array(uvab[::4], np.int64)
v = np.array(uvab[1::4], np.int64)
a = np.array(uvab[2::4], np.int64)
b = np.array(uvab[3::4], np.int64)

yen_matrix = csr_matrix((a, (u, v)), shape=(n + 1, n + 1))
snuuk_matrix = csr_matrix((b, (u, v)), shape=(n + 1, n + 1))

yen = dijkstra(yen_matrix, directed=False, indices=s)
snuuk = dijkstra(snuuk_matrix, directed=False, indices=t)

costs = (yen[1:] + snuuk[1:]).astype(int)
answer = 10 ** 15 - np.minimum.accumulate(costs[::-1])[::-1]
print('\n'.join(map(str, answer.tolist())))

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
from operator import itemgetter

read = sys.stdin.read
readline = sys.stdin.readline

n, m, s, t, *uvab = map(int, read().split())
u = np.array(uvab[::4], np.int64)
v = np.array(uvab[1::4], np.int64)
a = np.array(uvab[2::4], np.int64)
b = np.array(uvab[3::4], np.int64)

yen_matrix = csr_matrix((a, (u, v)), shape=(n + 1, n + 1))
snuuk_matrix = csr_matrix((b, (u, v)), shape=(n + 1, n + 1))

yen = dijkstra(yen_matrix, directed=False, indices=s)[1:]
snuuk = dijkstra(snuuk_matrix, directed=False, indices=t)[1:]

costs = (yen + snuuk).astype(int)
costs = sorted(zip(range(1, n + 1), costs.tolist()), key=itemgetter(1), reverse=True)

money = 10 ** 15
city, cost = costs.pop()
for i in range(n):
    if city <= i:
        while True:
            city, cost = costs.pop()
            if city > i:
                break
    print(money - cost)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline
from scipy.sparse.csgraph import csgraph_from_dense,dijkstra

def main():
    N,M,s,t = map(int,input().split())
    INF = 10**15
    
    yedge = [[INF for _ in range(N)] for _ in range(N)]
    sedge = [[INF for _ in range(N)] for _ in range(N)]
    for _ in range(M):
        u,v,a,b = map(int,input().split())
        yedge[u-1][v-1] = yedge[v-1][u-1] = a
        sedge[u-1][v-1] = sedge[v-1][u-1] = b
    
    Gy,Gs = dijkstra(csgraph_from_dense(yedge,null_value=INF),indices=s-1),dijkstra(csgraph_from_dense(sedge,null_value=INF),indices=t-1)
    
    al = []
    ans = 0
    for i,j in zip(Gy[::-1],Gs[::-1]):
        ans = max(ans,int(INF-i-j))
        al.append(ans)

    print(*al[::-1],sep="\n")
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline
from collections import deque

def main():
    N,M,s,t = map(int,input().split())
    INF = 10**15
    
    yedge = [[] for _ in range(N)]
    sedge = [[] for _ in range(N)]
    for _ in range(M):
        u,v,a,b = map(int,input().split())
        yedge[u-1].append((v-1,a))
        yedge[v-1].append((u-1,a))
        sedge[u-1].append((v-1,b))
        sedge[v-1].append((u-1,b))
        
    def dij(x,z):
        q = deque([x])
        go = [INF for _ in range(N)]
        go[x] = 0
        while q:
            now = q.pop()
            for fol,d in z[now]:
                if go[fol] > go[now]+d:
                    go[fol] = go[now]+d
                    q.append(fol)
        return go
        
    y,s = dij(s-1,yedge),dij(t-1,sedge)
    ans = []
    u = 0
    for i,j in zip(y[::-1],s[::-1]):
        u = max(u,INF-i-j) 
        ans.append(u)
        
    print(*ans[::-1],sep="\n")

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
inf = 1145141919810364364
start = 10**15
import heapq

def di(s,fl):
    d = [inf] * n
    used = [1] * n
    d[s] = 0
    used[s] = 0
    lis = []
    
    for q in edge[fl][s]:
        heapq.heappush(lis,q)
        
    while lis:
        minedge = heapq.heappop(lis)
        
        if used[minedge[1]] == 0:
            continue

        v = minedge[1]
        d[v] = minedge[0]
        used[v] = 0

        for q in edge[fl][v]:
            if used[q[1]] == 1:
                heapq.heappush(lis,[q[0]+d[v],q[1]])
    return d

n,m,s,t = map(int,input().split())
#0は円、1はスヌーク
edge = [[[] for i in range(n)] for _ in range(2)]

for i in range(m):
    u,v,a,b = map(int,input().split())
    edge[0][u-1].append([a,v-1])
    edge[0][v-1].append([a,u-1])
    edge[1][u-1].append([b,v-1])
    edge[1][v-1].append([b,u-1])
    
a = di(s-1,0)
b = di(t-1,1)
k = start - a[n-1] - b[n-1]
ans = [0] * n

for i in range(n):
    k = max(k , start - (a[n-1-i] + b[n-1-i]))
    ans[n-1-i] = k
    
for i in range(n):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
import heapq
def dijk(s,edge):
    used = [-1] * n #True:未確定
    used[s] = 0
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,[e[0],e[1]])
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if used[minedge[1]]>=0:
            continue
        v = minedge[1]
        kai=minedge[0]
        used[v] = kai
        for e in edge[v]:
            if used[e[1]]==-1:
                heapq.heappush(edgelist,[e[0]+kai,e[1]])                   
    return used

################################
n,m,s,t = map(int,input().split()) #n:頂点数　w:辺の数
s-=1
t-=1
edge1 = [[] for i in range(n)]
edge2= [[] for i in range(n)]
#edge[i] : iから出る道の[重み,行先]の配列
for i in range(m):
    x,y,z,w = map(int,input().split())
    edge1[x-1].append([z,y-1])
    edge1[y-1].append([z,x-1])
    edge2[x-1].append([w,y-1])
    edge2[y-1].append([w,x-1])
en=dijk(s,edge1)
su=dijk(t,edge2)
ans=[]
aa=10**20
for i in range(n-1,-1,-1):
    aa=min(aa,en[i]+su[i])
    ans.append(10**15-aa)
for i in range(n-1,-1,-1):
    print(ans[i])