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:
def resolve():
    import sys
    input = sys.stdin.readline
    import heapq
    def dijkstra_heap(s,edge):
        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

    n,m,s,t = map(int,input().split())
    edge1 = [[] for i in range(n)]
    edge2 = [[] for i in range(n)]
    for i in range(m):
        u,v,a,b= map(int,input().split())
        edge1[u-1].append([a,v-1])
        edge1[v-1].append([a,u-1])
        edge2[u-1].append([b,v-1])
        edge2[v-1].append([b,u-1])
    d1=dijkstra_heap(s-1,edge1)
    d2=dijkstra_heap(t-1,edge2)
    ma,ans=0,[]
    for c1,c2 in zip(d1[::-1],d2[::-1]):
        ma=max(ma,10**15-c1-c2)
        ans.append(ma)
    for i in ans[::-1]:print(i)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

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


class Graph(object):
    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(object):

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

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        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]

n,m,s,t = map(int, input().split())
uvab = [list(map(int, input().split())) for i in range(m)]
Ga = Graph()
Gb = Graph()
for u,v,a,b in uvab:
  Ga.add_edge(u-1,v-1,a)
  Ga.add_edge(v-1,u-1,a)
  Gb.add_edge(u-1,v-1,b)
  Gb.add_edge(v-1,u-1,b)
dist_a = Dijkstra(Ga,s-1)
dist_b = Dijkstra(Gb,t-1)
cost = 10 ** 18
money = 10 ** 15
ans = []
for i in range(n-1,-1,-1):
  tmp = dist_a.shortest_distance(i) + dist_b.shortest_distance(i)
  cost = min(cost, tmp)
  ans.append(cost)
for i in reversed(ans):
  print(money - i)

Submission status: Accepted

Solution code:
def main():
    import collections
    import heapq

    class Dijkstra:
        def __init__(self):
            self.e = collections.defaultdict(list)

        def add(self, u, v, d):  # 無向グラフの場合
            self.e[u].append([v, d])
            self.e[v].append([u, d])

        def delete(self, u, v):
            self.e[u] = [_ for _ in self.e[u] if _[0] != v]
            self.e[v] = [_ for _ in self.e[v] if _[0] != u]

        def search(self, s):  # d[i]はsからiまでの最短距離
            d = collections.defaultdict(lambda: float('inf'))
            d[s] = 0
            q = []
            heapq.heappush(q, (0, s))
            v = collections.defaultdict(bool)
            while len(q):
                k, u = heapq.heappop(q)
                if v[u]:
                    continue
                v[u] = True

                for uv, ud in self.e[u]:
                    if v[uv]:
                        continue
                    vd = k + ud
                    if d[uv] > vd:
                        d[uv] = vd
                        heapq.heappush(q, (vd, uv))

            return d

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

    G1 = Dijkstra()
    G2 = Dijkstra()

    for i in range(m):
        G1.add(data[i][0], data[i][1], data[i][2])
        G2.add(data[i][0], data[i][1], data[i][3])

    D1 = G1.search(s)
    D2 = G2.search(t)

    A = []

    for i in range(1, n + 1):
        A.append((D1[i] + D2[i], i))

    A.sort()

    b = 0
    for i in range(n):
        if i == 0:
            print(10 ** 15 - A[i][0])
        elif i < A[b][1]:
            print(10 ** 15 - A[b][0])
        else:
            while i >= A[b][1]:
                b += 1
            print(10 ** 15 - A[b][0])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq
INF = 10 ** 16


def dijkstra(n, town, k, start):
    d = []
    queue = []
    for i in range(n):
        d.append(INF)
    d[start] = 0
    heapq.heappush(queue, (0, start))
    # 都市kで交換した時の円またはスヌークのの最小値
    while len(queue) != 0:
        distance, v = heapq.heappop(queue)
        if d[v] < distance:
            continue
        for u in range(len(town[v])):
            if d[town[v][u][0]] > d[v] + town[v][u][k]:
                d[town[v][u][0]] = d[v] + town[v][u][k]
                heapq.heappush(queue, (d[town[v][u][0]], town[v][u][0]))

    return d


