Problem:


Score : 400 points

Problem Statement

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

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

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

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

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

Constraints

2 \leq n \leq 10^5

1 \leq m \leq 10^5

1 \leq s,t \leq n

s \neq t

1 \leq u_i < v_i \leq n

1 \leq a_i,b_i \leq 10^9

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

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

All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

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

Sample Output 1

999999999999998
999999999999989
999999999999979
999999999999897

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

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

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

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

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

Sample Input 2

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

Sample Output 2

999999574976994
999999574976994
999999574976994
999999574976994
999999574976994
999999574976994
999999574976994
999999574976994



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


Sample output:
999999999999998
999999999999989
999999999999979
999999999999897

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

def dijkstra(graph, start):
  N = len(graph)
  d = [INF] * N
  d[start] = 0
  f = [False] * N
  q = [(0, start)]
  while q:
    c,u = heapq.heappop(q)
    if f[u]: continue
    d[u] = c
    f[u] = True
    for c,v in graph[u]:
      if not f[v]:
        heapq.heappush(q, (c + d[u], v))
  return d

N,M,s,t = IL()
grapha = [[] for i in range(N)]
graphb = [[] for i in range(N)]
for _ in range(M):
  u,v,a,b = IL()
  grapha[u-1].append((a,v-1))
  grapha[v-1].append((a,u-1))
  graphb[u-1].append((b,v-1))
  graphb[v-1].append((b,u-1))
  
da = dijkstra(grapha, s-1)
db = dijkstra(graphb, t-1)

moto = 10**15
ans = [moto-INF]
for i in range(N)[::-1]:
  ans.append(max(ans[-1],moto-da[i]-db[i]))
for i in range(1,N+1):
  print(ans[i])

Submission status: Wrong Answer

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


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

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

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

Submission status: Wrong Answer

Solution code:
import heapq
N, M, s, t = map(int, input().split())

class Edge:

    def __init__(self, to, yenCost, snukCost):
        self.to = to
        self.yenCost = yenCost
        self.snukCost = snukCost

graph = [[] for _ in range(N)]

for i in range(M):
    u, v, a, b = map(int, input().split())
    graph[u-1].append(Edge(v-1, a, b))
    graph[v-1].append(Edge(u-1, a, b))

moneyNow = 10**15

yenCost = [float("inf") for _ in range(N)]
snukCost = [float("inf") for _ in range(N)]

def dijkstra(start:int):
    pq = []
    heapq.heapify(pq)
    yenCost[start] = 0
    heapq.heappush(pq, (0, start))
    while pq:
        d, v = heapq.heappop(pq)
        if d > yenCost[v]:
            continue
        for e in graph[v]:
            if yenCost[e.to] > yenCost[v] + e.yenCost:
                yenCost[e.to] = yenCost[v] + e.yenCost
                heapq.heappush(pq, (yenCost[e.to], e.to))

def dijkstra2(start:int):
    pq = []
    heapq.heapify(pq)
    snukCost[start] = 0
    heapq.heappush(pq, (0, start))

    while pq:
        d, v = heapq.heappop(pq)
        if d > snukCost[v]:
            continue

        for e in graph[v]:
            if snukCost[e.to] > snukCost[v] + e.snukCost:
                snukCost[e.to] = snukCost[v] + e.snukCost
                heapq.heappush(pq, (snukCost[e.to], e.to))

dijkstra(s-1)
dijkstra2(t-1)
ans = 0
for mid in range(N):
    allCost = yenCost[mid] + snukCost[mid]
    print(moneyNow - allCost)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import heapq


def dijkstra(N, adj, cost, start):
    INF = 10 ** 10
    min_cost = [INF] * N
    min_cost[start] = 0
    que = [(0, start)]
    while len(que) > 0:
        c, node = heapq.heappop(que)
        for next_node in adj[node]:
            next_cost = min_cost[node] + cost[(node, next_node)]
            if next_cost < min_cost[next_node]:
                min_cost[next_node] = next_cost
                heapq.heappush(que, (next_cost, next_node))
    return min_cost


