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:
import sys
fin = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush


def initialize(adj, s):
    MAX_NUM = float('inf')
    parent = {s: None}
    d = {vertex: MAX_NUM for vertex in adj.keys()}
    d[s] = 0
    return d, parent


def initialize_int(adj, s):
    """
    assume that all vertex in {0, 1, 2, ..., N - 1}
    """
    N = len(adj)
    MAX_NUM = float('inf')
    d = [MAX_NUM] * N
    d[s] = 0
    parent = [None] * N
    return d, parent


# Dijkstra can work using a minheap which does not have decrease_key.
# and also we do not have to implement Vertex class.
# Instead, we can use (distance, vertex).
# in this case, the time it takes is O(ElgE).
# E is at most O(V^2), thus O(ElgE) = O(ElgV).
def dijkstra_simple(adj, w, s):
    d, parent = initialize_int(adj, s)
    priority_queue = []
    heappush(priority_queue, (d[s], s))
    while priority_queue:
        distance, source = heappop(priority_queue) 
        for neighbor in adj[source]:
            new_distance = distance + w[(source, neighbor)]
            if new_distance < d[neighbor]:
                d[neighbor] = new_distance
                parent[neighbor] = source
                heappush(priority_queue, (new_distance, neighbor))
    return d


n, m, s, t = [int(elem) for elem in fin().split()]
s -= 1
t -= 1
adj = [[] for _ in range(n)]
yen_weights = dict()
snuuk_weights = dict()
for _ in range(m):
    u, v, a, b = [int(elem) for elem in fin().split()]
    u -= 1
    v -= 1
    for v1, v2 in [(u, v), (v, u)]:
        adj[v1].append(v2)
        yen_weights[(v1, v2)] = a
        snuuk_weights[(v1, v2)] = b

d_yen = dijkstra_simple(adj, yen_weights, s)
d_snuuk = dijkstra_simple(adj, snuuk_weights, t)
min_cost = float('inf')
min_cost_after_each_year_reversed = []
for vertex in reversed(range(n)):
    min_cost = min(min_cost, d_yen[vertex] + d_snuuk[vertex])
    min_cost_after_each_year_reversed.append(min_cost)

initial_money = 10**15
for cost in reversed(min_cost_after_each_year_reversed):
    print(initial_money - cost)

Submission status: Accepted

Solution code:
import sys
fin = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush


def initialize(adj, s):
    MAX_NUM = float('inf')
    parent = {s: None}
    d = {vertex: MAX_NUM for vertex in adj.keys()}
    d[s] = 0
    return d, parent


def initialize_int(adj, s):
    """
    assume that all vertex in {0, 1, 2, ..., N - 1}
    """
    N = len(adj)
    MAX_NUM = float('inf')
    d = [MAX_NUM] * N
    d[s] = 0
    parent = [None] * N
    return d, parent


# Dijkstra can work using a minheap which does not have decrease_key.
# and also we do not have to implement Vertex class.
# Instead, we can use (distance, vertex).
# in this case, the time it takes is O(ElgE).
# E is at most O(V^2), thus O(ElgE) = O(ElgV).
def dijkstra_simple(adj, w, s):
    d, parent = initialize_int(adj, s)
    priority_queue = []
    heappush(priority_queue, (d[s], s))
    while priority_queue:
        distance, source = heappop(priority_queue) 
        for neighbor in adj[source]:
            new_distance = distance + w[(source, neighbor)]
            if new_distance < d[neighbor]:
                d[neighbor] = new_distance
                parent[neighbor] = source
                heappush(priority_queue, (new_distance, neighbor))
    return d


n, m, s, t = [int(elem) for elem in fin().split()]
s -= 1
t -= 1
adj = defaultdict(list)
yen_weights = dict()
snuuk_weights = dict()
for _ in range(m):
    u, v, a, b = [int(elem) for elem in fin().split()]
    u -= 1
    v -= 1
    for v1, v2 in [(u, v), (v, u)]:
        adj[v1].append(v2)
        yen_weights[(v1, v2)] = a
        snuuk_weights[(v1, v2)] = b

