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: Accepted

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

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


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

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

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


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

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

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


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


def main():
    n, m, s, t = spline()
    g_yen = Graph()
    g_snuuk = Graph()
    for _ in range(m):
        u, v, cost, b = spline()
        g_yen.add_edge(u, v, cost)
        g_snuuk.add_edge(u, v, b)
    d_s = Dijkstra(g_yen, s)
    d_t = Dijkstra(g_snuuk, t)
    costs = [0] * n
    costs[-1] = YEN - d_s.minimum_cost(n) - d_t.minimum_cost(n)
    for i in range(n - 2, -1, -1):
        cost = YEN - d_s.minimum_cost(i + 1) - d_t.minimum_cost(i + 1)
        costs[i] = max(cost, costs[i + 1])
    for cost in costs:
        print(cost)


if __name__ == "__main__":
    main()

Submission status: Accepted

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 - i]
    print('\n'.join(map(lambda x: str(MONEY - x), ans)))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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


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

# dijkstra
import heapq
def dijkstra(links, start, n):
    inf = 10**10
    d = [inf] * (n+1)
    d[start] = 0
    hq = []
    used = set()
    used.add(start)
    for i in links[start]:
        heapq.heappush(hq, i)
    while(hq):
        cost,i = heapq.heappop(hq)
        if( i in used):
            continue
        d[i] = cost
        used.add(i)
        for tmp in links[i]:
            cost_next, j = tmp
            if(not j in used):
                heapq.heappush(hq, (cost+cost_next, j))
    return d

d_e = dijkstra(links_e, s, n)
d_s = dijkstra(links_s, t, n)

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

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

Submission status: Accepted

Solution code:
# Save snuk

# 方針: sからiまでに円を用いて行く最小コストと、iからt(tから)iまでスヌークでいく最小コストを求める

import heapq

def dijkstra(n:int,graph,s):
    # n: ノード数
    # graph: エッジの {x0:[(w1,y1),(w2,y2),...],x1:[...]} リストの中はタプルにする
    # s: 基準となるノード ノードsからの最短距離を求める
    
    d = [float('inf')] * n  # ノードsからの距離
    notvisited = [True] * n # 訪れていない、すなわち決定していない頂点
    vertex_list = []        # 次に訪れる頂点の候補リスト

    # sに合わせて初期化
    d[s] = 0
    notvisited[s] = False
    [heapq.heappush(vertex_list,v) for v in graph[s]] # 候補リストの初期化

    while len(vertex_list):
        minedge = heapq.heappop(vertex_list) # 決定していない頂点のうちsからの距離が最小のものを基準とする
        vertex = minedge[1]
        if notvisited[vertex]:
            d[vertex] = minedge[0]
            notvisited[vertex] = False # 距離決定

            # 基準となる頂点からと連結している頂点をみて、次の頂点の候補リストを更新
            for e in graph[vertex]: 
                next_vertex = e[1]
                if notvisited[next_vertex]:
                    heapq.heappush(vertex_list,(d[vertex]+e[0],next_vertex)) # 候補リストに頂点を追加
    
    return d



n,m,s,t = map(int,input().split())
graph_a = {x:[] for x in range(n)}
graph_b = {x:[] for x in range(n)}
money = 10**15

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

d_a = dijkstra(n,graph_a,s-1) # sから円を使ったときの最短距離
d_b = dijkstra(n,graph_b,t-1) # tからスヌークを使ったときの最短距離

min_list = [float('inf')] * n # 最後からi番目以降で両替した場合の最小値
min_list[0] = d_a[-1] + d_b[-1]
for i in range(1,n):
    x = d_a[n-i-1] + d_b[n-i-1]
    if x < min_list[i-1]:
        min_list[i] = x
    else:
        min_list[i] = min_list[i-1]

for i in range(n):
    print(money-min_list[-(i+1)])

Submission status: Accepted

Solution code:
from heapq import heappop,heappush

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())
    G[u-1].append({"to":v-1, "yen":a, "snuuk":b})
    G[v-1].append({"to":u-1, "yen":a, "snuuk":b})

