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:
def main():
    import heapq
    import sys
    import numpy as np
    from scipy.sparse import csr_matrix
    from scipy.sparse.csgraph import dijkstra

    input = sys.stdin.readline

    MAX  = 10 ** 15

    N, M, s, t = map(int, input().split())

    edge = np.array([input().split() for _ in range(M)], dtype = np.int64).T
    g1 = csr_matrix((edge[2], (edge[:2] - 1)), (N, N))
    g2 = csr_matrix((edge[3], (edge[:2] - 1)), (N, N))

    d1 = dijkstra(g1, directed = False, indices = s - 1)
    d2 = dijkstra(g2, directed = False, indices = t - 1)

    d = d1 + d2

    # print (d1)
    # print (d2)

    # print (g1)
    # print (g2)

    # print (edge)

    # tmp = MAX
    # ans = [MAX] * N
    # for i in range(N - 1, -1, -1):
    #     tmp = min(tmp, d[i])
    #     ans[i] -= int(tmp)

    # print (*ans, sep = '\n')

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    from sys import stdin
    input = stdin.readline
    import numpy as np
    import scipy.sparse as sp

    n, m, s, t = map(int, input().split())
    uvab = np.array([list(map(int, input().split())) for _ in [0]*m])

    data = uvab[:, 2]
    row = uvab[:, 0] - 1
    col = uvab[:, 1] - 1

    matrix = sp.csr_matrix(
        (data, (row, col)), shape=(n, n), dtype=np.int64)
    yen = sp.csgraph.dijkstra(matrix, indices=s-1, directed=False)

    data = uvab[:, 3]
    matrix = sp.csr_matrix(
        (data, (row, col)), shape=(n, n), dtype=np.int64)
    snk = sp.csgraph.dijkstra(matrix, indices=t-1, directed=False)
    
main()

Submission status: Wrong Answer

Solution code:
"""
「sからiに円による支払いで移動する際の最小の金額」円と、「iからtにスヌークによる支払いで移動する際の最小金額」スヌークになる。これを最小化すれば良い。
"""
from collections import defaultdict
G1 = defaultdict(list); G2 = defaultdict(list)
N, M, S, T = map(int, input().split())
S-=1; T-=1
for i in range(M):
    f, t , v1, v2 = map(int, input().split())
    G1[f-1].append((t-1, v1))
    G1[t-1].append((f-1, v1))
    G2[f-1].append((t-1, v2))
    G2[t-1].append((f-1, v2))

import queue
push = queue.heappush
pop = queue.heappop
INF = 10**10
d1 = [INF]*N; d2 = [INF]*N

def dijkstra(s, G, d):
    q = []
    d[s] = 0
    push(q, (0, s))

    while q:
        cost, v = pop(q)
        # print(f'd[{v}] = {cost}')
        # 既に q から取り出したものの方が低い
        if d[v] < cost:
            continue
        for to, tmpcost in G[v]:
            if d[to] > d[v] + tmpcost:
                d[to] = d[v] + tmpcost
                push(q, (d[to], to))

dijkstra(S, G1, d1)
dijkstra(T, G2, d2)
"""
for i in range(N):
    ans = 0
    for j in range(i, N):
        ans = max(ans, 10**15-d1[j]-d2[j])
    print(ans)
"""
anses = [0]*N
ans = 10**15
for i in range(N):
    ans = min(ans, d1[N-1-i]+d2[N-1-i])
    anses[N-1-i]=10**15-ans
for i in range(N):
    print(anses[i])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
G1 = defaultdict(list); G2 = defaultdict(list)
N, M, S, T = map(int, input().split())
S-=1; T-=1
for i in range(M):
    f, t , v1, v2 = map(int, input().split())
    G1[f-1].append((t-1, v1))
    G1[t-1].append((f-1, v1))
    G2[f-1].append((t-1, v2))
    G2[t-1].append((f-1, v2))

import queue
push = queue.heappush
pop = queue.heappop
INF = 10**10
d1 = [INF]*N; d2 = [INF]*N

