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

Submission status: Accepted

Solution code:
import heapq

def dijkstra(s, G):
    que = [(0, s)]
    d = [float("inf")]*len(G)
    d[s] = 0
    while que:
        c, v = heapq.heappop(que)
        if d[v] > c: continue
        for to, cost in G[v]:
            if d[to] > d[v] + cost:
                d[to] = d[v] + cost
                heapq.heappush(que, (d[to], to))
    return d

n, m, s, t = map(int, raw_input().split())
s, t = s - 1, t - 1 
G0, G1 = [[] for i in xrange(n)], [[] for i in xrange(n)]
for i in range(m):
    ui, vi, ai, bi = map(int, raw_input().split())
    ui, vi = ui - 1, vi - 1
    G0[ui].append((vi, ai))
    G0[vi].append((ui, ai))
    G1[ui].append((vi, bi))
    G1[vi].append((ui, bi))

d0 = dijkstra(s, G0)
d1 = dijkstra(t, G1)

yen = 10**15
ans = [float("inf")]*(n + 1)
for i in xrange(n - 1, -1, -1):
    ans[i] = min(ans[i + 1], d0[i] + d1[i])

for i in xrange(n):
    print yen - ans[i]

Submission status: Accepted

Solution code:
from heapq import heappush, heappop 
def main():
  INF = 10 ** 20
  n, m, s, t = map(int, input().split())
  s -= 1
  t -= 1
  init = 10 ** 15
  edges1 = [[] for _ in range(n)]
  edges2 = [[] for _ in range(n)]
  for _ in range(m):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    edges1[u].append((v, a))
    edges1[v].append((u, a))
    edges2[u].append((v, b))
    edges2[v].append((u, b))
  
  from_s = [INF] * n
  from_s[s] = 0
  que = []
  heappush(que, (0, s))
  while que:
    total, node = heappop(que)
    for to, dist in edges1[node]:
      if from_s[to] > total + dist:
        from_s[to] = total + dist
        heappush(que, (total + dist, to))
  
  from_t = [INF] * n
  from_t[t] = 0
  que = []
  heappush(que, (0, t))
  while que:
    total, node = heappop(que)
    for to, dist in edges2[node]:
      if from_t[to] > total + dist:
        from_t[to] = total + dist
        heappush(que, (total + dist, to))

  save = []
  for i in range(n):
    save.append(init - from_s[i] - from_t[i])
  save.reverse()
  acc = 0
  ans = []
  for s in save:
    acc = max(acc, s)
    ans.append(acc)
  ans.reverse() 
  for i in range(n):
    print(ans[i])

main()

Submission status: Accepted

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

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

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

import heapq