def dijkstra(sta:int, how:str):
    """
    頂点staから各頂点への最小コスト
    how: "yen" or "snuuk"
    """
    cost = [float("inf")] * N
    cost[sta] = 0
    que = [(0, sta)]

    while que:
        c,v = heappop(que)
        if cost[v] < c: continue
        for e in G[v]:
            if cost[e["to"]] > cost[v] + e[how]:
                cost[e["to"]] = cost[v] + e[how]
                heappush(que, (cost[e["to"]], e["to"]))
    
    return cost

# 頂点i - T をスヌークで移動
snuuk = dijkstra(T, "snuuk")
# S - 頂点i を円で移動
yen = dijkstra(S, "yen")

cost = [s + y for s,y in zip(snuuk,yen)]

ans = []
MINCOST = float("inf")
for year in range(N - 1, -1 ,-1):
    MINCOST = min(MINCOST, cost[year])
    ans.append(10 ** 15 - MINCOST)

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

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

N, M, S, T = map(int, input().split())
K = 10**15
S -= 1
T -= 1

edgesYen = [[] for _ in range(N)]
edgesSun = [[] for _ in range(N)]

for _ in range(M):
    fr, to, yen, sun = map(int, input().split())
    fr -= 1
    to -= 1
    edgesYen[fr].append((to, yen))
    edgesYen[to].append((fr, yen))
    edgesSun[fr].append((to, sun))
    edgesSun[to].append((fr, sun))

def calcMinDist(edges, start):
    minDist = [10**18] * N
    minDist[start] = 0
    que = [(0, start)]
    while que:
        dist, now = heappop(que)

        if minDist[now] < dist:
            continue

        for to, d in edges[now]:
            if minDist[to] > dist + d:
                heappush(que, (dist + d, to))
                minDist[to] = dist + d

    return minDist

minDistYenS = calcMinDist(edgesYen, S)
minDistSunT = calcMinDist(edgesSun, T)

ans = [0] * N
for mid in range(N):
    ans[mid] = K - minDistYenS[mid] - minDistSunT[mid]

for mid in range(N - 1)[::-1]:
    ans[mid] = max(ans[mid], ans[mid + 1])

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

Submission status: Accepted

Solution code:

from collections import defaultdict
from heapq import heappop, heappush
import sys
input=sys.stdin.readline

class Graph():

    def __init__(self):
        self.graph = defaultdict(list)

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

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra():

    def __init__(self, graph, start):
        self.g = graph.graph

        self.dist = defaultdict(lambda: float("inf"))
        self.dist[start] = 0

        self.prev = defaultdict(lambda: None)

        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            dist_u, u = heappop(self.Q)

            if self.dist[u] < dist_u:
                continue

            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):

        return self.dist[goal]

    def shortest_path(self, goal):
        path = []
        node = goal

        while node is not None:
            path.append(node)
            node = self.prev[node]

        return path[::-1]

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

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

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
import sys
input = sys.stdin.readline

def dijkstra(edges, size, source):
    distance = [float('inf')] * size
    distance[source] = 0
    visited = [False] * size
    pq = []
    heappush(pq, (0, source))
    while pq:
        dist_v, v = heappop(pq)
        visited[v] = True
        for u, weight in edges[v]:
            if not visited[u]:
                new_dist = dist_v + weight
                if distance[u] > new_dist:
                    distance[u] = new_dist
                    heappush(pq, (new_dist, u))
    return distance

n, m, s, t = map(int, input().split())
G_y = [[] for _ in range(n+1)]
G_s = [[] for _ in range(n+1)]
for _ in range(m):
    u, v, a, b = map(int, input().split())
    G_y[u].append((v, a))
    G_y[v].append((u, a))
    G_s[u].append((v, b))
    G_s[v].append((u, b))