def dijkstra(s, G, d):
    q = []
    d[s] = 0
    push(q, (0, s))

    while q:
        cost, v = pop(q)
        # print(f'd[{v}] = {cost}')
        # 既に q から取り出したものの方が低い
        if d[v] < cost:
            continue
        for to, tmpcost in G[v]:
            if d[to] > d[v] + tmpcost:
                d[to] = d[v] + tmpcost
                push(q, (d[to], to))

dijkstra(S, G1, d1)
dijkstra(T, G2, d2)
ans = 10**15
tmp = 0
for i in range(N):
    ans = 10**15
    for j in range(N):
        if i <= j:
            ans = min(ans, d1[i]+d2[i])
    print(10**15-ans)

Submission status: Wrong Answer

Solution code:
import heapq, sys
def input():
    return sys.stdin.readline()[:-1]

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

yen_edge = [[] for _ in range(n)]
snuke_edge = [[] for _ in range(n)]

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

class DijkstraList():
    #隣接リスト版
    #同一頂点の複数回探索を防ぐため訪問した頂点数を変数cntで持つ
    def __init__(self, adj, start):
        self.list = adj
        self.start = start
        self.size = len(adj)

    def solve(self):
        self.dist = [float("inf") for _ in range(self.size)]
        self.dist[self.start] = 0
        self.q = []
        self.cnt = 0

        heapq.heappush(self.q, self.start)

        while self.q and self.cnt < self.size:
            u = heapq.heappop(self.q)
            u_dist = self.dist[u]
            for v, w in self.list[u]:
                if self.dist[v] > u_dist + w:
                    self.dist[v] = u_dist + w
                    heapq.heappush(self.q, v)

            self.cnt += 1

        return

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

yen = DijkstraList(yen_edge, s - 1)
snuke = DijkstraList(snuke_edge, t - 1)
yen.solve()
snuke.solve()
ans_list = []

for i in range(n):
	ans_list.append(yen.distance(i) + snuke.distance(i))

ans = []

ans.append(10 ** 15 - ans_list[n - 1])

for i in range(1, n):
	if ans_list[n - i - 1] > ans_list[n - i]:
		ans_list[n - i - 1] = ans_list[n - i]
	ans.append(10 ** 15 - ans_list[n - i - 1])

for i in range(n - 1, -1, -1):
	print(ans[i])

Submission status: Wrong Answer

Solution code:
def dijkstra_heap(n,s,edge,k):
    # 始点sから各頂点への最短距離
    d = [float("inf")] * n
    d[s] = 0
    edgelist = []
    for e in edge[s]:
        heappush(edgelist, [e[k],e[2]])
    while edgelist:
        minedge = heappop(edgelist)
        v = minedge[1]
        d[v] = minedge[0]
        for e in edge[v]:
            if d[e[2]]>e[k] + d[v]:
                heappush(edgelist, [e[k] + d[v], e[2]])
    return d

def examD():
    N, M, s, t = LI()
    edge = defaultdict(list)
#    edge2 = defaultdict(list)
    # edge2 メモリ無駄
    for i in range(M):
        x, y, z1, z2 = map(int, input().split())
        x -=1; y -=1
        edge[x].append((z1,z2,y))
        edge[y].append((z1,z2,x))
    start1 = s-1
    start2 = t-1
    res1 = dijkstra_heap(N,start1, edge,0)
    res2 = dijkstra_heap(N,start2, edge,1)
    ans = []
    snuke = 10**15
    cur = res1[N-1] + res2[N-1]
    ans.append(cur)
    for i in range(N-2,-1,-1):
        if res1[i] + res2[i]<cur:
            cur = res1[i] + res2[i]
            ans.append(cur)
        else:
            ans.append(cur)
    for v in ans[::-1]:
        print(snuke-v)

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict as dd
import heapq
input = sys.stdin.readline
n, m, s, t = map(int, input().split())
e = dd(list)
money = 10 ** 15
for _ in range(m):
  u, v, a, b = map(int, input().split())
  e[u].append((v, a))
  e[v].append((u, a))
  e[u + n].append((v + n, b))
  e[v + n].append((u + n, b))