d_yen = dijkstra_simple(adj, yen_weights, s)
d_snuuk = dijkstra_simple(adj, snuuk_weights, t)
min_cost = float('inf')
min_cost_after_each_year_reversed = []
for vertex in reversed(range(n)):
    min_cost = min(min_cost, d_yen[vertex] + d_snuuk[vertex])
    min_cost_after_each_year_reversed.append(min_cost)

initial_money = 10**15
for cost in reversed(min_cost_after_each_year_reversed):
    print(initial_money - cost)

Submission status: Accepted

Solution code:
import sys
fin = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush


def initialize(adj, s):
    MAX_NUM = float('inf')
    parent = {s: None}
    d = {vertex: MAX_NUM for vertex in adj.keys()}
    d[s] = 0
    return d, parent


# Dijkstra can work using a minheap which does not have decrease_key.
# and also we do not have to implement Vertex class.
# Instead, we can use (distance, vertex).
# in this case, the time it takes is O(ElgE).
# E is at most O(V^2), thus O(ElgE) = O(ElgV).
def dijkstra_simple(adj, w, s):
    d, parent = initialize(adj, s)
    priority_queue = []
    heappush(priority_queue, (d[s], s))
    while priority_queue:
        distance, source = heappop(priority_queue) 
        for neighbor in adj[source]:
            new_distance = distance + w[(source, neighbor)]
            if new_distance < d[neighbor]:
                d[neighbor] = new_distance
                parent[neighbor] = source
                heappush(priority_queue, (new_distance, neighbor))
    return d


n, m, s, t = [int(elem) for elem in fin().split()]
adj = defaultdict(list)
yen_weights = dict()
snuuk_weights = dict()
for _ in range(m):
    u, v, a, b = [int(elem) for elem in fin().split()]
    for v1, v2 in [(u, v), (v, u)]:
        adj[v1].append(v2)
        yen_weights[(v1, v2)] = a
        snuuk_weights[(v1, v2)] = b

d_yen = dijkstra_simple(adj, yen_weights, s)
d_snuuk = dijkstra_simple(adj, snuuk_weights, t)
min_cost = float('inf')
min_cost_after_each_year_reversed = []
for vertex in range(n, 0, -1):
    min_cost = min(min_cost, d_yen[vertex] + d_snuuk[vertex])
    min_cost_after_each_year_reversed.append(min_cost)

initial_money = 10**15
for cost in reversed(min_cost_after_each_year_reversed):
    print(initial_money - cost)

Submission status: Accepted

Solution code:
import sys
fin = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush


def initialize(adj, s):
    MAX_NUM = float('inf')
    parent = {s: None}
    d = {vertex: MAX_NUM for vertex in adj.keys()}
    d[s] = 0
    return d, parent


# Dijkstra can work using a minheap which does not have decrease_key.
# and also we do not have to implement Vertex class.
# Instead, we can use (distance, vertex).
# in this case, the time it takes is O(ElgE).
# E is at most O(V^2), thus O(ElgE) = O(ElgV).
def dijkstra_simple(adj, w, s):
    d, parent = initialize(adj, s)
    priority_queue = []
    heappush(priority_queue, (d[s], s))
    while priority_queue:
        distance, source = heappop(priority_queue) 
        for neighbor in adj[source]:
            new_distance = distance + w[(source, neighbor)]
            if new_distance < d[neighbor]:
                d[neighbor] = new_distance
                parent[neighbor] = source
                heappush(priority_queue, (new_distance, neighbor))
    return d


n, m, s, t = map(int, fin().split())
adj = defaultdict(list)
yen_weights = dict()
snuuk_weights = dict()
for _ in range(m):
    u, v, a, b = map(int, fin().split())
    for v1, v2 in [(u, v), (v, u)]:
        adj[v1].append(v2)
        yen_weights[(v1, v2)] = a
        snuuk_weights[(v1, v2)] = b

