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: Time Limit Exceeded

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

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

MAX_VAL = 10**20
uvab =  [list(map(int,input().split())) for _ in range(m)]
jpy_cost = defaultdict(lambda :defaultdict(lambda :MAX_VAL))
snuke_cost = defaultdict(lambda :defaultdict(lambda :MAX_VAL))

class Graph:
  def __init__(self):
    self.nodes = set()
    self.edges = defaultdict(list)
    self.distances = {}

  def add_node(self, value):
    self.nodes.add(value)

  def add_edge(self, from_node, to_node, distance):
    self.edges[from_node].append(to_node)
    self.edges[to_node].append(from_node)
    self.distances[(from_node, to_node)] = distance

jpy_graph = Graph()
snuke_graph= Graph()

for i in range(n):
    jpy_graph.add_node(i)
    snuke_graph.add_node(i)

for u,v,a,b in uvab:
    u=u-1
    v=v-1
    jpy_cost[u][v] = a
    jpy_cost[v][u] =a
    snuke_cost[u][v]=b
    snuke_cost[v][u]=b
    jpy_graph.add_edge(u,v,a)
    jpy_graph.add_edge(v,u,a)
    snuke_graph.add_edge(u, v, b)
    snuke_graph.add_edge(v, u, b)

def dijsktra(graph, initial):
  visited = {initial: 0}
  path = {}

  nodes = set(graph.nodes)

  while nodes:
    min_node = None
    for node in nodes:
      if node in visited:
        if min_node is None:
          min_node = node
        elif visited[node] < visited[min_node]:
          min_node = node

    if min_node is None:
      break

    nodes.remove(min_node)
    current_weight = visited[min_node]

    for edge in graph.edges[min_node]:
      weight = current_weight + graph.distances[(min_node, edge)]
      if edge not in visited or weight < visited[edge]:
        visited[edge] = weight
        path[edge] = min_node

  return visited

jpy_dijk =  dijsktra(jpy_graph,s-1)
snuke_dijk = dijsktra(snuke_graph,t-1)

#print(s,t)
#print(jpy_dijk)
#print(snuke_dijk)
#print([jpy_dijk[i]+snuke_dijk[i] for i in range(n)])

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

Submission status: Time Limit Exceeded

Solution code:
n,m,s,t = map(int,input().split())
en = []
su = []
for i in range(m):
    x1,y1,z1,a1=[int(i) for i in input().split()]
    en.append([x1-1,y1-1,z1])
    en.append([y1-1,x1-1,z1])
    su.append([x1-1,y1-1,a1])
    su.append([y1-1,x1-1,a1])
def shortest_path(edge,num_v,start):
    inf = float("inf")
    d = [inf for f in range(num_v)]
    d[start] = 0;
    while True:
        update = False
        for e in edge:
            if d[e[0]] != inf and d[e[1]] > d[e[0]] + e[2]:
                d[e[1]] = d[e[0]] + e[2]
                update = True
        if not update:
            break
    return d
from collections import deque
ans = deque([])
tori = shortest_path(en,n,s-1)
for i in range(n):
  kae = shortest_path(su,n,i)[t-1]
  ans.append(kae+tori[i])
moti = 10**15
for i in range(n):
  c = min(ans)
  print(moti-c)
  ans.popleft()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(n, m, s, t, UVAB):
    g = defaultdict(dict)
    for u, v, a, b in UVAB:
        g[u][v] = (a, b)
        g[v][u] = (a, b)

    def find(i):
        c = 10**15
        def d(s, ck):
            dist = [0 if s == i else sys.maxsize for i in range(n+1)]
            p = [None for i in range(n+1)]
            q =[]
            for i in range(1, n+1):
                heapq.heappush(q, (dist[1], i))
            while q:
                d_, u = heapq.heappop(q)
                for v, cost in g[u].items():
                    alt = dist[u] + cost[ck]
                    if dist[v] > alt:
                        dist[v] = alt
                        p[v] = u
                        heapq.heappush(q, (dist[u], v))
            return dist

        dist0 = d(s, 0)
        costs = []
        # print('--')
        for j in range(i+1, n+1):
            costs.append(d(j, 1)[t] + dist0[j])
        #     print( d(j, 1), d(j, 1)[t],dist0[j], t)
        # print(costs)
        return c - min(costs)
    ans = []
    for i in range(n):
        ans.append(find(i))

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