class Dijkstra(object):
    def dijkstra(self, lst, start, goal=None):
        '''
        ダイクストラアルゴリズムによる最短経路を求めるメソッド
        入力
        adj: adj[i][j]の値が頂点iから頂点jまでの距離(頂点iから頂点jに枝がない場合，値はfloat('inf'))となるような2次元リスト(正方行列)
        start: 始点のID
        lst: 隣接リスト
        goal: オプション引数．終点のID
        出力
        goalを引数に持つ場合，startからgoalまでの最短経路を格納したリストを返す
        持たない場合は，startから各頂点までの最短距離を格納したリストを返す
        >>> d = Dijkstra()
        >>> d.dijkstra([[float('inf'), 2, 4, float('inf'), float('inf')], [2, float('inf'), 3, 5, float('inf')], [4, 3, float('inf'), 1, 4], [float('inf'), 5, 1, float('inf'), 3], [float('inf'), float('inf'), 4, 3, float('inf')]], 0)
        [0, 2, 4, 5, 8] # 例えば，始点0から頂点3までの最短距離は5となる
        >>> d.dijkstra([[float('inf'), 2, 4, float('inf'), float('inf')], [2, float('inf'), 3, 5, float('inf')], [4, 3, float('inf'), 1, 4], [float('inf'), 5, 1, float('inf'), 3], [float('inf'), float('inf'), 4, 3, float('inf')]], 0, goal=4)
        [0, 2, 4] # 頂点0から頂点4までの最短経路は0 -> 2 -> 4となる
        '''
        num = len(lst)         # グラフのノード数
        dist = [float('inf') for i in range(num)] # 始点から各頂点までの最短距離を格納する
        prev = [float('inf') for i in range(num)] # 最短経路における，その頂点の前の頂点のIDを格納する
        
        dist[start] = 0
        q = []                  # プライオリティキュー．各要素は，(startからある頂点vまでの仮の距離, 頂点vのID)からなるタプル
        heapq.heappush(q, (0, start)) # 始点をpush

        while len(q) != 0:
            prov_cost, src = heapq.heappop(q) # pop
            
            # プライオリティキューに格納されている最短距離が，現在計算できている最短距離より大きければ，distの更新をする必要はない
            if dist[src] < prov_cost:
                continue

            # 他の頂点の探索
            # for dest in range(num):
            for dest in lst[src]:
                # cost = adj[src][dest]
                cost = dest[1]
                # if dist[dest] > dist[src] + cost:
                if dist[dest[0]] > dist[src] + cost:
                	# dist[dest] = dist[src] + cost # distの更新
                	dist[dest[0]] = dist[src] + cost
                    # heapq.heappush(q, (dist[dest], dest)) # キューに新たな仮の距離の情報をpush
                	heapq.heappush(q, (dist[dest[0]], dest[0]))
                    # prev[dest] = src                      # 前の頂点を記録
                	prev[dest[0]] = src
         
        # 以下は経路を返すプログラム           
        # if goal is not None:
        #     return self.get_path(goal, prev)
        if goal is not None:
        	return dist[goal]

        else:
            return dist

    def get_path(self, goal, prev):
        '''
        始点startから終点goalまでの最短経路を求める
        '''
        path = [goal]           # 最短経路
        dest = goal

        # 終点から最短経路を逆順に辿る
        while prev[dest] != float('inf'):
            path.append(prev[dest])
            dest = prev[dest]

        # 経路をreverseして出力
        return list(reversed(path))

d = Dijkstra()
yen = d.dijkstra(yen_edge, s - 1)
snuke = d.dijkstra(snuke_edge, t - 1)
ans_list = []

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

ans = []

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

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

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

Submission status: Accepted

Solution code:

from heapq import *
from collections import defaultdict

def Dijkstra(s, N, E):
    # https://ja.wikipedia.org/wiki/%E3%83%80%E3%82%A4%E3%82%AF%E3%82%B9%E3%83%88%E3%83%A9%E6%B3%95
    d = [10**30] * (N + 1)
    d[s] = 0
    Q = []
    for v in range(1, N + 1):
        heappush(Q, (d[v], v))
    while Q:
        x, u = heappop(Q)
        for v, y in E[u].items():
            alt = d[u] + y
            if d[v] > alt:
                d[v] = alt
                heappush(Q, (alt, v))
    return d

N, M, S, T = [int(_) for _ in input().split()]
UVAB = [[int(_) for _ in input().split()] for i in range(M)]

Ea = defaultdict(dict)
Eb = defaultdict(dict)

for u, v, a, b in UVAB:
    Ea[u][v] = a
    Ea[v][u] = a
    Eb[u][v] = b
    Eb[v][u] = b
    
Da = Dijkstra(S, N, Ea)
Db = Dijkstra(T, N, Eb)

T = [None] * (N + 1)
t = 10**30

for i in range(N, 0, -1):
    r = Da[i] + Db[i]
    t = min(t, r)
    T[i] = t

ST = 10**15

for i in range(1, N + 1):
    print(ST-T[i])

Submission status: Accepted

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

s_dist = [float('inf')] * (n+1)
t_dist = [float('inf')] * (n+1)
yen_edge = {}
snu_edge = {}
for i in range(m):
  u, v, a, b = map(int, input().split())
  if u not in yen_edge:
    yen_edge[u] = {}
    snu_edge[u] = {}
  if v not in yen_edge:
    yen_edge[v] = {}
    snu_edge[v] = {}
  yen_edge[u][v] = yen_edge[v][u] = a
  snu_edge[u][v] = snu_edge[v][u] = b

def dijkstra(dist, edge, s):
  end = set()
  q = []
  dist[s] = 0
  heappush(q, (0, s))
  while len(q):
    c, k = heappop(q)
    if dist[k] < c:
      continue
    end.add(k)
    for j, cost in edge[k].items():
      if j not in end:
        if dist[j] > c + cost:
          dist[j] = c + cost
          heappush(q, (dist[j], j))