d_yen = dijkstra_simple(adj, yen_weights, s)
d_snuuk = dijkstra_simple(adj, snuuk_weights, t)
min_cost = float('inf')
min_cost_after_each_year_reversed = []
for vertex in range(n, 0, -1):
    min_cost = min(min_cost, d_yen[vertex] + d_snuuk[vertex])
    min_cost_after_each_year_reversed.append(min_cost)

initial_money = 10**15
for cost in reversed(min_cost_after_each_year_reversed):
    print(initial_money - cost)

Submission status: Accepted

Solution code:
# import sys
# fin = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush


def initialize(adj, s):
    MAX_NUM = float('inf')
    parent = {s: None}
    d = {vertex: MAX_NUM for vertex in adj.keys()}
    d[s] = 0
    return d, parent


# Dijkstra can work using a minheap which does not have decrease_key.
# and also we do not have to implement Vertex class.
# Instead, we can use (distance, vertex).
# in this case, the time it takes is O(ElgE).
# E is at most O(V^2), thus O(ElgE) = O(ElgV).
def dijkstra_simple(adj, w, s):
    d, parent = initialize(adj, s)
    priority_queue = []
    heappush(priority_queue, (d[s], s))
    while priority_queue:
        distance, source = heappop(priority_queue) 
        for neighbor in adj[source]:
            new_distance = distance + w[(source, neighbor)]
            if new_distance < d[neighbor]:
                d[neighbor] = new_distance
                parent[neighbor] = source
                heappush(priority_queue, (new_distance, neighbor))
    return d


n, m, s, t = map(int, input().split())
adj = defaultdict(list)
yen_weights = dict()
snuuk_weights = dict()
for _ in range(m):
    u, v, a, b = map(int, input().split())
    for v1, v2 in [(u, v), (v, u)]:
        adj[v1].append(v2)
        yen_weights[(v1, v2)] = a
        snuuk_weights[(v1, v2)] = b

d_yen = dijkstra_simple(adj, yen_weights, s)
d_snuuk = dijkstra_simple(adj, snuuk_weights, t)
min_cost = float('inf')
min_cost_after_each_year_reversed = []
for vertex in range(n, 0, -1):
    min_cost = min(min_cost, d_yen[vertex] + d_snuuk[vertex])
    min_cost_after_each_year_reversed.append(min_cost)

initial_money = 10**15
print(*(initial_money - cost for cost in reversed(min_cost_after_each_year_reversed)), sep='\n')

Submission status: Accepted

Solution code:
import sys
fin = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush


class Vertex(object):
    def __init__(self, name, distance):
        self.name = name
        self.distance = distance


    def __lt__(self, other_vertex):
        return self.distance < other_vertex.distance
    

    def __le__(self, other_vertex):
        return self.distance <= other_vertex.distance
    

    def __gt__(self, other_vertex):
        return self.distance > other_vertex.distance
    

    def __ge__(self, other_vertex):
        return self.distance >= other_vertex.distance


def initialize(adj, s):
    MAX_NUM = float('inf')
    parent = {s: None}
    d = {vertex: MAX_NUM for vertex in adj.keys()}
    d[s] = 0
    return d, parent


# Dijkstra can work using a minheap which does not have decrease_key.
# and also we do not have to implement Vertex class.
# Instead, we can use (distance, vertex).
# in this case, the time it takes is O(ElgE).
# E is at most O(V^2), thus O(ElgE) = O(ElgV).
def dijkstra_simple(adj, w, s):
    d, parent = initialize(adj, s)
    priority_queue = []
    heappush(priority_queue, (d[s], s))
    while priority_queue:
        distance, source = heappop(priority_queue) 
        for neighbor in adj[source]:
            new_distance = distance + w[(source, neighbor)]
            if new_distance < d[neighbor]:
                d[neighbor] = new_distance
                parent[neighbor] = source
                heappush(priority_queue, (new_distance, neighbor))
    return d


n, m, s, t = [int(elem) for elem in fin().split(' ')]
adj = defaultdict(list)
yen_weights = dict()
snuuk_weights = dict()
for _ in range(m):
    u, v, a, b = [int(elem) for elem in fin().split(' ')]
    for v1, v2 in [(u, v), (v, u)]:
        adj[v1].append(v2)
        yen_weights[(v1, v2)] = a
        snuuk_weights[(v1, v2)] = b