def main():
    n, m, s, t = read_int_n()
    UVAB = [read_int_n() for _ in range(m)]

    
    print(slv(n, m, s, t, UVAB))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

MAX_VAL = 10**20
uvab =  [list(map(int,input().split())) for _ in range(m)]
jpy_cost = defaultdict(lambda :defaultdict(lambda :MAX_VAL))
snuke_cost = defaultdict(lambda :defaultdict(lambda :MAX_VAL))


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


def dijkstra(glaph, start, goal,g_size):
    def get_path(start, goal, prev):
        path = []
        now = goal
        path.append(now)
        while True:
            path.append(prev[now])
            if prev[now] == start: break
            now = prev[now]
        path.reverse()
        return path
    #g_size = len(glaph)
    visited = [False] * g_size
    cost = [MAX_VAL] * g_size
    prev = [None] * g_size
    cost[start] = 0
    prev[start] = start
    now = start
    while True:
        min = MAX_VAL
        next = -1
        visited[now] = True
        for i in range(g_size):
        #for i in glaph[now]:
            if visited[i]: continue
            if glaph[now][i]:
                tmp_cost = glaph[now][i] + cost[now]
                if cost[i] > tmp_cost:
                    cost[i] = tmp_cost
                    prev[i] = now
            if min > cost[i]:
                min = cost[i]
                next = i
        if next == -1: break
        now = next

    return cost
    #return [get_path(start, goal, prev), cost[goal]]



def dijkstra2(graph, source):
    inf = float('inf')
    dist = defaultdict(lambda: inf)
    previous = {}
    visited = set()

    dist[source] = 0
    graph_nodes = [(dist[n], n) for n in graph.keys()]
    heapify(graph_nodes)
    while graph_nodes:
        _, u = heappop(graph_nodes)
        visited.add(u)
        if dist[u] == inf:
            break

        for v in graph[u]:
            if v in visited:
                continue
            alt = dist[u] + graph[u][v]
            if alt < dist[v]:
                i = graph_nodes.index((dist[v], v))
                graph_nodes[i] = (alt, v)
                heapify(graph_nodes)

                dist[v] = alt
                previous[v] = u

    return dist


#jpy_dijk = (dijkstra(jpy_cost,s-1,s-1,n))
#snuke_dijk = (dijkstra(snuke_cost,t-1,t-1,n))
jpy_dijk = (dijkstra2(jpy_cost,s-1))
snuke_dijk = (dijkstra2(snuke_cost,t-1))

#print(s,t)
#print(jpy_dijk)
#print(snuke_dijk)
#print([jpy_dijk[i]+snuke_dijk[i] for i in range(n)])

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n,m,s,t =list(map(int,input().split()))

MAX_VAL = 10**20
uvab =  [list(map(int,input().split())) for _ in range(m)]
jpy_cost = defaultdict(lambda :defaultdict(lambda :MAX_VAL))
snuke_cost = defaultdict(lambda :defaultdict(lambda :MAX_VAL))


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


def dijkstra(glaph, start, goal,g_size):
    def get_path(start, goal, prev):
        path = []
        now = goal
        path.append(now)
        while True:
            path.append(prev[now])
            if prev[now] == start: break
            now = prev[now]
        path.reverse()
        return path
    #g_size = len(glaph)
    visited = [False] * g_size
    cost = [MAX_VAL] * g_size
    prev = [None] * g_size
    cost[start] = 0
    prev[start] = start
    now = start
    while True:
        min = MAX_VAL
        next = -1
        visited[now] = True
        for i in range(g_size):
        #for i in glaph[now]:
            if visited[i]: continue
            if glaph[now][i]:
                tmp_cost = glaph[now][i] + cost[now]
                if cost[i] > tmp_cost:
                    cost[i] = tmp_cost
                    prev[i] = now
            if min > cost[i]:
                min = cost[i]
                next = i
        if next == -1: break
        now = next

    return cost
    #return [get_path(start, goal, prev), cost[goal]]