"""
for i in range(1, n + 1):
  e[i].append((i + n, 0))
"""
class dijkstra:
  def __init__(self, n, e):
    self.e = e
    self.n = n
  def path(self, s, t):
    d = [float("inf")] * (self.n + 1)
    vis = set()
    d[s] = 0
    h = [s]
    while not t in vis and len(h):
      v = heapq.heappop(h)
      v1 = v % (10 ** 15)
      v0 = v // (10 ** 15)
      if v1 in vis: continue
      vis.add(v1)
      for p in self.e[v1]:
        d[p[0]] = min(d[p[0]], d[v1] + p[1])
        if p[0] in vis: continue
        heapq.heappush(h, d[p[0]] * (10 ** 15) + p[0])
    return d
d = dijkstra(2 * n, e)
x = d.path(s, t)
y = d.path(t + n, s + n)
#print(x)
#print(y)
paths = [float("inf")] * (n + 1)
minpaths = [float("inf")] * (n + 1)
for i in range(1, n + 1):
  paths[i] = x[i] + y[n + i]
#print(paths)
minpaths[-1] = paths[-1]
for i in range(n - 1, -1, -1):
  minpaths[i] = min(minpaths[i + 1], paths[i])
#print(minpaths)
for i in range(1, n + 1):
  print(money - minpaths[i])

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict as dd
import heapq
input = sys.stdin.readline
n, m, s, t = map(int, input().split())
e = dd(list)
money = 10 ** 15
for _ in range(m):
  u, v, a, b = map(int, input().split())
  e[u].append((v, a))
  e[v].append((u, a))
  e[u + n].append((v + n, b))
  e[v + n].append((u + n, b))
"""
for i in range(1, n + 1):
  e[i].append((i + n, 0))
"""
class dijkstra:
  def __init__(self, n, e):
    self.e = e
    self.n = n
  def path(self, s, t):
    d = [float("inf")] * (self.n + 1)
    vis = set()
    d[s] = 0
    h = [s]
    while not t in vis and len(h):
      v = heapq.heappop(h)
      v1 = v % (10 ** 10)
      v0 = v // (10 ** 10)
      if v1 in vis: continue
      vis.add(v1)
      for p in self.e[v1]:
        d[p[0]] = min(d[p[0]], d[v1] + p[1])
        if p[0] in vis: continue
        heapq.heappush(h, d[p[0]] * (10 ** 10) + p[0])
    return d
d = dijkstra(2 * n, e)
x = d.path(s, t)
y = d.path(t + n, s + n)
#print(x)
#print(y)
paths = [float("inf")] * (n + 1)
minpaths = [float("inf")] * (n + 1)
for i in range(1, n + 1):
  paths[i] = x[i] + y[n + i]
#print(paths)
minpaths[-1] = paths[-1]
for i in range(n - 1, -1, -1):
  minpaths[i] = min(minpaths[i + 1], paths[i])
#print(minpaths)
for i in range(1, n + 1):
  print(money - minpaths[i])

Submission status: Wrong Answer

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


class Edge:
    def __init__(self, to, yen, snuuk):
        self.to = to
        self.yen = yen
        self.snuuk = snuuk


edges = [list() for _ in range(n)]

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

dist = [10**10]*n

heap = []
heapq.heapify(heap)
# heapq.heappush()

q = collections.deque()
q.append((s-1, 0))

while(len(q) != 0):
    v, cost = q.popleft()
    if dist[v] <= cost:
        continue
    dist[v] = cost
    for i in edges[v]:
        q.append((i.to, cost+i.yen))

q2 = collections.deque()
q2.append((t-1, 0))
dist2 = [10**10]*n

while(len(q2) != 0):
    v, cost = q2.popleft()
    if dist2[v] <= cost:
        continue
    dist2[v] = cost
    for i in edges[v]:
        q2.append((i.to, cost+i.snuuk))

# print(dist)
# print(dist2)
ans = [0]*n