def main():
    n, m, s, t = map(int, input().split())
    s -= 1
    t -= 1
    money = 10 ** 15
    town = []

    for i in range(n):
        town.append([])
    for i in range(m):
        fro, to, a, b = map(int, input().split())
        fro -= 1
        to -= 1
        town[fro].append((to, a, b))
        town[to].append((fro, a, b))

    a = dijkstra(n, town, 1, s)
    b = dijkstra(n, town, 2, t)

    total = []
    for i in range(n):
        heapq.heappush(total, (a[i] + b[i], i + 1))
    mon, year = heapq.heappop(total)
    for i in range(n):
        while year <= i:
            mon, year = heapq.heappop(total)
        print(money - mon)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from heapq import heapify, heappop, heappush


def dijkstra(n, train, start):
    d = []
    queue = []
    INF = 10 ** 16
    for i in range(n):
        d.append(INF)
    d[start] = 0
    heapify(queue)
    heappush(queue, (0, start))
    # 都市kに行く時の円またはスヌークのの最小値
    while len(queue) != 0:
        distance, v = heappop(queue)
        if d[v] < distance:
            continue
        for u in range(len(train[v])):
            if d[train[v][u][0]] > d[v] + train[v][u][1]:
                d[train[v][u][0]] = d[v] + train[v][u][1]
                heappush(queue, (d[train[v][u][0]], train[v][u][0]))
    return d


def main():
    n, m, s, t = map(int, input().split())
    s -= 1
    t -= 1
    money = 10 ** 15
    train_en = []
    train_snuuk = []

    for i in range(n):
        train_en.append([])
        train_snuuk.append([])
    for i in range(m):
        fro, to, a, b = map(int, input().split())
        fro -= 1
        to -= 1
        train_en[fro].append((to, a))
        train_en[to].append((fro, a))
        train_snuuk[fro].append((to, b))
        train_snuuk[to].append((fro, b))

    a = dijkstra(n, train_en, s)
    b = dijkstra(n, train_snuuk, t)

    cost_sum = []
    for i in range(n):
        cost_sum.append((a[i] + b[i], i + 1))
    heapify(cost_sum)
    m, y = heappop(cost_sum)
    for i in range(n):
        while y <= i:
            m, y = heappop(cost_sum)
        print(money - m)


if __name__ == '__main__':
    main()

Submission status: Accepted

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


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    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(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

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

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        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):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]


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

    g_yen = Graph()
    g_snuuk = Graph()

    for train in trains:
        u, v, a, b = train
        g_yen.add_edge(u, v, a)
        g_yen.add_edge(v, u, a)
        g_snuuk.add_edge(u, v, b)
        g_snuuk.add_edge(v, u, b)

    d_yen = Dijkstra(g_yen, s)
    d_snuuk = Dijkstra(g_snuuk, t)

    cost_sum = []
    for i in range(1, n+1):
        cost_sum.append([d_yen.dist[i] + d_snuuk.dist[i], i])

    heapify(cost_sum)
    c, l = heappop(cost_sum)
    for i in range(n):
        while l<=i:
            c, l = heappop(cost_sum)
        print(10**15 - c)


if __name__ == '__main__':
     main()

Submission status: Accepted

Solution code:
import heapq

def pcc(src, adj):
	pq = [(0,src)]
	dist = [float('inf')]*n
	dist[src] = 0
	heapq.heapify(pq)
	while pq:
		d, u = heapq.heappop(pq)
		for w, v in adj[u]:
			if dist[v] > dist[u] + w:
				dist[v] = dist[u] + w
				heapq.heappush(pq, (dist[v], v))
	return dist

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

dist_s = pcc(s, adjs)
dist_t = pcc(t, adjt)

ans = [0]*n
ans[n-1] = 10**15 - dist_s[n-1]-dist_t[n-1]
for i in range(n-2,-1,-1):
	ans[i] = max(ans[i+1], 10**15 - dist_s[i] - dist_t[i])
print(*ans, sep = "\n")

Submission status: Accepted