jpy_dijk = (dijkstra(jpy_cost,s-1,s-1,n))
snuke_dijk = (dijkstra(snuke_cost,t-1,t-1,n))

#print(s,t)
#print(jpy_dijk)
#print(snuke_dijk)
#print([jpy_dijk[i]+snuke_dijk[i] for i in range(n)])

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

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop 
INF = 10 ** 100
n, m, s, t = map(int, input().split())
s -= 1
t -= 1
init = 10 ** 15
edges = [[] for _ in range(n * 2)]
for _ in range(m):
  u, v, a, b = map(int, input().split())
  u -= 1
  v -= 1
  edges[u].append((v, a))
  edges[v].append((u, a))
  edges[u + n].append((v + n, b))
  edges[v + n].append((u + n, b))

for i in range(n):
  edges[i].append((i + n, 0))

for i in range(n):
  if i >= 1:
    edges[i - 1].remove((i - 1 + n, 0))

  que = []
  heappush(que, (0, s))
  costs = [INF] * (n * 2)
  costs[s] = 0
  while que:
    total, node = heappop(que)
    for to, dist in edges[node]:
      if costs[to] > total + dist:
        costs[to] = total + dist
        heappush(que, (total + dist, to))
  print(init - costs[t + n])

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush,heappop
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=[]
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.append(mod-t)
for i in range(N-1,-1,-1):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush,heappop
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=[]
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.append(mod-t)
ans=ans[::-1]
for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n,m,s,t =list(map(int,input().split()))

uvab =  [list(map(int,input().split())) for _ in range(m)]
jpy_cost = defaultdict(lambda :defaultdict(lambda :10000000000))
snuke_cost = defaultdict(lambda :defaultdict(lambda :10000000000))


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


def dijkstra(glaph, start, goal,g_size):
    def get_path(start, goal, prev):
        path = []
        now = goal
        path.append(now)
        while True:
            path.append(prev[now])
            if prev[now] == start: break
            now = prev[now]
        path.reverse()
        return path

    MAX_VAL = 0x1000000000000000
    #g_size = len(glaph)
    visited = [False] * g_size
    cost = [MAX_VAL] * g_size
    prev = [None] * g_size
    cost[start] = 0
    prev[start] = start
    now = start
    while True:
        min = MAX_VAL
        next = -1
        visited[now] = True
        for i in range(g_size):
            if visited[i]: continue
            if glaph[now][i]:
                tmp_cost = glaph[now][i] + cost[now]
                if cost[i] > tmp_cost:
                    cost[i] = tmp_cost
                    prev[i] = now
            if min > cost[i]:
                min = cost[i]
                next = i
        if next == -1: break
        now = next

    return cost
    #return [get_path(start, goal, prev), cost[goal]]


jpy_dijk = (dijkstra(jpy_cost,s-1,0,n))
snuke_dijk = (dijkstra(snuke_cost,t-1,0,n))

res = []
min_val = 1000000000000
for i in reversed(range(n)):
    val = jpy_dijk[i]+ snuke_dijk[i]
    min_val=min(min_val,val)
    res.append(min_val)

for x in reversed(res):
    print(10**15-  x)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

def dijkstra(graph, start):
  N = len(graph)
  d = [INF] * N
  d[start] = 0
  f = [False] * N
  q = [(0, start)]
  while q:
    c,u = heapq.heappop(q)
    if f[u]: continue
    d[u] = c
    f[u] = True
    for c,v in graph[u]:
      if not f[v]:
        heapq.heappush(q, (c + d[u], v))
  return d