def main():
    MONEY_MAX = 10 ** 15
    N, M, S, T = list(map(int, input().split()))
    S -= 1
    T -= 1
    adj = defaultdict(list)
    yen = defaultdict(int)
    snuuk = defaultdict(int)
    for _ in range(M):
        U, V, A, B = list(map(int, input().split()))
        U -= 1
        V -= 1
        adj[U].append(V)
        adj[V].append(U)
        yen[(U, V)], yen[(V, U)] = A, A
        snuuk[(U, V)], snuuk[(V, U)] = B, B
    min_yen = dijkstra(N, adj, yen, S)
    min_snuuk = dijkstra(N, adj, snuuk, T)
    # 都市iで両替をしてs -> tを移動した場合の最小コスト
    min_cost = [y + s for y, s in zip(min_yen, min_snuuk)]
    min_cost[T] = MONEY_MAX  # ゴールの都市Tでは両替不可なのでsnuukの残りは0になるよう調整
    city_cost = [(cost, city) for city, cost in enumerate(min_cost)]
    heapq.heapify(city_cost)
    ans = [0] * N
    cost, city = heapq.heappop(city_cost)
    for i in range(N):
        # i年後に都市0 ～ i - 1の両替所は使えない
        while city < i:
            cost, city = heapq.heappop(city_cost)
        ans[i] = 10 ** 15 - cost
    for a in ans:
        print(a)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import heapq


def dijkstra(N, adj, cost, start):
    INF = 10 ** 10
    min_cost = [INF] * N
    min_cost[start] = 0
    que = [(0, start)]
    while len(que) > 0:
        c, node = heapq.heappop(que)
        for next_node in adj[node]:
            next_cost = min_cost[node] + cost[(node, next_node)]
            if next_cost < min_cost[next_node]:
                min_cost[next_node] = next_cost
                heapq.heappush(que, (next_cost, next_node))
    return min_cost


def main():
    N, M, S, T = list(map(int, input().split()))
    S -= 1
    T -= 1
    adj = defaultdict(list)
    yen = defaultdict(int)
    snuuk = defaultdict(int)
    for _ in range(M):
        U, V, A, B = list(map(int, input().split()))
        U -= 1
        V -= 1
        adj[U].append(V)
        adj[V].append(U)
        yen[(U, V)], yen[(V, U)] = A, A
        snuuk[(U, V)], snuuk[(V, U)] = B, B
    min_yen = dijkstra(N, adj, yen, S)
    min_snuuk = dijkstra(N, adj, snuuk, T)
    # 都市iで両替をしてs -> tを移動した場合の最小コスト
    min_cost = [y + s for y, s in zip(min_yen, min_snuuk)]
    city_cost = [(cost, city) for city, cost in enumerate(min_cost)]
    heapq.heapify(city_cost)
    ans = [0] * N
    cost, city = heapq.heappop(city_cost)
    for i in range(N):
        # i年後に都市0 ～ i - 1の両替所は使えない
        while city < i:
            cost, city = heapq.heappop(city_cost)
        ans[i] = 10 ** 15 - cost
    for a in ans:
        print(a)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import heapq
def dijkstra(s, n, g): # s: start, n: |V|, g; glaph 
    INF = 10**10
    d = [INF] * n
    d[s] = 0
    que = [] # (a,b): a... shortest dist, b... v
    heapq.heappush(que, (0, s))

    while que:
        dist, v = heapq.heappop(que)
        if d[v] < dist: continue # if v has been already used -> continue
        for next_v, cost in g[v]:
            if d[next_v] > d[v] + cost:
                d[next_v] = d[v] + cost
                heapq.heappush(que, (d[next_v], next_v))
    return d


n,m,s,t = map(int, input().split())
gal = [ [] for _ in range(n+1) ]
gbl = [ [] for _ in range(n+1) ]

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

adl = dijkstra(s,n+1,gal)
bdl = dijkstra(t,n+1,gbl)
ansl = [0]*n
curr_min = 10**18
for i in range(n-1,-1,-1):
    cost = adl[i+1] + bdl[i+1]
    curr_min = min(cost, curr_min)
    ansl[i] = 10**15-curr_min

for ans in ansl:
    print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
def dijkstra(s, n, g): # s: start, n: |V|, g; glaph 
    INF = 10**10
    d = [INF] * n
    d[s] = 0
    que = [] # (a,b): a... shortest dist, b... v
    heapq.heappush(que, (0, s))

    while que:
        dist, v = heapq.heappop(que)
        if d[v] < dist: continue # if v has been already used -> continue
        for next_v, cost in g[v]:
            if d[next_v] > d[v] + cost:
                d[next_v] = d[v] + cost
                heapq.heappush(que, (d[next_v], next_v))
    return d