d_yen = dijkstra_simple(adj, yen_weights, s)
d_snuuk = dijkstra_simple(adj, snuuk_weights, t)
min_cost = float('inf')
min_cost_after_each_year_reversed = []
for vertex in range(n, 0, -1):
    min_cost = min(min_cost, d_yen[vertex] + d_snuuk[vertex])
    min_cost_after_each_year_reversed.append(min_cost)

initial_money = 10**15
print(*(initial_money - cost for cost in reversed(min_cost_after_each_year_reversed)), sep='\n')

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
n, m, s, t = map(int, input().split())
edge_a = [set() for _ in range(n + 1)]
edge_b = [set() for _ in range(n + 1)]
for _ in range(m):
    u, v, a, b = map(int, input().split())
    edge_a[u].add((v, a))
    edge_a[v].add((u, a))
    edge_b[u].add((v, b))
    edge_b[v].add((u, b))

def dijkstra(edge, s):
    sp = [10 ** 19] * (n + 1)
    sp[s] = 0
    q = [(0, s)]
    while q:
        dist, s = heappop(q)
        for t, w in edge[s]:
            if dist + w < sp[t]:
                sp[t] = dist + w
                heappush(q, (sp[t], t))
    return sp

sp_a = dijkstra(edge_a, s)
sp_b = dijkstra(edge_b, t)
dist = [int(sp_a[-1] + sp_b[-1])]
for i in range(n - 1, 0, -1):
    dist.append(min(dist[-1], int(sp_a[i] + sp_b[i])))

snuk = 10 ** 15
print(*(snuk - d for d in reversed(dist)), sep='\n')

Submission status: Accepted

Solution code:
import heapq

def Yen(s):
    Cost = [float("inf") for i in range(n)]
    V = [False for i in range(n)]
    Q = [(0, s-1)]
    Cost[s-1] = 0
    while Q:
        tempCost, tempNode = heapq.heappop(Q)
        V[tempNode] = True
        for node in A[tempNode]:
            if V[node[1]] == False:
                if Cost[node[1]] > tempCost + node[0]:
                    Cost[node[1]] = tempCost + node[0]
                    heapq.heappush(Q, (Cost[node[1]], node[1]))
    return Cost

def Snuuk(t):
    Cost = [float("inf") for i in range(n)]
    V = [False for i in range(n)]
    Q = [(0, t-1)]
    Cost[t-1] = 0
    while Q:
        tempCost, tempNode = heapq.heappop(Q)
        V[tempNode] = True
        for node in B[tempNode]:
            if V[node[1]] == False:
                if Cost[node[1]] > tempCost + node[0]:
                    Cost[node[1]] = tempCost + node[0]
                    heapq.heappush(Q, (Cost[node[1]], node[1]))
    return Cost

n, m ,s, t = map(int, input().split())
ini = 10 ** 15
A = [[] for i in range(n)]
B = [[] for i in range(n)]
for i in range(m):
    u, v, a, b = map(int, input().split())
    u, v = u-1, v-1
    A[u].append((a, v))
    A[v].append((a, u))
    B[u].append((b, v))
    B[v].append((b, u))

Yen, Snuuk = Yen(s), Snuuk(t)
total, minCost = [], []
tempmin = float("inf")
for i in reversed(range(n)):
    total.append(Yen[i] + Snuuk[i])
    tempmin = min(tempmin, Yen[i] + Snuuk[i])
    minCost.append(tempmin)

for i in reversed(range(n)):
    print(ini - minCost[i])

Submission status: Accepted

Solution code:
import heapq