ans[n-1] = 10**15-dist[n-1]-dist2[n-1]
for i in range(n-2, -1, -1):
    ans[i] = max(10**15-dist[i]-dist2[i], ans[i+1])

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

Submission status: Wrong Answer

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


def dijkstra(start: int, graph: list) -> list:
    """dijkstra法: 始点startから各頂点への最短距離を求める
    重み付きグラフgraphは隣接リストで与えられる
    計算量: O(|E|log|V|)
    """
    INF = float("inf")
    n = len(graph)
    distance = [INF] * n
    distance[start] = 0
    q = [(start, 0)]  #q = [(現在地, startからの距離)]
    while q:
        pos, dist = heapq.heappop(q)
        if distance[pos] < dist:
            continue
        for next_pos, cost in graph[pos]:
            if distance[pos] + cost < distance[next_pos]:
                distance[next_pos] = distance[pos] + cost
                heapq.heappush(q, (next_pos, distance[next_pos]))
    return distance


n, m, s, t = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]

y_graph = [[] for i in range(n)]
s_graph = [[] for i in range(n)]
for u, v, a, b in info:
    u -= 1
    v -= 1
    y_graph[u].append((v, a))
    y_graph[v].append((u, a))
    s_graph[u].append((v, b))
    s_graph[v].append((u, b))

s -= 1
t -= 1
y_cost = dijkstra(s, y_graph)
s_cost = dijkstra(t, s_graph)

"""ans = [0]*n
for i in range(n):
    ans[i] = y_cost[i] + s_cost[i]

for i in range(n-1)[::-1]:
    ans[i] = min(ans[i], ans[i+1])

for num in ans:
    print(10**15 - num)"""

Submission status: Wrong Answer

Solution code:
import heapq
N, M, S, T = map(int, input().split())
S, T = S - 1, T - 1
G_yen = [[] for i in range(N)]
G_snuuk = [[] for i in range(N)]
for i in range(M):
    u, v, a, b = map(int, input().split())
    u, v = u - 1, v - 1
    G_yen[u].append([v, a])
    G_yen[v].append([u, a])
    G_snuuk[u].append([v, b])
    G_snuuk[v].append([u, b])


def dijkstra(graph, start, inf=float('inf')):
    n = len(graph)
    distances = [inf] * n

    # 距離・頂点
    hq = [(0, start)]
    while hq:
        dist, fr = heapq.heappop(hq)
        distances[fr] = dist

        for to, cost in graph[fr]:
            if distances[to] != inf:
                continue

            new_dist = distances[fr] + cost
            if distances[to] <= new_dist:
                continue

            heapq.heappush(hq, (new_dist, to))

    return distances


from_start_yen = dijkstra(G_yen, S)
from_goal_snuuk = dijkstra(G_snuuk, T)

ans = [0] * (N + 1)
for i, yen, snuuk in zip(reversed(range(N)), from_start_yen[::-1], from_goal_snuuk[::-1]):
    ans[i] = max(ans[i + 1], 10 ** 15 - (yen + snuuk))

print(*ans[:-1], sep='\n')

Submission status: Wrong Answer

Solution code:
import heapq
inf = 10**10
def dijkstra(s, n, G):#スタート, 頂点数, グラフ:[[(cost, v)], ...]
    dist = [inf]*n
    edges = []#(sからvまでのコストの候補, v)
    dist[s] = 0
    for e in G[s]:
        heapq.heappush(edges, e)
    while edges:
        cost, v = heapq.heappop(edges)
        if dist[v] != inf:
            continue
        dist[v] = cost
        for c, nv in G[v]:
            if dist[nv] == inf:
                heapq.heappush(edges, (cost + c, nv))
    return dist

n, m, s, t = map(int, input().split())
G1 = [[] for _ in range(n)]
G2 = [[] for _ in range(n)]
for i in range(m):
    u, v, a, b = map(int, input().split())
    G1[u-1].append((a, v-1))
    G1[v-1].append((a, u-1))
    G2[u-1].append((b, v-1))
    G2[v-1].append((b, u-1))