dijkstra(s_dist, yen_edge, s)
dijkstra(t_dist, snu_edge, t)

ans = []
ans.append(s_dist[n]+t_dist[n])
for i in range(n-1, 0, -1):
  ans.append(min(ans[-1], s_dist[i]+t_dist[i]))

money = 10 ** 15
for a in ans[::-1]:
  print(money - a)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

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 = collections.defaultdict(lambda: 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

def main():
    n,m,s,t = LI()
    aa = [LI() for i in range(m)]
    d1 = Dijkstra()
    d2 = Dijkstra()
    for u,v,a,b in aa:
        d1.add(u,v,a)
        d2.add(u,v,b)
    ad = d1.search(s)
    bd = d2.search(t)
    rr = [inf]
    for i in range(n,0,-1):
        tr = ad[i] + bd[i]
        if tr > rr[-1]:
            tr = rr[-1]
        rr.append(tr)

    return '\n'.join(map(lambda x: str(10**15-x), rr[1:][::-1]))


print(main())

Submission status: Accepted

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


def dijkstra(x, G):
    d = [float('inf')] * N
    d[x] = 0
    visited = {x}

    # d, u
    hq = [(0, x)]

    while hq:
        u = heapq.heappop(hq)[1]
        visited.add(u)

        for node, cost in G[u]:
            if (node not in visited) and d[node] > d[u] + cost:
                d[node] = d[u] + cost
                heapq.heappush(hq, (d[u]+cost, node))
    return d


toChange = dijkstra(S, G1)
toGoal = dijkstra(T, G2)

ans = [float('inf')]
for i in range(N-1, -1, -1):
    ans.append(min(ans[-1], toChange[i] + toGoal[i]))

del ans[0]
money = 10 ** 15
for cost in ans[::-1]:
    print(money - cost)

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)

Submission status: Accepted

Solution code:
#!/usr/bin/env pypy3


import heapq
import sys


M = 10 ** 15
INF = 10 * M


def dijkstra(num_vs, source, adj_vs, costs):
    min_dist = [INF for _ in range(num_vs)]
    min_dist[source] = 0
    pq = [(min_dist[i], i) for i in range(num_vs)]
    heapq.heapify(pq)
    while pq:
        min_dist_i, i = heapq.heappop(pq)
        for j in adj_vs[i]:
            new_length = min_dist[i] + costs[(i, j)]
            if new_length < min_dist[j]:
                min_dist[j] = new_length
                heapq.heappush(pq, (new_length, j))
    return min_dist


def max_values(n, s, t, adj_vs, yen_costs, snuke_costs):
    s_to_x_yen_dists = dijkstra(n, s, adj_vs, yen_costs)
    # s_to_x_snuke_dists = dijkstra(n, s, adj_vs, snuke_costs)
    # t_to_x_yen_dists = dijkstra(n, t, adj_vs, yen_costs)
    t_to_x_snuke_dists = dijkstra(n, t, adj_vs, snuke_costs)
    # 両替所 i を経由したときの残金
    p2r = [M - s_to_x_yen_dists[i] - t_to_x_snuke_dists[i] for i in range(n)]
    # print(p2r, file=sys.stderr)
    res = [p2r[n - 1]]
    for i in range(n - 1)[::-1]:
        new_r = p2r[i]
        if new_r > res[-1]:
            res.append(new_r)
        else:
            res.append(res[-1])
    res.reverse()
    # print(res, file=sys.stderr)
    return res


def main():
    n, m, s, t = (int(x) for x in input().split())
    s -= 1
    t -= 1
    yen_costs = dict()
    snuke_costs = dict()
    adj_vs = [set() for _ in range(n)]
    for _ in range(m):
        u, v, a, b = (int(x) for x in input().split())
        u -= 1
        v -= 1
        adj_vs[u].add(v)
        adj_vs[v].add(u)
        yen_costs[(u, v)] = yen_costs[(v, u)] = a
        snuke_costs[(u, v)] = snuke_costs[(v, u)] = b
    res = max_values(n, s, t, adj_vs, yen_costs, snuke_costs)
    for line in res:
        print(line)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq

n, m, s, t = map(int, input().split())
adjYen = [[] for v in range(n)]
adjSnuuk = [[] for v in range(n)]