class Dijkstra:

    def __init__(self, rote_map, start_point, goal_point=None):
        self.rote_map = rote_map
        self.start_point = start_point
        self.goal_point = goal_point

    def execute(self):
        """
        :param rote_map:
        :param start_point:
        :param distance:
        :return:
        """
        num_of_city = len(self.rote_map)
        dist = [float("inf") for _ in range(num_of_city)]
        prev = [float("inf") for _ in range(num_of_city)]

        dist[self.start_point] = 0
        heap_q = []
        heapq.heappush(heap_q, (0, self.start_point))
        while len(heap_q) != 0:
            prov_cost, src = heapq.heappop(heap_q)

            if dist[src] < prov_cost:
                continue

            for dest, cost in self.rote_map[src].items():
                if cost != float("inf") and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost
                    heapq.heappush(heap_q, (dist[dest], dest))
                    prev[dest] = src
        if self.goal_point is not None:
            return self.get_path(self.goal_point, prev)
        else:
            return dist

    def get_path(self, goal, prev):
        path = [goal]
        dest = goal

        while prev[dest] != float("inf"):
            path.append(prev[dest])
            dest = prev[dest]

        return list(reversed(path))


n, m, s, t = map(int, input().split())
yen_route_map = [dict() for _ in range(n)]
snuuk_route_map = [dict() for _ in range(n)]

for i in range(m):
    u, v, a, b = map(int, input().split())
    u, v = u-1, v-1
    yen_route_map[u][v] = yen_route_map[v][u] = a
    snuuk_route_map[u][v] = snuuk_route_map[v][u] = b
yen_dijkstra = Dijkstra(yen_route_map, s-1).execute()
snuuk_dijkstra = Dijkstra(snuuk_route_map, t-1).execute()

from itertools import accumulate
ans = list(accumulate([y+s for y, s in zip(yen_dijkstra, snuuk_dijkstra)][::-1],min))
[print(10**15-ans[i]) for i in range(n-1,-1,-1)]

Submission status: Accepted

Solution code:
import heapq


class Dijkstra:

    def __init__(self, rote_map, start_point, goal_point=None):
        self.rote_map = rote_map
        self.start_point = start_point
        self.goal_point = goal_point

    def execute(self):
        """
        :param rote_map:
        :param start_point:
        :param distance:
        :return:
        """
        num_of_city = len(self.rote_map)
        dist = [float("inf") for _ in range(num_of_city)]
        prev = [float("inf") for _ in range(num_of_city)]

        dist[self.start_point] = 0
        heap_q = []
        heapq.heappush(heap_q, (0, self.start_point))
        while len(heap_q) != 0:
            prov_cost, src = heapq.heappop(heap_q)

            if dist[src] < prov_cost:
                continue

            for dest, cost in self.rote_map[src].items():
                if cost != float("inf") and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost
                    heapq.heappush(heap_q, (dist[dest], dest))
                    prev[dest] = src
        if self.goal_point is not None:
            return self.get_path(self.goal_point, prev)
        else:
            return dist

    def get_path(self, goal, prev):
        path = [goal]
        dest = goal

        while prev[dest] != float("inf"):
            path.append(prev[dest])
            dest = prev[dest]

        return list(reversed(path))


n, m, s, t = map(int, input().split())
yen_route_map = [dict() for _ in range(n)]
snuuk_route_map = [dict() for _ in range(n)]

for i in range(m):
    u, v, a, b = map(int, input().split())
    u, v = u-1, v-1
    yen_route_map[u][v] = yen_route_map[v][u] = a
    snuuk_route_map[u][v] = snuuk_route_map[v][u] = b
yen_dijkstra = Dijkstra(yen_route_map, s-1).execute()
snuuk_dijkstra = Dijkstra(snuuk_route_map, t-1).execute()

from itertools import accumulate
ans = list(accumulate([y+s for y, s in zip(yen_dijkstra, snuuk_dijkstra)][::-1],min))
[print(10**15-ans[i]) for i in range(n-1,-1,-1)]

# answer1 = [yen + snuuk for yen, snuuk in zip(yen_dijkstra, snuuk_dijkstra)]
# answer2
#
# for i in range(n):
#     print(10**15 - answer1[i])

Submission status: Accepted

Solution code:
import heapq
from itertools import accumulate

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

