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 sys
    input = sys.stdin.readline
    import heapq

    n,m,s,t = map(int,input().split())
    edgesYen = [[]for _ in range(n+1)]
    edgesSnuuk = [[]for _ in range(n+1)]
    for _ in range(m):
        u,v,a,b = map(int,input().split())
        edgesYen[u].append((v,a))
        edgesSnuuk[u].append((v,b))
        edgesYen[v].append((u,a))
        edgesSnuuk[v].append((u,b))
    
    def dijkstra(edges,costDic,startPoint):
        que=[(0,startPoint)]
        heapq.heapify(que)
        while que:
            cost,now = heapq.heappop(que)
            if now not in costDic:
                costDic[now] = cost
                for nx,c in edges[now]:
                    if nx not in costDic:
                        heapq.heappush(que,(cost+c,nx))
    costDicYen = {}
    costDicSnuuk = {}
    dijkstra(edgesYen,costDicYen,s)
    dijkstra(edgesSnuuk,costDicSnuuk,t)

    costList = []
    for i in range(1,n+1):
        cost = costDicYen[i]+costDicSnuuk[i]
        costList.append((cost,i))
    heapq.heapify(costList)
    c,l = heapq.heappop(costList)
    for i in range(n):
        while l<=i:
            c,l = heapq.heappop(costList)
        print(10**9-c)
main()

Submission status: Wrong Answer

Solution code:
from heapq import heapify,heappush,heappop

n,m,s,t = map(int,input().split())#順に都市の数、電車の数、スタート、ゴール
adj_list = [[]for i in range(0,(n+1),1,)]#隣接リスト(都市1~nをそのまま使いたいのでn+1の大きさで宣言して0は使わない)
for i in range(0,m,1):
    u,v,a,b = map(int,input().split())
    adj_list[u].append([v,a,b])#[0]行先[1]円[2]スヌーク
    adj_list[v].append([u,a,b])

D_INF = 10**15
d = [D_INF]*(n+1)#最速到達距離。でかい数で初期化
d[s] = 0#スタート
que = []
heapify(que)
heappush(que,(d[s],s))

while(len(que)):
    time,place = heappop(que)
    if time > d[place]:
        continue
    for i in range(0,len(adj_list[place]),1):
        if d[adj_list[place][i][0]] > time + adj_list[place][i][1]:#とりあえず円で
            d[adj_list[place][i][0]] = time + adj_list[place][i][1]
            heappush(que,(d[adj_list[place][i][0]],adj_list[place][i][0]))


d_sn = [D_INF]*(n+1)#最速到達距離。でかい数で初期化
d_sn[t] = 0#スタート
heappush(que,(d_sn[t],t))

while(len(que)):
    time,place = heappop(que)
    if time > d_sn[place]:
        continue
    for i in range(0,len(adj_list[place]),1):
        if d_sn[adj_list[place][i][0]] > time + adj_list[place][i][2]:
             d_sn[adj_list[place][i][0]] = time + adj_list[place][i][2]
             heappush(que,(d_sn[adj_list[place][i][0]],adj_list[place][i][0]))

print(d)
print(d_sn)

for i in range(1,n+1,1):
    d[i]=d[i]+d_sn[i]
    heappush(que,(d[i],i))
minimum,minimum_place = heappop(que)
print()

for i in range(0,n,1):
    if minimum_place <= i:
        while(len(que)):
            minimum,minimum_place = heappop(que)
            if minimum_place > i:
                break
    print(10**15-minimum)

Submission status: Wrong Answer

Solution code:
import heapq
n,m,s,t = map(int, input().split())
s -= 1
t -= 1
edges1 = [[] for i in range(n)]
edges2 = [[] for i in range(n)]
#  1 real world
#  2 snuuk world
for i in range(m):
    u,v,a,b = map(int, input().split())
    u -= 1
    v -= 1
    # real
    edges1[u].append((v,a))
    edges1[v].append((u,a))
    # snuuk
    edges2[u].append((v,b))
    edges2[v].append((u,b))