for i in range(m):
    u, v, a, b = map(int, input().split())
    adjYen[u-1].append((v-1, a))
    adjYen[v-1].append((u-1, a))
    adjSnuuk[u-1].append((v-1, b))
    adjSnuuk[v-1].append((u-1, b))

# 単一始点最短経路を求める（ダイクストラ法）
def Dijkstra(adjList, vSt):
    numV = len(adjList)

    numDone = 0
    pq = []

    cost = [float('inf')] * numV
    cost[vSt] = 0
    heapq.heappush(pq, (0, vSt))

    while pq:
        c, vNow = heapq.heappop(pq)
        if c > cost[vNow]: continue

        numDone += 1
        if numDone == numV: break

        for v2, wt in adjList[vNow]:
            c2 = cost[vNow] + wt
            if c2 < cost[v2]:
                cost[v2] = c2
                heapq.heappush(pq, (c2, v2))

    return cost


costYen = Dijkstra(adjYen, s-1)
costSnuuk = Dijkstra(adjSnuuk, t-1)

cost = [(y + s, v) for v, (y, s) in enumerate(zip(costYen, costSnuuk))]
cost.sort()

iC = 0
for i in range(n):
    while cost[iC][1] < i:
        iC += 1
    print(10 ** 15 - cost[iC][0])

Submission status: Accepted

Solution code:
import heapq as hq

# adj list graph
def dijkstra(adj, costs, s):
  N = len(adj)
  q = [(0,s)]
  dist = [float('inf')]*N
  dist[s] = 0
  prev = [None]*N

  while q:
    c, u = hq.heappop(q)
    if c > dist[u]:
      continue

    for v in adj[u]:
      if dist[v] > dist[u] + costs[(u,v)]:
        dist[v] = dist[u] + costs[(u,v)]
        prev[v] = u
        hq.heappush(q, (dist[v], v))

  return prev, dist


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

G = [list() for _ in range(n)]
Cs = dict()
Ct = dict()

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

Ds = dijkstra(G, Cs, s)[1]
Dt = dijkstra(G, Ct, t)[1]

D = sorted(((a+b, i) for i,(a,b) in enumerate(zip(Ds,Dt))), reverse=True)
for i in range(n):
  while D[-1][1] < i:
    D.pop()
  print(int(10**15 - D[-1][0]))

Submission status: Accepted

Solution code:
from heapq import heappush,heappop
from collections import deque
N,M,s,t=map(int,input().split())
table=[[] for i in range(N)]
rtable=[[] for i in range(N)]
for i in range(M):
    u,v,a,b=map(int,input().split())
    table[u-1].append([a,v-1])
    table[v-1].append([a,u-1])
    rtable[u-1].append([b,v-1])
    rtable[v-1].append([b,u-1])
dij=[]
heappush(dij,[0,s-1])
val=[10**16]*N
val[s-1]=0
while dij:
    q,x=heappop(dij)
    if val[x]<q:
        continue
    for d,y in table[x]:
        if val[y]>val[x]+d:
            val[y]=val[x]+d
            heappush(dij,[val[y],y])
rdij=[]
heappush(rdij,[0,t-1])
rval=[10**16]*N
rval[t-1]=0
while rdij:
    q,x=heappop(rdij)
    if rval[x]<q:
        continue
    for d,y in rtable[x]:
        if rval[y]>rval[x]+d:
            rval[y]=rval[x]+d
            heappush(rdij,[rval[y],y])
ans=deque()
t=val[N-1]+rval[N-1]
mod=pow(10,15)
ans.append(mod-t)
for i in range(N-2,-1,-1):
    t=min(t,val[i]+rval[i])
    ans.appendleft(mod-t)
print('\n'.join(map(str,ans)))

Submission status: Accepted

Solution code:
import heapq
import collections


class Graph:

    def __init__(self, size):
        self.size = size
        self.graph = [[] for i in range(size)]

    def add_edge(self, source, target, cost):
        self.graph[source].append((target, cost))

    def add_bidirectional_edge(self, source, target, cost):
        self.add_edge(source, target, cost)
        self.add_edge(target, source, cost)

    def min_dist_dijkstra(self, s):
        dist = [float('inf')] * self.size
        dist[s] = 0
        q = [(0, s)]
        while q:
            d, v = heapq.heappop(q)
            if dist[v] < d:
                continue
            for t, c in self.graph[v]:
                if dist[t] > dist[v] + c:
                    dist[t] = dist[v] + c
                    heapq.heappush(q, (dist[t], t))
        return dist

    def __str__(self):
        res = ''
        for i in range(self.size):
            res += str(i)
            for t, d in self.graph[i]:
                res += ' ' + str(t) + '(' + str(d) + ')'
            res += '\n'
        return res