N,M,s,t = IL()
grapha = [[] for i in range(N)]
graphb = [[] for i in range(N)]
for _ in range(M):
  u,v,a,b = IL()
  grapha[u-1].append((a,v-1))
  grapha[v-1].append((a,u-1))
  graphb[u-1].append((b,v-1))
  graphb[v-1].append((b,u-1))
  
da = dijkstra(grapha, s-1)
db = dijkstra(graphb, t-1)

moto = 10**15
ans = [moto-INF]
for i in range(N)[::-1]:
  ans.append(max(ans[-1],moto-da[i]-db[i]))
for i in range(1,N+1)[::-1]:
  print(ans[i])

Submission status: Accepted

Solution code:
import sys
import heapq

input = sys.stdin.buffer.readline
in_n = lambda: int(input())
in_nn = lambda: map(int, input().split())
in_s = lambda: input().rstrip().decode('utf-8')
in_map = lambda: [s == ord('.') for s in input() if s != ord('\n')]

MOD = 10**9 + 7
INF = 8 * 10**18


def dijkstra(N, s0, edge):

    d = [INF] * N
    used = [False] * N
    edgelist = [(0, s0)]
    heapq.heapify(edgelist)

    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = True
        for e in edge[v]:
            if d[e[1]] <= (e[0] + d[v]) or used[e[1]]:
                continue
            heapq.heappush(edgelist, [e[0] + d[v], e[1]])
    return d


def main():

    N, M, S, T = in_nn()
    S, T = S - 1, T - 1

    edge_yen = [[] for _ in range(N)]
    edge_sun = [[] for _ in range(N)]

    for i in range(M):
        u, v, a, b = in_nn()
        u, v = u - 1, v - 1
        edge_yen[u].append((a, v))
        edge_yen[v].append((a, u))
        edge_sun[u].append((b, v))
        edge_sun[v].append((b, u))

    d_s_yen = dijkstra(N, S, edge_yen)
    d_t_sun = dijkstra(N, T, edge_sun)

    money = 10**15
    year = [0] * N
    for i in range(N):
        year[i] = money - d_s_yen[i] - d_t_sun[i]

    ans = [0] * N
    year_max = 0
    for i in range(N - 1, -1, -1):
        year_max = max(year_max, year[i])
        ans[i] = year_max

    print('\n'.join(map(str, ans)))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq

N, M, s, t = map(int, input().split())
inf = 10 ** 18

def dijkstra(start, G):
    q = [(0, start)]
    heapq.heapify(q)
    cost = [inf] * N
    cost[start] = 0
    while q:
        c, v = heapq.heappop(q)
        if c > cost[v]:
            continue
        for d, u in G[v]:
            tmp = d + cost[v]
            if tmp < cost[u]:
                cost[u] = tmp
                heapq.heappush(q, (tmp, u))
    return cost

# G = [(cost, edge), ...]
Ga = [[] for _ in range(N)]
Gb = [[] for _ in range(N)]
for _ in range(M):
    u, v, a, b = map(int, input().split())
    u, v = u - 1, v - 1
    Ga[u].append((a, v))
    Ga[v].append((a, u))
    Gb[u].append((b, v))
    Gb[v].append((b, u))

s2i = dijkstra(s - 1, Ga)
i2t = dijkstra(t - 1, Gb)

c = [0] * N
tmp = 10 ** 18
for i in range(N):
    tmp = min(tmp, s2i[-(i + 1)] + i2t[-(i + 1)])
    c[-(i + 1)] = tmp

for cc in c:
    print(10 ** 15 - cc)

Submission status: Accepted

Solution code:
# D - Saving Snuuk
from heapq import heappop, heappush
INF = float('inf')
def dijkstra(s,n,g): # sからの最短距離 頂点数n g[v]=[(u1,w1),(u2,w2)....]:vからuへの有向辺があり、重みw
  que = []
  d = [INF for _ in range(n)]
  d[s] = 0
  heappush(que,(0,s))
  while len(que) > 0:
    p = heappop(que)
    v = p[1]
    if d[v] < p[0]:
      continue
    for u,w in g[v]:
      if d[u] > d[v]+w:
        d[u] = d[v]+w
        heappush(que,(d[u],u))
  return d

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