def dijkstra(n, edges, s):
    INF = 10**20
    """
    input
        n : 頂点数
        edges : リスト(始点, 終点, コスト)
        s : 始点
    output
        d : 始点からの最短距離
    """
    d = [INF] * n
    used = [False] * n
    d[s] = 0
    used[s] = True
    edgelist = []
    # 初期のやつ
    for v, c in edges[s]:
        # print("v{},c{}".format(v,c))
        # コストを前にしてpushしておく(そこから最小値を取り出すので)
        heapq.heappush(edgelist, (c, v))
    # 空になるまで
    while len(edgelist):
        # コスト最小値を取り出す
        c_min, v_min = heapq.heappop(edgelist)
        # そのエッジがすでに確定していたら終わり
        if used[v_min]:
            continue
        # 確定していなければ、そこから派生するエッジをコスト付与して与える
        d[v_min] = c_min
        used[v_min] = True
        for v, c in edges[v_min]:
            if not used[v]:
                heapq.heappush(edgelist, (c+c_min, v))
    return d


cnt1 = dijkstra(n,edges1,s)
cnt2 = dijkstra(n,edges2,t)
# print(cnt1)
# print(cnt2)
zs = [c1+c2 for c1,c2 in zip(cnt1,cnt2)]
mn = 10**20
ans = []
for z in zs[::-1]:
    print(mn,z)
    mn = min(mn,z)
    ans.append(10**15-mn)

for a in ans[::-1]:
    print(a)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
n,m,s,t = map(int,input().split())
edge = [[] for i in range(n)]
es = [[] for i in range(n)]
for i in range(m):
  u,v,a,b = map(int,input().split())
  es[u-1].append([a,v-1])
  es[v-1].append([a,u-1]) 
  edge[u-1].append([b,v-1])
  edge[v-1].append([b,u-1]) 

es = tuple(es)
edge = tuple(edge)

import heapq
def dijkstra_heap(s):
    #始点sから各頂点への最短距離
    d = [10**18] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

ES = dijkstra_heap(s-1)
EDGE = dijkstra_heap(t-1)
cost = 0
chk = [0]*n
for i in range(n-1,-1,-1):
  cost = max(cost,10**15-ES[i]-EDGE[i])
  chk[i] = cost
chk = tuple(chk)
print(*chk, sep="\n")

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
n,m,s,t = map(int,input().split())
edge = [[] for i in range(n)]
es = [[] for i in range(n)]
for i in range(m):
  u,v,a,b = map(int,input().split())
  es[u-1].append([a,v-1])
  es[v-1].append([a,u-1]) 
  edge[u-1].append([b,v-1])
  edge[v-1].append([b,u-1]) 

es = tuple(es)
edge = tuple(edge)

import heapq
def dijkstra_heap(s):
    #始点sから各頂点への最短距離
    d = [10**15] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

ES = dijkstra_heap(s-1)
EDGE = dijkstra_heap(t-1)
chk = [0]*(n+1)
for i in range(n-1,-1,-1):
  chk[i] = max(chk[i+1],10**15-ES[i]-EDGE[i])

chk = tuple(chk)
for i in range(n):
  print(chk[i])

Submission status: Wrong Answer

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

def dijkstra(n, graph, s, yen=True):
    dist = [10**18] * n
    queue = [(s, 0)]
    dist[s] = 0
    while queue:
        v, d = heapq.heappop(queue)
        if dist[v] < d:
            continue
        for child, costa, costb in graph[v]:
            if yen:
                cost = costa
            else:
                cost = costb
            if dist[v] + cost < dist[child]:
                dist[child] = dist[v] + cost
                heapq.heappush(queue, (child, dist[child]))
    return dist

def main():
    n, m, s, t = map(int, input().split())
    s -= 1
    t -= 1
    s_graph = [[] for _ in range(n)]
    t_graph = [[] for _ in range(n)]
    for i in range(m):
        u, v, a, b = map(int, input().split())
        u -= 1
        v -= 1
        s_graph[u].append((v, a, b))
        s_graph[v].append((u, a, b))
        t_graph[u].append((v, a, b))
        t_graph[v].append((u, a, b))
    s_dist = dijkstra(n, s_graph, s, True)
    t_dist = dijkstra(n, t_graph, t, False)

    cost = 10 ** 18
    for i in range(n-1, -1, -1):
        cost = min(cost, s_dist[i] + t_dist[i])
        print(10 ** 15 - cost)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import permutations,combinations