Solution code:
import heapq
INF = float('inf')
yen = 10**15
def pcc(src, adj):
	pq = [(0,src)]
	heapq.heapify(pq)
	dist = [INF]*n
	dist[src] = 0
	while pq:
		d,u = heapq.heappop(pq)
		if d>dist[u]:continue
		for w, v in adj[u]:
			if dist[v] > dist[u] + w:
				dist[v] = dist[u] + w
				heapq.heappush(pq, (dist[v], v))
	return dist

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

dist_s = pcc(s,adjs)
dist_t = pcc(t,adjt)
ans = [0]*(n)
ans[n-1] = yen -dist_s[n-1] - dist_t[n-1]
for i in range(n-2,-1,-1):
	ans[i] = max(ans[i+1], yen - dist_s[i] - dist_t[i])
print(*ans, sep = '\n')

Submission status: Accepted

Solution code:
import heapq
def dijkstra(s, neighbor):
	dist = [float('inf')] * N
	dist[s] = 0
	que = [(0, s)]
	heapq.heapify(que)
	while que:
		d, v = heapq.heappop(que)
		if d > dist[v]:
			continue
		for u, l in neighbor[v]:
			tmp_d = d + l
			if tmp_d < dist[u]:
				dist[u] = tmp_d
				heapq.heappush(que, (tmp_d, u))
	return dist
 
N, M, s, t = map(int, input().split())
yen = [[] for _ in range(N)]
snuuk = [[] for _ in range(N)]
for _ in range(M):
	u, v, a, b = map(int, input().split())
	yen[u-1].append((v-1, a))
	yen[v-1].append((u-1, a))
	snuuk[u-1].append((v-1, b))
	snuuk[v-1].append((u-1, b))
 
dist_s = dijkstra(s-1, yen)
dist_t = dijkstra(t-1, snuuk)
ans = [-1] * N
tmp = float('inf')
for i in range(N-1, -1, -1):
	if dist_s[i] + dist_t[i] < tmp:
		tmp = dist_s[i] + dist_t[i]
	ans[i] = 10 ** 15 - tmp
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
import heapq
INF = 10**18
def dijkstra(s, edge, n):
    d = [INF] * n
    used = [True] * n #True: not used
    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
 
n, m, s, t = map(int, input().split())
s -= 1
t -= 1
graph_a = [[] for _ in range(n)]
graph_b = [[] for _ in range(n)]
for i in range(m):
    u, v, a, b = map(int, input().split())
    u, v = 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))
 
yen = dijkstra(s, graph_a, n)
snu = dijkstra(t, graph_b, n)

cost = [0] * n
for i in range(n):
    cost[i] = (yen[i] + snu[i],i)

heapq.heapify(cost)
c = -1
aaa = 10 ** 15
for i in range(n):
    if c < i:
        while cost:
            nn, t = heapq.heappop(cost)
            if t >= i:
                c = t
                break
    print(aaa - nn)

Submission status: Accepted

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**15-c)
main()

Submission status: Accepted

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

import heapq
INF = 10**18
def dijkstra_heap(s, edge, n):
    d = [INF] * n
    used = [True] * n #True: not used
    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

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

    d1 = dijkstra_heap(s, edge1, n)
    d2 = dijkstra_heap(t, edge2, n)
    #print(d1)
    #print(d2)
    C = [0]*n
    for i in range(n):
        C[i] = (d1[i]+d2[i], i)
    heapq.heapify(C)
    cur = -1
    for i in range(n):
        if cur < i:
            while C:
                x, t = heapq.heappop(C)
                if t >= i:
                    cur = t
                    break
        #print(cur)
        print(10**15-x)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
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))
    edgesYen[v].append((u,a))
    edgesSnuuk[u].append((v,b))
    edgesSnuuk[v].append((u,b))


def dijkstra(edges,costDic,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))
#都市sから各都市に円で行く場合の最小コストを求める。
costYen = {}
que1 = [(0,s)]
heapq.heapify(que1)
dijkstra(edgesYen,costYen,que1)

costSnuuk = {}
que2 = [(0,t)]
heapq.heapify(que2)
dijkstra(edgesSnuuk,costSnuuk,que2)


minimumCosts = []
for i in range(1,n+1):
    cost = costYen[i] + costSnuuk[i]
    minimumCosts.append((cost,i))