de = dijkstra(s,n,ge)
ds = dijkstra(t,n,gs)
c = []
for i in range(n):
  c.append((de[i]+ds[i],i))
c.sort()
j = 0
for i in range(n):
  while(c[j][1] < i):
    j += 1
  print(10**15-c[j][0])

Submission status: Accepted

Solution code:
from networkx import*
(N,M,*S),*t=[map(int,t.split())for t in open(0)]
G=Graph()
for u,v,a,b in t:G.add_edge(u,v,y=a,s=b)
b=m=10**15
y,s,*r=map(eval(dir()[761]),(G,G),S,(m,m),'ys')
while N:b=min(b,y[N]+s[N]);r+=m-b,;N-=1
print(*r[::-1])

Submission status: Accepted

Solution code:
from networkx import*
(N,M,S,T,*r),*t=[map(int,t.split())for t in open(0)]
G=Graph()
for u,v,a,b in t:G.add_edge(u,v,y=a,s=b)
b=m=10**15
y,s=map(eval(dir()[763]),(G,G),(S,T),(m,m),'ys')
while N:b=min(b,y[N]+s[N]);r+=m-b,;N-=1
print(*r[::-1])

Submission status: Accepted

Solution code:
from networkx import*
(N,M,S,T,*r),*t=[map(int,t.split())for t in open(0)]
G=Graph()
for u,v,a,b in t:G.add_edge(u,v,y=a,s=b)
b=m=10**15
y,s=map(f:=eval(dir()[763]),(G,G),(S,T),(m,m),'ys')
while N:b=min(b,y[N]+s[N]);r+=m-b,;N-=1
print(*r[::-1])

Submission status: Accepted

Solution code:
import sys
from networkx import*
i=sys.stdin.readline
m=10**15
N,M,S,T=map(int,i().split())
G=Graph()
G.add_nodes_from(range(1,N+1))
for _ in range(M):u,v,a,b=map(int,i().split());G.add_edge(u,v,y=a,s=b)
y=single_source_dijkstra_path_length(G,S,weight='y')
s=single_source_dijkstra_path_length(G,T,weight='s')
a=[m]*(N+1)
for j in range(N,0,-1):a[j-1]=min(a[j],y[j]+s[j])
for x in a[:N]:print(m-x)

Submission status: Accepted

Solution code:
import sys
from networkx import*
i=sys.stdin.readline
m=10**15
N,M,S,T=map(int,i().split())
G=Graph()
G.add_nodes_from(range(1,N+1))
for _ in range(M):
  u,v,a,b=map(int,input().split())
  G.add_edge(u,v,y=a,s=b)
y=single_source_dijkstra_path_length(G,S,weight='y')
s=single_source_dijkstra_path_length(G,T,weight='s')
a=[m]*(N+1)
for j in range(N,0,-1):
  a[j-1]=min(a[j],y[j]+s[j])
for x in a[:N]:
  print(m-x)

Submission status: Accepted

Solution code:
import sys
import networkx as nx

input = sys.stdin.buffer.readline

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

G = nx.Graph()
G.add_nodes_from(range(1, N + 1))
for _ in range(M):
    u, v, a, b = map(int, input().split())
    G.add_edge(u, v, yen=a, snuuk=b)

yen_path = nx.single_source_dijkstra_path_length(G, S, weight='yen')
snuuk_path = nx.single_source_dijkstra_path_length(G, T, weight='snuuk')

ans = [MAX] * (N + 1)
for i in range(N, 0, -1):
    ans[i - 1] = min(ans[i], yen_path[i] + snuuk_path[i])
for x in ans[:N]:
    print(MAX - x)

Submission status: Accepted