dist1 = dijkstra(s-1, n, G1)
dist2 = dijkstra(t-1, n, G2)
ans = [0]*n
ans[-1] = dist1[n-1]+dist2[n-1]
for i in range(n-1)[::-1]:
    ans[i] = min(ans[i+1], dist1[i]+dist2[i])
for i in range(n):
    print(10**15-ans[i])

Submission status: Wrong Answer

Solution code:
n,m,s,t = map(int,input().split())
import collections
edge = collections.defaultdict(list)
for _ in range(m):
    u,v,a,b = map(int,input().split())
    edge[u-1].append([v-1,a,b])
    edge[v-1].append([u-1,a,b])
yen_dist = [-1 for _ in range(n)]
sunuk_dist = [-1 for _ in range(n)]

import heapq
next_point = []
heapq.heappush(next_point,(s-1,0))
while next_point:
    node,cost = heapq.heappop(next_point)
    if yen_dist[node] == -1:
        yen_dist[node] = cost
        for u,a,_ in edge[node]:
            if yen_dist[u] == -1:
                heapq.heappush(next_point,(u,cost+a))

heapq.heappush(next_point,(t-1,0))
while next_point:
    node,cost = heapq.heappop(next_point)
    if sunuk_dist[node] == -1:
        sunuk_dist[node] = cost
        for u,_,b in edge[node]:
            if sunuk_dist[u] == -1:
                heapq.heappush(next_point,(u,cost+b))

r = [0]*n
for i in range(n):
    r[-i-1] = max(r[-i],10**15-yen_dist[-i-1]-sunuk_dist[-i-1])
print(*r,sep='\n')

Submission status: Wrong Answer

Solution code:
n,m,s,t = map(int,input().split())
import collections
edge = collections.defaultdict(list)
for _ in range(m):
    u,v,a,b = map(int,input().split())
    edge[u-1].append([v-1,a,b])
    edge[v-1].append([u-1,a,b])
yen_dist = [-1 for _ in range(n)]
sunuk_dist = [-1 for _ in range(n)]

import heapq
next_point = []
heapq.heappush(next_point,(s-1,0))
while next_point:
    node,cost = heapq.heappop(next_point)
    if yen_dist[node] == -1:
        yen_dist[node] = cost
        for u,a,_ in edge[node]:
            if yen_dist[u] == -1:
                heapq.heappush(next_point,(u,cost+a))

heapq.heappush(next_point,(t-1,0))
while next_point:
    node,cost = heapq.heappop(next_point)
    if sunuk_dist[node] == -1:
        sunuk_dist[node] = cost
        for u,_,b in edge[node]:
            if sunuk_dist[u] == -1:
                heapq.heappush(next_point,(u,cost+b))

ys = 2 ** 63 -1
ans = []
for i in range(n-1,-1,-1):
    next_ys = yen_dist[i] + sunuk_dist[i]
    if ys > next_ys:
        ans.append((i,next_ys))
        ys = next_ys
ans.append((-1,0))
m = 10 ** 15
for i in range(len(ans)-1,-1,-1):
    for j in range(ans[i][0],ans[i-1][0]):
        print(m-ans[i-1][1])

Submission status: Wrong Answer

Solution code:
import heapq

n,m,s,t = map(int, input().split())
L = [[int(x) for x in input().split()] for _ in range(m)]

cost = [[] for _ in range(n)]
for i in range(m):
    cost[L[i][0]-1].append((L[i][2], L[i][3], L[i][1]-1))
    cost[L[i][1]-1].append((L[i][2], L[i][3], L[i][0]-1))
    
print(cost)
def dijkstra(s, n, cost, c):
    g = 10**6
    d = [10**15]*n
    used = [0]*n
    d[s] = 0
    used[s] = 1
    edgelist = []
    for e in cost[s]:
        heapq.heappush(edgelist, e[c]*g+e[2])
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if used[minedge%g] == 1:
            continue
        v = minedge%g
        d[v] = minedge//g
        used[v] = 1
        for e in cost[v]:
            if used[e[2]] == 0:
                heapq.heappush(edgelist, (e[c]+d[v])*g + e[2])
    return d