heapq.heapify(minimumCosts)

money = 10**15
tmp = heapq.heappop(minimumCosts)
for i in range(n):
    while tmp[1] <= i:
        tmp = heapq.heappop(minimumCosts)
    print(money-tmp[0])

Submission status: Accepted

Solution code:
'''
1つの始点から全頂点への最短距離を求めるアルゴリズム
辺の数E,頂点の数Vに対し、O((E+V)log(V))
edge[u]=[(d1, v1), (d2, v2), ...]が頂点uと頂点viに距離diの辺があることを表す隣接リストが入力
無向グラフにて検証済み。有効グラフのたぶんいけるので確認したらここを書き換えて欲しい。
'''

from heapq import heappush, heappop

INF = 10**15
 
def dijkstra(s, edges):
    n = len(edges)
    que = []
    d = [INF] * n
    d[s] = 0
    heappush(que, (0, s))

    while len(que) > 0:
        (c, v) = heappop(que)
        if d[v] < c:
            continue
        for (cc, w) in edges[v]:
            if d[w] > d[v] + cc:
                d[w] = d[v] + cc
                heappush(que, (d[w], w))

    return d

n, m, s, t = map(int, input().split())
s, t = s-1, t-1
yen_edge = [[] for i in range(n)]
snook_edge = [[] for i in range(n)]
for i in range(m):
    ui, vi, ai, bi = map(int, input().split())
    ui, vi = vi-1, ui-1
    yen_edge[ui].append((ai, vi))
    yen_edge[vi].append((ai, ui))
    snook_edge[ui].append((bi, vi))
    snook_edge[vi].append((bi, ui))

distance_yen = dijkstra(s, yen_edge)
distance_snook = dijkstra(t, snook_edge)

ans_lst = [0 for i in range(n)]
temp_min = 10**15
for i in range(n)[::-1]:
    now = distance_yen[i] + distance_snook[i]
    temp_min = min(temp_min, now)
    ans_lst[i] = 10**15 - temp_min

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

Submission status: Accepted

Solution code:
'''
1つの始点から全頂点への最短距離を求めるアルゴリズム
辺の数E,頂点の数Vに対し、O((E+V)log(V))
edge[u]=[(d1, v1), (d2, v2), ...]が頂点uと頂点viに距離diの辺があることを表す隣接リストが入力
無向グラフにて検証済み。有効グラフのたぶんいけるので確認したらここを書き換えて欲しい。
'''

from heapq import heappush, heappop

INF = 10**15
 
def dijkstra(s, edges):
    que = []
    d = [INF] * n
    d[s] = 0
    heappush(que, (0, s))

    while len(que) > 0:
        (c, v) = heappop(que)
        if d[v] < c:
            continue
        for (cc, w) in edges[v]:
            if d[w] > d[v] + cc:
                d[w] = d[v] + cc
                heappush(que, (d[w], w))

    return d

n, m, s, t = map(int, input().split())
s, t = s-1, t-1
yen_edge = [[] for i in range(n)]
snook_edge = [[] for i in range(n)]
for i in range(m):
    ui, vi, ai, bi = map(int, input().split())
    ui, vi = vi-1, ui-1
    yen_edge[ui].append((ai, vi))
    yen_edge[vi].append((ai, ui))
    snook_edge[ui].append((bi, vi))
    snook_edge[vi].append((bi, ui))

distance_yen = dijkstra(s, yen_edge)
distance_snook = dijkstra(t, snook_edge)

ans_lst = [0 for i in range(n)]
temp_min = 10**15
for i in range(n)[::-1]:
    now = distance_yen[i] + distance_snook[i]
    temp_min = min(temp_min, now)
    ans_lst[i] = 10**15 - temp_min

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

Submission status: Accepted

Solution code:
n,m,s,t=map(int,input().split())
edge=[[] for i in range(n+1)]
edge2=[[] for i in range(n+1)]
for i in range(m):
    a,b,c,d=map(int,input().split())
    edge[a].append((b,c))
    edge[b].append((a,c))
    edge2[a].append((b,d))
    edge2[b].append((a,d))