def main():
    n, m, s, t = map(int, input().split())
    graph_a = Graph(n + 1)
    graph_b = Graph(n + 1)

    for i in range(m):
        u, v, a, b = map(int, input().split())
        graph_a.add_bidirectional_edge(u, v, a)
        graph_b.add_bidirectional_edge(u, v, b)
    cost_a = graph_a.min_dist_dijkstra(s)
    cost_b = graph_b.min_dist_dijkstra(t)

    min_costs = [(n + 1, float('inf'))]
    for i in range(n, 0, -1):
        cost = cost_a[i] + cost_b[i]
        if cost < min_costs[-1][1]:
            min_costs.append((i, cost))
    year = 0
    for i in range(n):
        while min_costs[-1][0] <= i:
            min_costs.pop()
        print(10**15 - min_costs[-1][1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin, stdout
from heapq import heappush, heappop
from itertools import repeat
def main():
    n, m, s, t = map(int, stdin.readline().split())
    dat = map(int, stdin.read().split(), repeat(10, 4 * m))
    la = [None] * (n + 1)
    xt = [None] * (4 * m)
    j = 0
    for i in xrange(m):
        x, y = dat[j], dat[j+1]
        xt[j] = la[y]
        la[y] = j
        j += 1
        xt[j] = la[x]
        la[x] = j
        j += 3
    dd = [[10 ** 15] * (n + 1), [10 ** 15] * (n + 1)]
    for i in xrange(2):
        d = dd[i]
        x = t if i else s
        d[x] = 0
        q = []
        heappush(q, (0, x))
        while q:
            co, x = heappop(q)
            y = la[x]
            if d[x] != co:
                continue
            while y is not None:
                z = dat[y]
                yy = y / 4 * 4 + 2
                c = dat[yy+i]
                if d[z] > co + c:
                    d[z] = co + c
                    heappush(q, (d[z], z))
                y = xt[y]
    ans = [0] * n
    z = 10 ** 15
    ans[n-1] = z - dd[0][n] - dd[1][n]
    for i in xrange(n - 2, -1, -1):
        ans[i] = x = z - dd[0][i+1] - dd[1][i+1]
        if ans[i+1] > x:
            ans[i] = ans[i+1]
    stdout.write(''.join('%d\n' % x for x in ans))
main()

Submission status: Accepted

Solution code:
from heapq import heappop, heappush


def dijkstra(costs, s, i):
    q = [(0, s)]
    while q:
        c, v = heappop(q)
        if costs[v] >= 0:
            continue
        costs[v] = c
        for link in links[v]:
            u = link[0]
            if costs[u] == -1:
                heappush(q, (c + link[i], u))


n, m, s, t = map(int, input().split())
links = [set() for _ in range(n)]
for _ in range(m):
    u, v, a, b = map(int, input().split())
    links[u - 1].add((v - 1, a, b))
    links[v - 1].add((u - 1, a, b))
s -= 1
t -= 1
yen_costs = [-1] * n
snk_costs = [-1] * n
dijkstra(yen_costs, s, 1)
dijkstra(snk_costs, t, 2)
total_costs = list(map(sum, zip(yen_costs, snk_costs)))
tmp = float('inf')
ans = []
ini = int(1e15)
for c in reversed(total_costs):
    tmp = min(tmp, c)
    ans.append(ini - tmp)
ans.reverse()
print('\n'.join(map(str, ans)))

Submission status: Accepted

Solution code:
# D
from collections import deque

n, m, s, t = map(int, input().split())
cost_y = [10**15]*(n+1)
cost_s = [10**15]*(n+1)

G_y = dict()
G_s = dict()
for i in range(1, n+1):
    G_y[i] = dict()
    G_s[i] = dict()

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

# for yen
cost_y[s] = 0
queue = deque([s])
while len(queue) > 0:
    u = queue.popleft()
    for v in G_y[u].keys():
        if cost_y[u] + G_y[u][v] < cost_y[v]:
            queue.append(v)
            cost_y[v] = cost_y[u] + G_y[u][v]
            
# for snuke
cost_s[t] = 0
queue = deque([t])
while len(queue) > 0:
    u = queue.popleft()
    for v in G_s[u].keys():
        if cost_s[u] + G_s[u][v] < cost_s[v]:
            queue.append(v)
            cost_s[v] = cost_s[u] + G_s[u][v]
            
res_list = []
res = cost_y[-1] + cost_s[-1]
for i in range(n, 0, -1):
    res = min(res, cost_y[i] + cost_s[i])
    res_list.append(res)
for i in range(n-1, -1, -1):
    print(10**15 - res_list[i])

Submission status: Accepted

Solution code:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect
from heapq import heappush, heappop

setrecursionlimit(10**6)

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

n, m, s, t = reads()
s, t = s-1, t-1
esyen = [[] for _ in range(n)]
essnk = [[] for _ in range(n)]

for _ in range(m):
  u, v, a, b = reads()
  u, v = u-1, v-1
  esyen[u].append((a, v))
  esyen[v].append((a, u))
  essnk[u].append((b, v))
  essnk[v].append((b, u))

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

ds = dijkstra(s, esyen)
dt = dijkstra(t, essnk)

scores = [0] * n
for i in range(n):
  scores[i] = 10**15 - (ds[i] + dt[i])

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

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

Submission status: Accepted

Solution code:
n, m, s, t = map(int, input().split())
s -= 1; t -= 1
G = [[] for i in range(n)]
for i in range(m):
    u, v, a, b = map(int, input().split())
    G[u-1].append((v-1, a, b))
    G[v-1].append((u-1, a, b))
V = 10**15
ans = [0]*n

from heapq import heappush, heappop
def dijkstra(s, m):
    D = [10**30]*n
    que = [(0, s)]
    D[s] = 0
    while que:
        co, v = heappop(que)
        if D[v] < co:
            continue
        for w, a, b in G[v]:
            c = b if m else a
            if co + c < D[w]:
                D[w] = co + c
                heappush(que, (co+c, w))
    return D
D1 = dijkstra(s, 0)
D2 = dijkstra(t, 1)
v = 10**30
for i in range(n-1, -1, -1):
    v = min(v, D1[i] + D2[i])
    ans[i] = 10**15 - v
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq

# decimal.getcontext().prec = 50
# sys.setrecursionlimit(10000)
# MOD = 10**9 + 7

def dijkstra(g, st):
    """Dijkstra method"""

    n = len(g)
    d = [float('inf')] * n
    d[st] = 0

    que = [(0, st)]     # (min_dist, vertex)
    heapq.heapify(que)

    while len(que) > 0:
        dist, v0 = heapq.heappop(que)
        if d[v0] < dist: continue
        for v1, dist in g[v0]:
            if d[v1] > d[v0] + dist:
                d[v1] = d[v0] + dist
                heapq.heappush(que, (d[v1], v1))

    return d

def solve(f):
    n, m, s, t = f.read_int_list()

    g1 = [[] for _ in range(n)]
    g2 = [[] for _ in range(n)]

    for _ in xrange(m):
        u, v, a, b = f.read_int_list()
        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))

    c1 = dijkstra(g1, s-1)
    c2 = dijkstra(g2, t-1)

    ans = [0] * n
    ans[n-1] = 10**15-c1[n-1]-c2[n-1]
    for i in xrange(n-2, -1, -1):
        ans[i] = max(ans[i+1], 10**15-c1[i]-c2[i])

    return "\n".join(map(str, ans))


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else raw_input()

    def next_case(self):
        self.file.next()
        self.case += 1

    def read_int(self): return int(self.__readline())
    def read_float(self): return float(self.__readline())
    def read_long(self): return long(self.__readline())
    def read_decimal(self): return decimal.Decimal(self.__readline())
    def read_str(self): return self.__readline()

    def read_int_list(self): return map(int, self.__readline().split())
    def read_float_list(self): return map(float, self.__readline().split())
    def read_long_list(self): return map(long, self.__readline().split())
    def read_decimal_list(self): return map(decimal.Decimal, self.__readline().split())
    def read_str_list(self): return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print "Case #%d\n"%f.case, solve(f)
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)