Solution code:
n,m,s,t=map(int,input().split())
yen=[[]*n for i in range(n)]
sunuke=[[]*n for i in range(n)]
for i in range(m):
  u,v,a,b=map(int,input().split())
  yen[u-1].append((a,v-1))
  yen[v-1].append((a,u-1))
  sunuke[u-1].append((b,v-1))
  sunuke[v-1].append((b,u-1))
  


#ダイクストラ法
#n:頂点数　s:始点　es:隣接リスト表現
import heapq
def dijkstra(n,s,es):
  d=[float("INF")]*n
  d[s]=0
  used=[False]*n
  used[s]=True
  edgelist=[]
  for to in es[s]:
    heapq.heappush(edgelist,to)
  while len(edgelist)>0:
    minedge=heapq.heappop(edgelist)
    v=minedge[1]
    if used[v]:
      continue
    used[v]=True
    d[v]=minedge[0]
    for to in es[v]:
      heapq.heappush(edgelist,(d[v]+to[0],to[1]))
  return d

ans=[0]*n
d_yen=dijkstra(n,s-1,yen)
d_sunuke=dijkstra(n,t-1,sunuke)
check=float("INF")
for i in range(n-1,-1,-1):
  check=min(d_yen[i]+d_sunuke[i],check)
  ans[i]=check


for j in range(n):
  print(10**15-ans[j])

Submission status: Accepted

Solution code:
from heapq import heappush,heappop

def main():
  n,m,s,t=map(int,input().split())
  INF=10**20
  G1,G2 = [{} for _ in range(n)],[{} for _ in range(n)]
  for i in range(m):
    u,v,a,b=map(int,input().split())
    G1[u-1][v-1] = G1[v-1][u-1] = a
    G2[u-1][v-1] = G2[v-1][u-1] = b

  def dijkstra(G,start = 0):
      d = [INF for i in range(len(G))]
      d[start] = 0
      que = []
      heappush(que, (0, start))

      while len(que):
          p = heappop(que)
          v = p[1]
          if d[v] < p[0]:
              continue
          for u in G[v].keys():
              if d[u] > d[v] + G[v][u]:
                  d[u] = d[v] + G[v][u]
                  heappush(que, (d[u], u))
      return d

  d1 = dijkstra(G1,s-1)
  d2 = dijkstra(G2,t-1)

  ans=[]
  MIN = INF
  for i in range(n-1,-1,-1):
    MIN = min(MIN,d1[i]+d2[i])
    if i == s-1:
      MIN = min(MIN,d2[s-1])
    if i == t-1:
      MIN = min(MIN,d1[t-1])

    ans.append(MIN)

  for a in reversed(ans):
    print(10**15-a)
  
if __name__=="__main__":
  main()

Submission status: Accepted

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

def main():
  n,m,s,t=map(int,input().split())
  INF=10**20
  G1,G2 = [{} for _ in range(n)],[{} for _ in range(n)]
  for i in range(m):
    u,v,a,b=map(int,input().split())
    G1[u-1][v-1] = G1[v-1][u-1] = a
    G2[u-1][v-1] = G2[v-1][u-1] = b

  def dijkstra(G,start = 0):
      d = [INF for i in range(len(G))]
      d[start] = 0
      que = []
      heappush(que, (0, start))

      while len(que):
          p = heappop(que)
          v = p[1]
          if d[v] < p[0]:
              continue
          for u in G[v].keys():
              if d[u] > d[v] + G[v][u]:
                  d[u] = d[v] + G[v][u]
                  heappush(que, (d[u], u))
      return d

  d1 = dijkstra(G1,s-1)
  d2 = dijkstra(G2,t-1)

  ans=deque()
  MIN = INF
  for i in range(n-1,-1,-1):
    MIN = min(MIN,d1[i]+d2[i])
    if i == s-1:
      MIN = min(MIN,d2[s-1])
    if i == t-1:
      MIN = min(MIN,d1[t-1])

    ans.appendleft(10**15-MIN)

  print(*ans)
  
if __name__=="__main__":
  main()