from heapq import *
def dijkstra(s,n):
    d = [float('inf') for i in range(n+1)]
    pq = []
    d[s]=0
    heappush(pq,(0,s))
    while pq:
        dist,u = heappop(pq)
        for v,cost in edge[u]:
            if d[v]<=dist+cost:
                continue
            d[v]=dist+cost
            heappush(pq,(d[v],v))
    return d
ds=dijkstra(s,n)
edge=edge2
dt=dijkstra(t,n)
ans=[10**15 for i in range(n+1)]
for i in range(n):
    ans[i]=ds[i+1]+dt[i+1]
for i in range(n-1,-1,-1):
    ans[i]=min(ans[i],ans[i+1])
for i in range(n):
    print(10**15-ans[i])

Submission status: Accepted

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

N, M, S, T = map(int, input().split())
edge = [[] for _ in range(N + 1)]
for _ in range(M):
    x, y, a, b = map(int, input().split())
    edge[x].append((y, a, b))
    edge[y].append((x, a, b))


def dijkstra(start, currency):
    # currency=0 -> yen, 1 -> snuuk
    dist = [inf] * (N + 1)
    dist[start] = 0
    que = [(0, start)]
    while que:
        c, s = heapq.heappop(que)
        if dist[s] < c:
            continue
        for t, *cost in edge[s]:
            cost = cost[currency]
            if dist[t] > dist[s] + cost:
                dist[t] = dist[s] + cost
                heapq.heappush(que, (dist[t], t))
    return dist


s_to_i_yen = dijkstra(S, 0)
t_to_i_snu = dijkstra(T, 1)
need = [(x + y, i) for i, (x, y) in enumerate(zip(s_to_i_yen, t_to_i_snu))]
need.sort(reverse=True)

money = 10 ** 15
for y in range(N):
    while need[-1][1] <= y:
        need.pop()
    print(money-need[-1][0])

Submission status: Accepted

Solution code:
import heapq
n, m, s, t = map(int, input().split())
edges_yen = [[]for _ in range(n)]
edges_snuuk = [[]for _ in range(n)]
for _ in range(m):
    u, v, a, b = map(int, input().split())
    edges_yen[u-1].append((a, v-1))
    edges_yen[v-1].append((a, u-1))
    edges_snuuk[u-1].append((b, v-1))
    edges_snuuk[v-1].append((b, u-1))


def dijkstra(init_v, edges):
    next_v = [(0, init_v)]
    INF = 10**18
    dist = [INF]*n
    dist[init_v] = 0
    while next_v:
        d, v = heapq.heappop(next_v)
        if dist[v] < d:
            continue
        for d, v2 in edges[v]:
            if dist[v2] <= dist[v]+d:
                continue
            dist[v2] = dist[v]+d
            heapq.heappush(next_v, (dist[v2], v2))
    return dist


dist_yen = dijkstra(s-1, edges_yen)
dist_snuuk = dijkstra(t-1, edges_snuuk)
dist = [x+y for x, y in zip(dist_yen, dist_snuuk)]
ans = []
INF = 10**18
MIN = INF
for x in dist[::-1]:
    if x < MIN:
        MIN = x
    ans.append(MIN)
for x in ans[::-1]:
    print(10**15-x)

Submission status: Accepted

Solution code:
import heapq
n, m, s, t = map(int, input().split())
edges_yen = [[]for _ in range(n)]
edges_snuuk = [[]for _ in range(n)]
for _ in range(m):
    u, v, a, b = map(int, input().split())
    edges_yen[u-1].append((a, v-1))
    edges_yen[v-1].append((a, u-1))
    edges_snuuk[u-1].append((b, v-1))
    edges_snuuk[v-1].append((b, u-1))


def dijkstra(init_v, edges):
    next_v = [(0, init_v)]
    INF = 10**18
    dist = [INF]*n
    dist[init_v] = 0
    while next_v:
        d, v = heapq.heappop(next_v)
        if dist[v] < d:
            continue
        for d, v2 in edges[v]:
            if dist[v2] <= dist[v]+d:
                continue
            dist[v2] = dist[v]+d
            heapq.heappush(next_v, (dist[v2], v2))
    return dist