from collections import defaultdict,Counter
from pprint import pprint

def myinput():
    return map(int,input().split())

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col):
    data.sort(key=lambda x:x[col],reverse=False)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

n,m,s,t = myinput()
uvab = mylistinput(m)

# Dijkstra法(O(ElogV))
# edge[i] : iから出る道の[重み,行先]の配列
# import heapq
# def dijkstra_heap(n,s,edge):
#     #始点sから各頂点への最短距離
#     d = [float("inf")] * n
#     used = [True] * n # True:未確定
#     d[s] = 0
#     used[s] = False
#     edgelist = []
#     for e in edge[s]:
#         heapq.heappush(edgelist,e)
#     while len(edgelist):
#         minedge = heapq.heappop(edgelist)
#         # まだ使われてない頂点の中から最小の距離のものを探す
#         if not used[minedge[1]]:
#             continue
#         v = minedge[1]
#         d[v] = minedge[0]
#         used[v] = False
#         for e in edge[v]:
#             if used[e[1]]:
#                 heapq.heappush(edgelist,[e[0]+d[v],e[1]])
#     return d

# Dijkstra法(O(ElogV))
# edge[i] : iから出る道の[重み,行先]の配列
# 高速化版 
import heapq
def dijkstra_heap(n,s,edge):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

g1 = [ [] for _ in range(n) ]
g2 = [ [] for _ in range(n) ]
for i in range(m):
    u = uvab[i][0] - 1
    v = uvab[i][1] - 1
    a = uvab[i][2]
    b = uvab[i][3]
    g1[u].append([a,v])
    g1[v].append([a,u])
    g2[u].append([b,v])
    g2[v].append([b,u])
# print(g1)
# print(g2)

d1 = dijkstra_heap(n,s-1,g1)
d2 = dijkstra_heap(n,t-1,g2)
# print(d1)
# print(d2)

yen = 10**15
ans = -1*float("inf")
for i in reversed(range(n)):
    snuke = yen - d1[i] - d2[i] 
    ans = max(ans,snuke)
    print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
INF = float("inf")


def Dijkstra(n, s, g, mode):  # (頂点数，始点，グラフ，モード)を引数に
    dist = [INF] * n  # distを初期化
    dist[s] = 0  # 始点の距離は0
    hq = [(0, s)]  # (距離，頂点)で管理
    while hq:  # BFSと同様に探索
        d, v = heappop(hq)  # 最小距離とその頂点を取得
        if dist[v] < d:  # すでに最小になっている時はcontinue
            continue
        for w, *a in g[v]:  # そうでない時は隣接点への重みとその頂点を順に取得
            nd = d + a[mode]
            if dist[w] > nd:  # 最小になっていな開ければ更新してhqにpush
                dist[w] = nd
                heappush(hq, (nd, w))
    return dist


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

    d_yen = Dijkstra(n, s, g, 0)
    d_sunnk = Dijkstra(n, t, g, 1)

    ans = [0] * n
    cost = float("inf")
    for i in range(n-1, -1, -1):
        cost = min(cost, d_yen[i] + d_sunnk[i])
        ans[i-1] = 10 ** 15 - cost
    print(*ans, sep='\n')


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import heapq

def dijkstra(s, G):
    inf = 1145141919810
    dist = [inf] * n
    dist[s] = 0
    c = [0] * n
    p = []
    heapq.heapify(p)
    heapq.heappush(p, (dist[s], s))
    while p:
        d, u = heapq.heappop(p)
        if dist[u] < d:
            continue
        c[u] = 1
        for g in G[u]:
            if c[g[0]] == 0 and dist[u] + g[1] < dist[g[0]]:
                dist[g[0]] = dist[u] + g[1]
                heapq.heappush(p, (dist[g[0]], g[0]))
    return dist

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

Submission status: Wrong Answer

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