def dijkstra(graph, start):
    dist = [ 10**14 for _ in range(n)]
    dist[start] = 0
    q = [(0,start)]
    while q:
        l, v = heapq.heappop(q)
        if dist[v] < l:
            continue
        for u, d in graph[v].items():
            if dist[u] > l+d:
                dist[u] = l+d
                heapq.heappush(q, (dist[u], u))
    return dist

D_yen = [ dict() for _ in range(n)]
D_snuuk = [ dict() for _ in range(n)]
for _ in range(m):
    u, v, a, b = map( int, input().split())
    u, v = u-1, v-1
    D_yen[u][v] = D_yen[v][u] = a
    D_snuuk[u][v] = D_snuuk[v][u] = b

C_yen = dijkstra(D_yen, s-1)
C_snuuk = dijkstra(D_snuuk, t-1)

ANS = list( accumulate( [y+s for y, s in zip( C_yen, C_snuuk)][::-1], min))
[ print( 10**15 - ANS[i]) for i in range(n-1,-1,-1)]

Submission status: Accepted

Solution code:
import heapq

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

def dijkstra(graph, start):
    dist = [ 10**14 for _ in range(n)]
    dist[start] = 0
    q = [(0,start)]
    while q:
        l, v = heapq.heappop(q)
        if dist[v] < l:
            continue
        for u, d in graph[v].items():
            if dist[u] > l+d:
                dist[u] = l+d
                heapq.heappush(q, (dist[u], u))
    return dist

D_yen = [ dict() for _ in range(n)]
D_snuuk = [ dict() for _ in range(n)]
for _ in range(m):
    u, v, a, b = map( int, input().split())
    u, v = u-1, v-1
    D_yen[u][v] = D_yen[v][u] = a
    D_snuuk[u][v] = D_snuuk[v][u] = b

C_yen = dijkstra(D_yen, s-1)
C_snuuk = dijkstra(D_snuuk, t-1)
ans = 10**15
ANS = [ 0 for _ in range(n)]
for i in range(n):
    ans = min( ans, C_yen[n-1-i] + C_snuuk[n-1-i])
    ANS[n-1-i] = ans
for i in range(n):
    print(10**15 - ANS[i])

Submission status: Accepted

Solution code:
'''
隣接リストを用いた実装
O(ElogV) ：次に探す頂点をプライオリティーキューを用いて探索
V: 頂点数
G[i] = [(j, c_ij) for j in (iに隣接する頂点）]
'''
import heapq

def Dijkstra(G, start):
    d = [float('inf')] * V
    d[start] = 0
    q =[]
    heapq.heappush(q, (0, start))
    while len(q) > 0:
        dist, v  = heapq.heappop(q)
        if d[v] < dist:
            continue
        for j, cost in G[v]:
            if d[j] > d[v] + cost:
                d[j] = d[v] + cost
                heapq.heappush(q, (d[j], j))
    return d

V, E, s, t = map(int, input().split())
Yen = [[] for _ in range(V)]
Snuke = [[] for _ in range(V)]
for i in range(E):
    ui, vi, ai, bi = map(int, input().split())
    Yen[ui - 1].append((vi - 1, ai))
    Yen[vi - 1].append((ui - 1, ai))
    Snuke[ui - 1].append((vi - 1, bi))
    Snuke[vi - 1].append((ui - 1, bi))

Yen_min = Dijkstra(Yen, s - 1)
Snuke_min = Dijkstra(Snuke, t - 1)
dist = [(Yen_min[i] + Snuke_min[i]) for i in range(V)]
ans = [float('inf') for i in range(V)]
ans[V - 1] = dist[V - 1]
for i in range(V - 2, -1, -1):
    ans[i] = min(dist[i], ans[i + 1] )
for i in range(V):
    print(10 ** 15 - ans[i])

Submission status: Accepted

Solution code:
import heapq

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

INF = 10 ** 15
G1, G2 = [[] for i1 in range(N)], [[] for i2 in range(N)]
used1, used2 = [0 for i3 in range(N)], [0 for i4 in range(N)]
dist1, dist2 = [INF for i5 in range(N)], [INF for i6 in range(N)]