jpy = dijkstra(s-1, n, cost, 0)
snuuk = dijkstra(t-1, n, cost, 1)
ans_list = [0]*n
ans_list[n-1] = jpy[n-1]+snuuk[n-1]
for i in range(n-2, -1, -1):
    ans_list[i] = min(ans_list[i+1], jpy[i]+snuuk[i])
    
for i in range(n):
    print(10**15-ans_list[i])

Submission status: Wrong Answer

Solution code:
import heapq

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

cost = [[] for _ in range(n)]
for i in range(m):
    u, v, a, b = map(int, input().split())
    cost[u-1].append([a, b, v-1])
    cost[v-1].append([a, b, u-1])
    
print(cost)
def dijkstra(s, n, cost, c):
    d = [10**15]*n
    used = [0]*n
    d[s] = 0
    used[s] = 1
    edgelist = []
    for e in cost[s]:
        heapq.heappush(edgelist, [e[c], e[2]])
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if used[minedge[1]] == 1:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = 1
        for e in cost[v]:
            if used[e[2]] == 0:
                heapq.heappush(edgelist, [e[c]+d[v], e[2]])
    return d

jpy = dijkstra(s-1, n, cost, 0)
snuuk = dijkstra(t-1, n, cost, 1)
ans_list = [0]*n
ans_list[n-1] = jpy[n-1]+snuuk[n-1]
for i in range(n-2, -1, -1):
    ans_list[i] = min(ans_list[i+1], jpy[i]+snuuk[i])
    
for i in range(n):
    print(10**15-ans_list[i])

Submission status: Wrong Answer

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

E=[[]for i in range(n+1)]
S=[[]for i in range(n+1)]

for i in range(m):
    x,y,a,b=map(int,input().split())
    E[x].append((a,y,x))
    E[y].append((a,x,y))
    S[x].append((b,y,x))
    S[y].append((b,x,y))
    
#print(E)
#print(S)
import heapq
def dij(N,X):
    C=[10**15 for i in range(n+1)]
    C[N]=0
    Q=X[N]
    heapq.heapify(Q)
    for i in range(10**7):
        if len(Q)==0:
            break
        if C[Q[0][1]]!=10**15:
            heapq.heappop(Q)
        else:
            C[Q[0][1]]=C[Q[0][2]]+Q[0][0]
            q=Q[0]
            heapq.heappop(Q)
            for j in X[q[1]]:
                if C[j[1]]==10**15:
                    heapq.heappush(Q,j)
    return C
    
E=dij(s,E)
S=dij(t,S)
#print(E)
#print(S)
ans=[]
for i in range(1,n+1):
    ans.append((E[i]+S[i],i))
ans.sort()
#print(ans)
cnt=0
for i in range(1,n+1):
    while ans[cnt][1]<i:
        cnt+=1
    print(10**15-ans[cnt][0])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

import numpy as np
from heapq import *

N, M, S, T = map(int, input().split())
INF = 10 ** 7
graph = [[] for _ in range(N+1)] # graph[0]は使わない

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

def dijkstra(start, mode):
    dist = [INF] * (N+1) # dist[0]使わない
    dist[start] = 0
    que = [(0, start)]
    while que:
        d, p = heappop(que)
        # 既に安い交通費で来たことがある場合
        if dist[p] < d:
            continue
        for next_city, *fee in graph[p]:
            d1 = d + fee[mode]
            if dist[next_city] > d1:
                dist[next_city] = d1
                heappush(que, (d1, next_city))
    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)))

Submission status: Wrong Answer

Solution code:
import heapq
from heapq import heapify, heappush, heappop

global G

def input_graph(M, uvab):
  global G
  for i in range(M):
    u, v, a, b = uvab[i]
    G[u-1] += [[v-1, (a, b)]]
    G[v-1] += [[u-1, (a, b)]]
  