class PriorityQueue:
    def __init__(self, heap):
        self.heap = heap
        heapify(self.heap)

    def push(self, item):
        heappush(self.heap, item)

    def pop(self):
        return heappop(self.heap)

    def pushpop(self, item):
        return heappushpop(self.heap, item)

    def __call__(self):
        return self.heap

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


def main():

    N, M, s, t = map(int, input().split())
    s, t = s - 1, t - 1
    G = [{} for _ in range(N)]

    for _ in range(M):
        u, v, a, b = map(int, input().split())
        u, v = u - 1, v - 1
        G[u][v] = (a, b)    # (yen, snu)
        G[v][u] = (a, b)

    # Dijkstra
    ans = [0] * N
    # exchange at ith station
    # s to i
    q = PriorityQueue([(0, s)])  # (cost, id)
    vis = [False] * N
    while len(q):
        c, v = q.pop()
        if vis[v] is True:
            continue
        ans[v] = c
        vis[v] = True
        for n in G[v].keys():
            if vis[n] is True:
                continue
            q.push((c + G[v][n][0], n))    # pay by yen
    # i to t
    q = PriorityQueue([(0, t)])  # (cost, id)
    vis = [False] * N
    while len(q):
        c, v = q.pop()
        if vis[v] is True:
            continue
        ans[v] += c
        vis[v] = True
        for n in G[v].keys():
            if vis[n] is True:
                continue
            q.push((c + G[v][n][1], n))    # pay by snu

    # calc ans
    MONEY = pow(10, 15)
    for i in range(1, N):
        if ans[N - i] < ans[N - i - 1]:
            ans[N - i - 1] = ans[N - 1]
    print('\n'.join(map(lambda x: str(MONEY - x), ans)))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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


class PriorityQueue:
    def __init__(self, heap):
        self.heap = heap
        heapify(self.heap)

    def push(self, item):
        heappush(self.heap, item)

    def pop(self):
        return heappop(self.heap)

    def pushpop(self, item):
        return heappushpop(self.heap, item)

    def __call__(self):
        return self.heap

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


def main():

    N, M, s, t = map(int, input().split())
    s, t = s - 1, t - 1
    G = [{} for _ in range(N)]

    for _ in range(M):
        u, v, a, b = map(int, input().split())
        u, v = u - 1, v - 1
        G[u][v] = (a, b)    # (yen, snu)
        G[v][u] = (a, b)

    # Dijkstra
    ans = [0] * N
    # exchange at ith station
    # s to i
    q = PriorityQueue([(0, s)])  # (cost, id)
    vis = [False] * N
    while len(q):
        c, v = q.pop()
        ans[v] = c
        vis[v] = True
        for n in G[v].keys():
            if vis[n] is True:
                continue
            q.push((c + G[v][n][0], n))    # pay by yen
    # i to t
    q = PriorityQueue([(0, t)])  # (cost, id)
    vis = [False] * N
    while len(q):
        c, v = q.pop()
        ans[v] += c
        vis[v] = True
        for n in G[v].keys():
            if vis[n] is True:
                continue
            q.push((c + G[v][n][1], n))    # pay by snu

    # calc ans
    MONEY = pow(10, 15)
    for i in range(1, N):
        if ans[N - i] < ans[N - i - 1]:
            ans[N - i - 1] = ans[N - 1]
    print('\n'.join(map(lambda x: str(MONEY - x), ans)))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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


class PriorityQueue:
    def __init__(self, heap):
        self.heap = heap
        heapify(self.heap)

    def push(self, item):
        heappush(self.heap, item)

    def pop(self):
        return heappop(self.heap)

    def pushpop(self, item):
        return heappushpop(self.heap, item)

    def __call__(self):
        return self.heap

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