def dijkstra(g, s, d, c):
    d[s], pq = 0, []
    heapq.heappush(pq, (0, s))

    while len(pq) != 0:
        u = heapq.heappop(pq)
        c[u[1]] = 2

        if d[u[1]] < u[0]:
            continue

        for v in g[u[1]]:
            if c[v[0]] != 2:
                if d[u[1]] + v[1] < d[v[0]]:
                    d[v[0]], c[v[0]] = d[u[1]] + v[1], 1
                    heapq.heappush(pq, (d[v[0]], v[0]))


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

    dijkstra(G1, S-1, dist1, used1)
    dijkstra(G2, T-1, dist2, used2)

    c = [0 for i in range(N)]
    for i in range(N):
        c[i] = dist1[i] + dist2[i]

    cc = [0 for i in range(N)]
    cc[N-1] = c[N-1]
    for i in range(N-2, -1, -1):
        cc[i] = min(cc[i+1], c[i])

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop


class Dijk:
    def __init__(self, n):
        self.table = [[] for i in range(n)]
        self.n = n

    def add(self, x, y, f):
        self.table[x].append((y, f))

    def di(self, s):
        inf = 10 ** 20
        self.val = [inf] * self.n
        self.val[s] = 0
        h = []
        heappush(h, (0, s))
        while h:
            q, i = heappop(h)
            if self.val[i] < q:
                continue
            for x, c in self.table[i]:
                if self.val[x] > self.val[i] + c:
                    self.val[x] = self.val[i] + c
                    heappush(h, (self.val[x], x))

    def dist(self, s, t):
        return self.val[t]


N, M, s, t = map(int, input().split())
stra = Dijk(N)
rstra = Dijk(N)
for i in range(M):
    u, v, a, b = map(int, input().split())
    stra.add(u - 1, v - 1, a)
    stra.add(v - 1, u - 1, a)
    rstra.add(u - 1, v - 1, b)
    rstra.add(v - 1, u - 1, b)
stra.di(s - 1)
rstra.di(t - 1)
ans = []
T = 10 ** 15
mod = 10 ** 15
for i in range(N - 1, -1, -1):
    T = min(stra.dist(s - 1, i) + rstra.dist(t - 1, i), T)
    ans.append(mod - T)
print('\n'.join(map(str, ans[::-1])))

Submission status: Accepted

Solution code:
from  heapq import heappush, heappop, heapify

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

nl=[ [ ] for j in range(n+1) ] 

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


def dij(v,type):
	d=[ float("inf") for i  in range(n+1)]
	d[v]=0

	Q=[]
	heappush(Q, (0,v ) )

	while len(Q)>0:
		base, u=heappop(Q)
		for v,yen,snuuk in nl[u]:
			if type=="y":alt=base+yen
			elif type=="s":alt=base+snuuk

			if d[v]> alt:
				d[v]=alt
				heappush(Q,( d[v], v ) )
	return d

d_y=dij(s,"y")
d_s=dij(t,"s")

val=float("inf")

A=[]
for i in range(n,0,-1):
	tmp=d_y[i]+d_s[i]
	val=min(val, tmp)
	A.append(val)

for i in reversed(A):
	print 10**15-i

Submission status: Accepted

Solution code:
import  heapq

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

nl=[ [ ] for j in range(n+1) ] 

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


#Dijkstra yen
d_y=[ float("inf") ]*(n+1)
d_y[s]=0

Q=[]
heapq.heappush(Q, (0,s) )

while Q:
	cost, u=heapq.heappop(Q)
	for v,yen,snuuk in nl[u]:
		if d_y[v] > cost+yen:
			d_y[v]=cost+yen
			heapq.heappush(Q, (d_y[v], v)  )

#Dijkstra snuuk
d_s=[ float("inf")]*(n+1)
d_s[t]=0

Q=[]
heapq.heappush(Q,(0,t) )

while Q:
	cost, u=heapq.heappop(Q)
	for v,yen,snuuk in nl[u]:
		if d_s[v] > cost+snuuk:
			d_s[v]=cost+snuuk
			heapq.heappush(Q, (d_s[v], v)  )