dist_y = dijkstra(G_y, n+1, s)
dist_s = dijkstra(G_s, n+1, t)
ans = [0] * n
prev = 0
for i in range(1, n+1)[::-1]:
    amount = 10**15 - (dist_y[i] + dist_s[i])
    prev = max(prev, amount)
    ans[i-1] = prev
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
N,M,S,T = map(int,input().split())
S,T = S-1,T-1
UVAB = [tuple(map(int,input().split())) for i in range(M)]
es = [[] for _ in range(N)]
for u,v,a,b in UVAB:
    u,v = u-1,v-1
    es[u].append((v,a,b))
    es[v].append((u,a,b))

import heapq
INF = float('inf')
dy = [INF]*N
dy[S] = 0
hq = [(0,S)]
heapq.heapify(hq)
while hq:
    d,v = heapq.heappop(hq)
    for to,a,_ in es[v]:
        if d+a >= dy[to]: continue
        dy[to] = d+a
        heapq.heappush(hq, (d+a, to))
ds = [INF]*N
ds[T] = 0
hq = [(0,T)]
heapq.heapify(hq)
while hq:
    d,v = heapq.heappop(hq)
    for to,_,a in es[v]:
        if d+a >= ds[to]: continue
        ds[to] = d+a
        heapq.heappush(hq, (d+a, to))

ans = []
m = 0
for y,s in reversed(list(zip(dy,ds))):
    m = max(m, 10**15-y-s)
    ans.append(m)
ans.reverse()
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,m,s,t = LI()
    s -= 1
    t -= 1
    v = [[] for i in range(n)]
    for i in range(m):
        x,y,a,b = LI()
        x -= 1
        y -= 1
        v[x].append((y,a,b))
        v[y].append((x,a,b))
    d = [float("inf")]*n
    d[s] = 0
    q = [(0,s)]
    while q:
        dx,x = heappop(q)
        if d[x] < dx:
            continue
        for y,a,b in v[x]:
            nd = dx+a
            if nd < d[y]:
                d[y] = nd
                heappush(q,(nd,y))
    c = [float("inf")]*n
    c[t] = 0
    q = [(0,t)]
    while q:
        cx,x = heappop(q)
        if c[x] < cx:
            continue
        for y,a,b in v[x]:
            nc = cx+b
            if nc < c[y]:
                c[y] = nc
                heappush(q,(nc,y))
    s = float("inf")
    N = 10**15
    ans = []
    for i in range(n)[::-1]:
        s = min(s,d[i]+c[i])
        ans.append(N-s)
    for i in ans[::-1]:
        print(i)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from itertools import accumulate
def dijkstra(s,n,dic):
  q = [(0,s)]
  dist = [10**20]*n
  dist[s] = 0
  while q:
    v,p = heappop(q)
    if dist[p]<v:
      continue
    for e,c in dic[p]:
      if dist[e]>dist[p]+c:
        dist[e] = dist[p]+c
        heappush(q,(dist[e],e))
  return dist
N,M,s,t,*L = map(int, open(0).read().split())
Els = [[] for i in range(N+1)]
yEls = [[] for i in range(N+1)]
sEls = [[] for i in range(N+1)]
for u,v,a,b in zip(*[iter(L)]*4):
  sEls[u].append((v,b))
  sEls[v].append((u,b))
  yEls[u].append((v,a))
  yEls[v].append((u,a))

ydist = dijkstra(s,N+1,yEls)
sdist = dijkstra(t,N+1,sEls)
ls = list(accumulate((ydist[i]+sdist[i] for i in range(N,0,-1)),min))
for i in range(N-1,-1,-1):
  print(10**15-ls[i])

Submission status: Accepted

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

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

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

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

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

Submission status: Accepted

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

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


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


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


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

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


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


def dijkstra2(adj, start, n):
    MAX_VAL = float('inf')
    INF = MAX_VAL
    dist = [INF for _ in range(n)]
    dist[start] = 0
    pq = []
    heapq.heappush(pq, [dist[start], start])
    while pq:
        u_dist, u_id = heapq.heappop(pq)  # u is a tuple [u_dist, u_id]
        if u_dist == dist[u_id]:
            for v in adj[u_id]:
                w_uv = adj[u_id][v]
                if dist[u_id] + w_uv < dist[v]:
                    dist[v] = dist[u_id] + w_uv
                    heapq.heappush(pq, [dist[v], v])
    return dist