def dijkstra(N, S, flag):
  global G
  dist = [float('inf') for _ in range(N)]
  dist[S] = 0
  Q = [(0, S)]
  while Q:
    c, v = heappop(Q)
    if dist[v] < c:
      continue
    for t, cost in G[v]:
      yen, snuuk = cost
      if flag:
        if dist[v] + yen < dist[t]:
          dist[t] = dist[v] + yen
          heappush(Q, (dist[t], t))
      else:
        if dist[v] + snuuk < dist[t]:
          dist[t] = dist[v] + snuuk
          heappush(Q, (dist[t], t))
  return dist

def main():
  global G, dist
  N, M, S, T = map(int, input().split())
  S -= 1
  T -= 1
  uvab = [list(map(int, input().split())) for _ in range(M)]
  G = [[] for _ in range(N)]
  dist = [float('inf') for _ in range(N)]
  dist[S] = 0
  input_graph(M, uvab)
  yen_dist = dijkstra(N, S, True)
  snuuk_dist = dijkstra(N, T, False)
  dist = [yen_dist[i]+snuuk_dist[i] for i in range(N)]
  for i in range(N):
    print(10**15-min(dist))

if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
import heapq
from heapq import heapify, heappush, heappop

global G

def input_graph(M, uvab):
  global G
  for i in range(M):
    u, v, a, b = uvab[i]
    G[u-1] += [[v-1, (a, b)]]
    G[v-1] += [[u-1, (a, b)]]
  
def dijkstra(N, S, flag):
  global G
  dist = [float('inf') for _ in range(N)]
  dist[S] = 0
  Q = [(0, S)]
  while Q:
    c, v = heappop(Q)
    if dist[v] < c:
      continue
    for t, cost in G[v]:
      yen, snuuk = cost
      if flag:
        if dist[v] + yen < dist[t]:
          dist[t] = dist[v] + yen
          heappush(Q, (dist[t], t))
      else:
        if dist[v] + snuuk < dist[t]:
          dist[t] = dist[v] + snuuk
          heappush(Q, (dist[t], t))
  return dist

def main():
  global G, dist
  N, M, S, T = map(int, input().split())
  S -= 1
  T -= 1
  uvab = [list(map(int, input().split())) for _ in range(M)]
  G = [[] for _ in range(N)]
  dist = [float('inf') for _ in range(N)]
  dist[S] = 0
  input_graph(M, uvab)
  yen_dist = dijkstra(N, S, True)
  snuuk_dist = dijkstra(N, T, False)

  for i in range(N):
    print(10**15-yen_dist[i]-snuuk_dist[i])


if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
N,M,S,T=map(int,input().split())
En=[[]for i in range(N+1)]
Sn=[[]for i in range(N+1)]
for i in range(M):
    u,v,a,b=map(int,input().split())
    En[u].append((a,v,u))
    En[v].append((a,u,v))
    Sn[u].append((b,v,u))
    Sn[v].append((b,u,v))
    
EN=[-1 for i in range(N+1)]
EN[S]=0
import heapq
Q=[]
for i in En[S]:
    Q.append(i)
heapq.heapify(Q)
for i in range(10**7):
    if len(Q)==0:
        break
    else:
        if EN[Q[0][1]]!=-1:
            heapq.heappop(Q)
        else:
            q=heapq.heappop(Q)
            EN[q[1]]=EN[q[2]]+q[0]
            for j in En[q[1]]:
                if EN[j[1]]==-1:
                    heapq.heappush(Q,(j))
#print(EN)
SN=[-1 for i in range(N+1)]
SN[T]=0

Q=[]
for i in Sn[T]:
    Q.append(i)
heapq.heapify(Q)
for i in range(10**7):
    if len(Q)==0:
        break
    else:
        if SN[Q[0][1]]!=-1:
            heapq.heappop(Q)
        else:
            q=heapq.heappop(Q)
            SN[q[1]]=SN[q[2]]+q[0]
            for j in Sn[q[1]]:
                if SN[j[1]]==-1:
                    heapq.heappush(Q,(j))
#print(SN)

Q=[]
for i in range(1,len(SN)):
    Q.append((EN[i]+SN[i],i))
#print(Q)
heapq.heapify(Q)