dist_yen = dijkstra(s-1, edges_yen)
dist_snuuk = dijkstra(t-1, edges_snuuk)

ans = []
INF = 10**18
min_c = INF
for x, y in zip(dist_yen[::-1], dist_snuuk[::-1]):
    if x+y < min_c:
        min_c = x+y
    ans.append(10**15-min_c)
print(*ans[::-1], sep='\n')

Submission status: Accepted

Solution code:
import heapq
n, m, s, t = map(int, input().split())
edges_yen = [[]for _ in range(n)]
edges_snuuk = [[]for _ in range(n)]
for _ in range(m):
    u, v, a, b = map(int, input().split())
    edges_yen[u-1].append((a, v-1))
    edges_yen[v-1].append((a, u-1))
    edges_snuuk[u-1].append((b, v-1))
    edges_snuuk[v-1].append((b, u-1))


def dijkstra(init_v, edges):
    next_v = [(0, init_v)]
    INF = 10**18
    dist = [INF]*n
    dist[init_v] = 0
    while next_v:
        d, v = heapq.heappop(next_v)
        if dist[v] < d:
            continue
        for d, v2 in edges[v]:
            if dist[v2] <= dist[v]+d:
                continue
            dist[v2] = dist[v]+d
            heapq.heappush(next_v, (dist[v2], v2))
    return dist


dist_yen = dijkstra(s-1, edges_yen)
dist_snuuk = dijkstra(t-1, edges_snuuk)
dist = [x+y for x, y in zip(dist_yen, dist_snuuk)]
ans = []
INF = 10**18
MIN = INF
for x in dist[::-1]:
    if x < MIN:
        MIN = x
    ans.append(MIN)
for x in ans[::-1]:
    print(10**15-x)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline

    import heapq


    INF = 10 ** 15

    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([a, v])
        G_y[v].append([a, u])

        G_s[u].append([b, v])
        G_s[v].append([b, u])


    def dijksrea(s, G): #始点s, 隣接グラフG
        d = [INF] * (N + 1)
        d[s] = 0 #始点の距離を0にする
        pque = []
        heapq.heappush(pque, [0, s]) #要素を[距離、頂点]として管理　最初の位置を入れる

        while len(pque) != 0: #queの中に要素が残っている時
            p = heapq.heappop(pque) #最も距離が短いものを取り出す
            v = p[1] #距離が最も短い頂点
            if d[v] < p[0]: #取り出した値より既に小さい値がdに入っているときは無視して次へ
                continue
            for i in range(len(G[v])): #頂点vの隣接リストを走査
                e = G[v][i]
                if d[e[1]] > d[v] + e[0]: #距離が更新できるかを検討
                    d[e[1]] = d[v] + e[0]
                    heapq.heappush(pque, [d[e[1]], e[1]]) #更新できた場合、その値をpqueに入れる
        
        return d

    d_y = dijksrea(S, G_y)
    d_s = dijksrea(T, G_s)

    # print (d_y)
    # print (d_s)

    ans = [0] * (N + 1)
    for i in range(N, 0, -1): #交換する場所をどこにするか
        tmp = INF - d_y[i] - d_s[i]
        ans[i] = max(ans[i], tmp)
        ans[i - 1] = ans[i]

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

if __name__ == '__main__':
    main()

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')
cy = [INF] * N
cy[S] = 0
hq = [(0,S)]
heapq.heapify(hq)
while hq:
    c,v = heapq.heappop(hq)
    for to,a,_ in es[v]:
        if c+a >= cy[to]: continue
        cy[to] = c+a
        heapq.heappush(hq, (c+a, to))
cs = [INF] * N
cs[T] = 0
hq = [(0,T)]
heapq.heapify(hq)
while hq:
    c,v = heapq.heappop(hq)
    for to,_,b in es[v]:
        if c+b >= cs[to]: continue
        cs[to] = c+b
        heapq.heappush(hq, (c+b, to))

ans = [-1] * N
minc = INF
for i,(y,s) in reversed(list(enumerate(zip(cy,cs)))):
    minc = min(minc, y+s)
    ans[i] = 10**15 - minc
print(*ans, sep='\n')