for u, v, a, b in uvab:
    u = u - 1
    v = v - 1
    jpy_cost[u][v] = a
    jpy_cost[v][u] = a
    snuke_cost[u][v] = b
    snuke_cost[v][u] = b

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

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
import sys

input = sys.stdin.readline

def Dijkstra_heap(s, edge):
    d = [10 ** 20] * n
    used = [False] * n
    d[s] = 0
    used[s] = True
    edgelst = []
    for i, j in edge[s]:
        heappush(edgelst, i+j*(10**6))
    while edgelst:
        edgemin = heappop(edgelst)
        v = edgemin % (10**6)
        if used[v]: continue
        d[v] = edgemin // (10**6)
        used[v] = True
        for e in edge[v]:
            if not used[e[0]]:
                heappush(edgelst, e[0]+(e[1]+d[v])*(10**6))
    return d

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

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

cos1 = Dijkstra_heap(s-1, Yen)
cos2 = Dijkstra_heap(t-1, Snk)

ans = 0
ANS = []
ANS_append = ANS.append
for yen,snk in zip(cos1[::-1], cos2[::-1]):
  tmp = 10**15-(yen+snk)
  ans = max(ans, tmp)
  ANS_append(ans)
print(*ANS[::-1], sep='\n')

Submission status: Accepted

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**17
  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: Accepted

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

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

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

Submission status: Accepted

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

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

import heapq

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

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

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

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

Submission status: Accepted

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

import numpy as np
from heapq import heappush, heappop

N,M,S,T, *uvab = map(int,input().split())
graph = [[] for _ in range(N+1)]
for u,v,a,b in zip(*[iter(uvab)]*4):
    graph[u].append((v,a,b))
    graph[v].append((u,a,b))

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

d1 = np.array(dijkstra(S,0))
d2 = np.array(dijkstra(T,1))

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

Submission status: Accepted

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

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import namedtuple
from heapq import heappush, heappop


INF = sys.maxsize
Edge = namedtuple('Edge', 'to yen snuuk')
Vertex = namedtuple('Vertex', 'cost id')

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

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

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

costs_in_yen = [INF] * (n + 1)
costs_in_snuuk = [INF] * (n + 1)

q = []

heappush(q, Vertex(0, s))
costs_in_yen[s] = 0

while q:
  v = heappop(q)
  if v.cost > costs_in_yen[v.id]:
    continue
  for edge in edges[v.id]:
    if v.cost + edge.yen < costs_in_yen[edge.to]:
      costs_in_yen[edge.to] = v.cost + edge.yen
      heappush(q, Vertex(costs_in_yen[edge.to], edge.to))
      
heappush(q, Vertex(0, t))
costs_in_snuuk[t] = 0

while q:
  v = heappop(q)
  if v.cost > costs_in_snuuk[v.id]:
    continue
  for edge in edges[v.id]:
    if v.cost + edge.snuuk < costs_in_snuuk[edge.to]:
      costs_in_snuuk[edge.to] = v.cost + edge.snuuk
      heappush(q, Vertex(costs_in_snuuk[edge.to], edge.to))      

# DPっぽく結果を記録しながら解いていく
# n - 1 年後からはじめて0年後まで遡っていく

# n 年後の手持ち snuuk の最大額
snuuk_in_hand = [0] * (n + 1)

# 現在に近づくにつれて、利用できる両替所が毎年ひとつずつ増えていく、と考える
# 新しく増えた両替所で両替したほうがお得であればdpテーブルを更新する
for i in range(n, 0, -1):  
  # 例: 3年後の最大金額は4年後の最大金額と都市4で両替した場合の所持金額のどちらか大きい方
  snuuk_in_hand[i - 1] = max(
    snuuk_in_hand[i],
    # 最初の所持金 - スタートから都市iまでの費用（yen) - 都市iからゴールまでの費用(snuuk）
    10**15 - costs_in_yen[i] - costs_in_snuuk[i]
  )

for i in range(0, n):
  print(snuuk_in_hand[i])