for i in range(N):
    while Q[0][1]<i+1:
        heapq.heappop(Q)
    print(10**15-Q[0][0])

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter, deque, defaultdict
from math import factorial
import heapq, bisect
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

n, e, s, t = MAP()
s-= 1
t-= 1    
G1 = [[]for i in range(n)]
G2 = [[]for i in range(n)]       

for i in range(e):
    fr, to, w1, w2 = MAP()
    G1[fr-1].append((w1, to -1))
    G1[to-1].append((w1, fr -1))
    G2[fr-1].append((w2, to -1))
    G2[to-1].append((w2, fr -1))


def djkstra(s,G):
    visited = [False]*n     #その頂点を確定したかどうか
    d = [INF]*n
    que = []
    heapq.heapify(que)
    heapq.heappush(que, (0,s))

    while(len(que)>0):
        vs = heapq.heappop(que)
        print(vs)
        distance = vs[0]
        vertex = vs[1]
        if visited[vertex]:
            continue
        d[vertex] = distance
        visited[vertex] = True
        for Gs in G[vertex]:
            if d[Gs[1]] <= distance+Gs[0]:
                continue
            heapq.heappush(que,(distance+Gs[0], Gs[1]))
    
    return d

d_yen = djkstra(s,G1)
d_snuuk = djkstra(t,G2)

d_sum = [0]*n

for i in range(n):
    d_sum[i] = d_yen[i] + d_snuuk[i]

d_sum.reverse()
d_ans = [0]*n
d_ans[0] = d_sum[0]
for i in range(1,n):
    d_ans[i] = min(d_ans[i-1],d_sum[i])

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

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush

n, m, s, g = map(int, input().split())
e_list = [[] for _ in range(n+1)]
for _ in range(m):
  _from, _to, _yen, _snuuk = map(int, input().split())
  e_list[_from].append((_from, _to, _yen, _snuuk))
  e_list[_to].append((_to, _from, _yen, _snuuk))
yen = [-1] * (n+1)
snuuk = [-1] * (n+1)
yen[s] = snuuk[g] = 0
# yen
hq = []
for f, t, y, sn in e_list[s]:
  heappush(hq, (y, f, t))

while len(hq) > 0:
  y, f, t = heappop(hq)
  yen[t] = yen[f] + y
  for _f, _t, _y, _s in e_list[t]:
    if f != _t and yen[_t] < 0:
      heappush(hq, (_y, _f, _t))
# snuuk
hq = []
for f, t, y, sn in e_list[g]:
  heappush(hq, (sn, f, t))
while len(hq) > 0:
  sn, f, t = heappop(hq)
  snuuk[t] = snuuk[f] + sn
  for _f, _t, _y, _s in e_list[t]:
    if f != _t and snuuk[_t] < 0:
      heappush(hq, (_s, _f, _t))
# 累積和
hq = []
for i in range(1, n+1):
  heappush(hq, (yen[i]+snuuk[i], i))
last = (0, 0)
for i in range(n):
  if last[1] > i:
    print(10**15-last[0])
  else:
    while True:
      sn, town = heappop(hq)
      if town > i:
        print(10**15-sn)
        last = (sn, town)
        break

Submission status: Wrong Answer

Solution code:
from heapq import *
import numpy as np
n,m,s,t=map(int,input().split())
a=[[]for i in range (n+1)]
b=[[]for i in range(n+1)]
for i in range(m):
    p,q,r,g=map(int,input().split())
    a[p].append([q,r])
    a[q].append([p,r])
    b[p].append([q,g])
    b[q].append([p,g])
def f(x,r):
    p=[float("INF")]*(n+1)
    p[x],q=0,[[0,x]]
    while q:
        y,z=heappop(q)
        for i,j in r[z]:
            if p[i]>y+j:
                p[i]=y+i
                heappush(q,[p[i],i])
    return p[1:]
s1,t1=f(s,a),f(t,b)
p=[]
for i in range(n):
    p.append((s1[i]+t1[i],i+1))
p,e=sorted(p),0
for i in range(n):
    while p[e][1]<=i: e+=1
    print(10**15-p[e][0])