n,m,s,t = map(int, input().split())
gal = [ [] for _ in range(n+1) ]
gbl = [ [] for _ in range(n+1) ]

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

adl = dijkstra(s,n+1,gal)
bdl = dijkstra(t,n+1,gbl)
ansl = [0]*(n+1)
curr_min = 10**18
for i in range(n,0,-1):
    cost = adl[i] + bdl[i]
    curr_min = min(cost, curr_min)
    ansl[i] = 10**15-curr_min

for ans in ansl[1:]:
    print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
def dijkstra(s, n, g): # s: start, n: |V|, g; glaph 
    INF = 10**10
    d = [INF] * n
    d[s] = 0
    que = [] # (a,b): a... shortest dist, b... v
    heapq.heappush(que, (0, s))

    while que:
        dist, v = heapq.heappop(que)
        if d[v] < dist: continue # if v has been already used -> continue
        for next_v, cost in g[v]:
            if d[next_v] > d[v] + cost:
                d[next_v] = d[v] + cost
                heapq.heappush(que, (d[next_v], next_v))
    return d


n,m,s,t = map(int, input().split())
gal = [ [] for _ in range(n+1) ]
gbl = [ [] for _ in range(n+1) ]

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

adl = dijkstra(s,n+1,gal)
bdl = dijkstra(t,n+1,gbl)
ansl = [0]*(n+1)
curr_min = 10**18
for i in range(n,0,-1):
    cost = adl[i] + bdl[i]
    curr_min = min(cost, curr_min)
    ansl[i] = 10**15-curr_min

for ans in ansl:
    print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush as pu, heappop as po

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

def dik(s,v):
    S = [float("INF")]*(n+1)
    S[s] = 0
    h = []
    pu(h,[0,s])
    while h:
        d,now = po(h)
        for nex in e[now]:
            a,b = nex[0],nex[v]
            if d+b < S[a]:
                S[a] = d+b
                pu(h,[d+b,a])
    return S[::-1]
ans = []
cost = 10**15
now = 0
for i,j in zip(dik(s,1),dik(t,2)):
    now = max(now,cost-i-j)
    ans.append(now)
print(*ans[::-1],sep="\n")

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop

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

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

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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

def dijkstra(G, s=0):
    n = len(G)
    que = [(0, s)]
    dist = [INF] * n
    dist[s] = 0
    while que:
        min_dist, u = heappop(que)
        if min_dist > dist[u]:
            continue
        for v, c in G[u]:
            if dist[u] + c < dist[v]:
                dist[v] = dist[u] + c
                heappush(que, (dist[u] + c, v))
    return dist

n, m, s, t = LI()
s-=1
t-=1
G1 = [[] for _ in range(n)]
G2 = [[] for _ in range(n)]
for _ in range(m):
    u, v, a, b = LI()
    G1[u-1] += [(v-1, a)]
    G1[v - 1] += [(u - 1, a)]
    G2[u-1] += [(v-1, b)]
    G2[v - 1] += [(u - 1, b)]

y_cost = dijkstra(G1, s)
s_cost = dijkstra(G2, t)
ans = [0] * n
ret = INF
for i in range(n - 1, -1, -1):
    ret = min(ret, s_cost[i] + y_cost[i])
    ans[i] = 10**15 - ret

print(*ans, sep="\n")

Submission status: Wrong Answer

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


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

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

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

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

Submission status: Wrong Answer

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


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

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

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

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

Submission status: Wrong Answer

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)
    return []
    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: Wrong Answer

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)
    return []    
    smat = dijkstra(coo_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: Wrong Answer

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
    co = coo_matrix((a, (u, v)), shape=(n+1, n+1), dtype=np.int32)
    return []
    ymat = dijkstra(coo_matrix((a, (u, v)), shape=(n+1, n+1), dtype=np.int32), indices=s, directed=False)
    smat = dijkstra(coo_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: Wrong Answer

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
    return []
    ymat = dijkstra(coo_matrix((a, (u, v)), shape=(n+1, n+1), dtype=np.int32), indices=s, directed=False)
    smat = dijkstra(coo_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: Wrong Answer

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)
    return []
    smat = dijkstra(coo_matrix((b, (u, v)), shape=(n+1, n+1), dtype=np.int32).tocsr(), indices=t, directed=False)    
    return []
    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()