def main():

    N, M, s, t = map(int, input().split())
    s, t = s - 1, t - 1
    G = [{} for _ in range(N)]

    for _ in range(M):
        u, v, a, b = map(int, input().split())
        u, v = u - 1, v - 1
        G[u][v] = (a, b)    # (yen, snu)
        G[v][u] = (a, b)

    # Dijkstra
    ans = [0] * N
    for i in range(N):
        # exchange at ith station
        # s to i
        q = PriorityQueue([(0, s)])  # (cost, id)
        vis = [False] * N
        while len(q):
            c, v = q.pop()
            if v == i:
                ans[i] = c
                break
            vis[v] = True
            for n in G[v].keys():
                if vis[n] is True:
                    continue
                q.push((c + G[v][n][0], n))    # pay by yen
        # i to t
        q = PriorityQueue([(0, i)])  # (cost, id)
        vis = [False] * N
        while len(q):
            c, v = q.pop()
            if v == t:
                ans[i] += c
                break
            vis[v] = True
            for n in G[v].keys():
                if vis[n] is True:
                    continue
                q.push((c + G[v][n][1], n))    # pay by snu

    # calc ans
    MONEY = pow(10, 15)
    for i in range(1, N):
        if ans[N - i] < ans[N - i - 1]:
            ans[N - i - 1] = ans[N - 1]
    print('\n'.join(map(lambda x: str(MONEY - x), ans)))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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**10
  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 range(n):print(10**15-ans[i])

Submission status: Wrong Answer

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**10
  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: Wrong Answer

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)
    if dist[u] < cost:
      continue
    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-1, 1, -1):
  result[i-1] = min(result[i], result[i-1])

for i in range(n):
  print(money-result[i])

Submission status: Wrong Answer

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-1, 1, -1):
  result[i-1] = min(result[i], result[i-1])

for i in range(n):
  print(money-result[i])

Submission status: Wrong Answer

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 dist[v] < cost:
        continue
      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-1, 1, -1):
  result[i-1] = min(result[i], result[i-1])

for i in range(n):
  print(money-result[i])

Submission status: Wrong Answer

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 dist[v] < cost:
        continue
      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-1, 1, -1):
  result[i-1] = min(result[i], result[i])

for i in range(n):
  print(money-result[i])

Submission status: Wrong Answer

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

snuuk = dijkstra(snuuk_matrix, directed=False, indices=t)

Submission status: Wrong Answer

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)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

money = 10 ** 15
inf = float('inf')

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

edges = defaultdict(dict)
for i in range(1, M + 1):
    u, v, a, b = map(int, input().split())
    edges[u][v] = {"a": a, "b": b}
    edges[v][u] = {"a": a, "b": b}

costs_y = defaultdict(int)
costs_s = defaultdict(int)

def find_lowest_cost_node(costs, processed):
    lowest_cost = inf
    lowest_cost_node = None

    for node in costs:
        cost = costs[node]
        
        if cost < lowest_cost and node not in processed:
            lowest_cost = cost
            lowest_cost_node = node
    return lowest_cost_node

# Sから両替所候補となる各ノードへの円を使った最短距離を計算する
temp_processed = []
for i in range(1, N + 1):
    if i is S:
        costs_y[i] = 0
        temp_processed.append(i)
    else:
        costs_y[i] = inf


node = find_lowest_cost_node(costs_y, temp_processed)
while node is not None:
    cost = costs_y[node]
    neighbors = edges[node].keys()
    for n in neighbors:
        new_cost = cost + edges[node][n]["a"]
        if costs_y[n] > new_cost:
            costs_y[n] = new_cost
    temp_processed.append(node)
    node = find_lowest_cost_node(costs_y, temp_processed)

# 両替所候補となる各ノードからTへのスヌークを使った最短距離を計算する
temp_processed = []
for i in range(1, N + 1):
    if i is T:
        costs_s[i] = 0
        temp_processed.append(i)
    else:
        costs_s[i] = inf

node = find_lowest_cost_node(costs_s, temp_processed)
while node is not None:
    cost = costs_s[node]
    neighbors = edges[node].keys()
    for n in neighbors:
        new_cost = cost + edges[node][n]["b"]
        if costs_s[n] > new_cost:
            costs_s[n] = new_cost
    temp_processed.append(node)
    node = find_lowest_cost_node(costs_s, temp_processed)


# S->i + i->T の合計コスト
total_costs = []
for i in range(1, N + 1):
    total_costs.append(costs_y[i] + costs_s[i])

for i in range(N):
    print(money - min(total_costs[i:]))