val=float("inf")
A=[]
for i in range(n,0,-1):
	tmp=d_y[i]+d_s[i]
	val=min(val, tmp)
	A.append(val)

for i in reversed(A):
	print 10**15-i

Submission status: Accepted

Solution code:
import  heapq

n,m,s,t=map(int,raw_input().split())
src = [ tuple( map( int, raw_input().split() ) )   for i in range(m)]

nl=[ [ ] for j in range(n+1) ] 

for u,v,a,b in src:
	nl[u].append( (v,a,b) )
	nl[v].append( (u,a,b) )

#Dijkstra yen
d_y=[ float("inf") ]*(n+1)
d_y[s]=0

Q=[]
heapq.heappush(Q, (0,s) )

while Q:
	cost, u=heapq.heappop(Q)
	for v,yen,snuuk in nl[u]:
		if d_y[v] > cost+yen:
			d_y[v]=cost+yen
			heapq.heappush(Q, (d_y[v], v)  )

#Dijkstra snuuk
d_s=[ float("inf")]*(n+1)
d_s[t]=0

Q=[]
heapq.heappush(Q,(0,t) )

while Q:
	cost, u=heapq.heappop(Q)
	for v,yen,snuuk in nl[u]:
		if d_s[v] > cost+snuuk:
			d_s[v]=cost+snuuk
			heapq.heappush(Q, (d_s[v], v)  )


val=float("inf")
A=[]
for i in range(n,0,-1):
	tmp=d_y[i]+d_s[i]
	val=min(val, tmp)
	A.append(val)

for i in reversed(A):
	print 10**15-i

Submission status: Accepted

Solution code:
import heapq
 
N,M,S,T = map(int, raw_input().split())
S,T = S-1,T-1
src = [tuple(map(int, raw_input().split())) for i in range(M)]
 
es = [[] for i in range(N)]
for u,v,a,b in src:
    u,v = u-1,v-1
    es[u].append((v,a,b))
    es[v].append((u,a,b))
 
INF = float('inf')
cy = [INF] * N
cy[S] = 0
hq = [(0,S)]
heapq.heapify(hq)
while hq:
    cost,v = heapq.heappop(hq)
    for to,a,b in es[v]:
        if cost + a >= cy[to]: continue
        cy[to] = cost + a
        heapq.heappush(hq, (cy[to],to))
 
cs = [INF] * N
cs[T] = 0
hq = [(0,T)]
heapq.heapify(hq)
while hq:
    cost,v = heapq.heappop(hq)
    for to,a,b in es[v]:
        if cost + b >= cs[to]: continue
        cs[to] = cost + b
        heapq.heappush(hq, (cs[to],to))
 
ans = [INF]
for i in reversed(range(N)):
    tmp = cs[i] + cy[i]
    ans.append(min(ans[-1],tmp))
 
for a in reversed(ans[1:]):
    print 10**15 - a

Submission status: Accepted

Solution code:
import heapq
 
N,M,S,T = map(int,input().split())
S,T = S-1,T-1
src = [tuple(map(int,input().split())) for i in range(M)]
 
es = [[] for i in range(N)]
for u,v,a,b in src:
    u,v = u-1,v-1
    es[u].append((v,a,b))
    es[v].append((u,a,b))
 
INF = float('inf')
cy = [INF] * N
cy[S] = 0
hq = [(0,S)]
heapq.heapify(hq)
while hq:
    cost,v = heapq.heappop(hq)
    for to,a,b in es[v]:
        if cost + a >= cy[to]: continue
        cy[to] = cost + a
        heapq.heappush(hq, (cy[to],to))
 
cs = [INF] * N
cs[T] = 0
hq = [(0,T)]
heapq.heapify(hq)
while hq:
    cost,v = heapq.heappop(hq)
    for to,a,b in es[v]:
        if cost + b >= cs[to]: continue
        cs[to] = cost + b
        heapq.heappush(hq, (cs[to],to))
 
ans = [INF]
for i in reversed(range(N)):
    tmp = cs[i] + cy[i]
    ans.append(min(ans[-1],tmp))
 
for a in reversed(ans[1:]):
    print(10**15 - a)