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())
INF = 2**63-1
data = []
for _ in range(m):
    data.append(list(map(int, input().split())))

check = [False for i in range(n+1)]
graph = [[] for i in range(n+1)]

for i in range(m):
    graph[data[i][0]].append([data[i][1], data[i][2], data[i][3]])
    graph[data[i][1]].append([data[i][0], data[i][2], data[i][3]])
city_yen_cost = [INF for i in range(n+1)]
city_yen_cost[s] = 0
queue = []
#[cost, vertex]
heapq.heappush(queue, [0, s])
while len(queue) > 0:
    now = heapq.heappop(queue)
    if check[now[1]]:
        continue
    else:
        check[now[1]] = True
        for path in graph[now[1]]:
            if city_yen_cost[now[1]]+path[1] < city_yen_cost[path[0]]:
                city_yen_cost[path[0]] = min(city_yen_cost[now[1]]+path[1], city_yen_cost[path[0]])
                if not check[path[0]]:
                    heapq.heappush(queue, [city_yen_cost[now[1]]+path[1], path[0]])




check = [False for i in range(n+1)]
city_snuke_cost = [INF for i in range(n+1)]
city_snuke_cost[t] = 0
queue = []
heapq.heappush(queue, [0, t])
while len(queue) > 0:
    now = heapq.heappop(queue)
    if check[now[1]]:
        continue
    else:
        check[now[1]] = True
        for path in graph[now[1]]:
            if city_snuke_cost[now[1]]+path[2] < city_snuke_cost[path[0]]:
                city_snuke_cost[path[0]] = min(city_snuke_cost[now[1]]+path[2], city_snuke_cost[path[0]])
                if not check[path[0]]:
                    heapq.heappush(queue, [city_snuke_cost[now[1]]+path[2], path[0]])


totalcost = [None] * (n+1)
for i in range(n+1):
    totalcost[i] = city_yen_cost[i] + city_snuke_cost[i]
for i in range(n):
    totalcost[-i-2] = min(totalcost[-i-2], totalcost[-i-1])
for i in range(n):
    print(10**15-totalcost[i+1])

Submission status: Accepted

Solution code:
import heapq
from itertools import accumulate
inf = float('inf')

def dijkstra(ad_lst, n, s):
    costs = [inf for i in range(n+1)]
    costs[s], Q = 0, []
    heapq.heappush(Q, [costs[s], s])

    while(Q != []):
        c, u = heapq.heappop(Q)
        for v, c in ad_lst[u].items():
            if costs[u] + c < costs[v]:
                heapq.heappush(Q, [costs[u] + c, v])
                costs[v] = costs[u] + c

    return costs

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

route_y = {i: {} for i in range(n+1)}
route_s = {i: {} for i in range(n+1)}
for i in range(m):
    u, v, a, b = map(int, input().split())
    route_y[u][v] = a
    route_y[v][u] = a
    route_s[u][v] = b
    route_s[v][u] = b

cost_y = dijkstra(route_y, n, s)
cost_s = dijkstra(route_s, n, t)
result = list(accumulate([y+s for y,s in zip(cost_y, cost_s)][::-1], min))
yen = 10**15
[print(yen-result[i]) for i in range(n-1, -1, -1)]

Submission status: Accepted

Solution code:
from heapq import *

n,m,s,t=map(int,input().split())
s-=1
t-=1
INF=10**19
Gyen=[[]for i in range(n)]
Gsnu=[[]for i in range(n)]
for i in range(m):
  u,v,a,b=map(int,input().split())
  u-=1
  v-=1
  Gyen[u].append([v,a])
  Gyen[v].append([u,a])
  Gsnu[u].append([v,b])
  Gsnu[v].append([u,b])

def dijkstra(G,s):
  d=[INF]*n
  d[s]=0
  visited={s}
  que=[(0,s)]
  while(que):
    p=heappop(que)
    v=p[1]
    visited.add(v)
    for node,cost in G[v]:
      if (node not in visited) and d[node]>d[v]+cost:
        d[node]=d[v]+cost
        heappush(que,(d[node],node))
  return d

yen=dijkstra(Gyen,s)
snu=dijkstra(Gsnu,t)
ans=10**15
ans_list=[]
for i in reversed(range(n)):
  ans=min(ans,yen[i]+snu[i])
  ans_list.append(10**15-ans)
print(*ans_list[::-1], sep='\n')

Submission status: Accepted

Solution code:
from heapq import *

n,m,s,t=map(int,input().split())
s-=1
t-=1
INF=float("inf")
Gyen=[[]for i in range(n)]
Gsnu=[[]for i in range(n)]
for i in range(m):
  u,v,a,b=map(int,input().split())
  u-=1
  v-=1
  Gyen[u].append([v,a])
  Gyen[v].append([u,a])
  Gsnu[u].append([v,b])
  Gsnu[v].append([u,b])

def dijkstra(G,s):
  d=[INF]*n
  d[s]=0
  visited={s}
  que=[(0,s)]
  while(que):
    p=heappop(que)
    v=p[1]
    visited.add(v)
    for node,cost in G[v]:
      if (node not in visited) and d[node]>d[v]+cost:
        d[node]=d[v]+cost
        heappush(que,(d[node],node))
  return d

yen=dijkstra(Gyen,s)
snu=dijkstra(Gsnu,t)
ans=10**15
ans_list=[]
for i in reversed(range(n)):
  ans=min(ans,yen[i]+snu[i])
  ans_list.append(10**15-ans)
for i in ans_list[::-1]:
  print(i)

Submission status: Accepted

Solution code:
from heapq import *

n,m,s,t=map(int,input().split())
s-=1
t-=1
INF=10**19
Gyen=[[]for i in range(n)]
Gsnu=[[]for i in range(n)]
for i in range(m):
  u,v,a,b=map(int,input().split())
  u-=1
  v-=1
  Gyen[u].append([v,a])
  Gyen[v].append([u,a])
  Gsnu[u].append([v,b])
  Gsnu[v].append([u,b])

def dijkstra(G,s):
  d=[INF]*n
  d[s]=0
  visited={s}
  que=[(0,s)]
  while(que):
    p=heappop(que)
    v=p[1]
    visited.add(v)
    if d[v]<p[0]:
      continue

    for node,cost in G[v]:
      if (node not in visited) and d[node]>d[v]+cost:
        d[node]=d[v]+cost
        heappush(que,(d[node],node))
  return d

yen=dijkstra(Gyen,s)
snu=dijkstra(Gsnu,t)
ans=10**15
ans_list=[]
for i in reversed(range(n)):
  ans=min(ans,yen[i]+snu[i])
  ans_list.append(10**15-ans)
print(*ans_list[::-1], sep='\n')

Submission status: Accepted

Solution code:
from heapq import *

n,m,s,t=map(int,input().split())
s-=1
t-=1
INF=float("inf")
Gyen=[[]for i in range(n)]
Gsnu=[[]for i in range(n)]
for i in range(m):
  u,v,a,b=map(int,input().split())
  u-=1
  v-=1
  Gyen[u].append([v,a])
  Gyen[v].append([u,a])
  Gsnu[u].append([v,b])
  Gsnu[v].append([u,b])

def dijkstra(G,s):
  d=[INF]*n
  d[s]=0
  visited={s}
  que=[(0,s)]
  while(que):
    p=heappop(que)
    v=p[1]
    visited.add(v)
    for node,cost in G[v]:
      if (node not in visited) and d[node]>d[v]+cost:
        d[node]=d[v]+cost
        heappush(que,(d[node],node))
  return d

yen=dijkstra(Gyen,s)
snu=dijkstra(Gsnu,t)
ans=10**15
ans_list=[]
for i in reversed(range(n)):
  ans=min(ans,yen[i]+snu[i])
  ans_list.append(10**15-ans)
print(*ans_list[::-1], sep='\n')

Submission status: Accepted

Solution code:
from heapq import *

n,m,s,t=map(int,input().split())
s-=1
t-=1
INF=10**19
Gyen=[[]for i in range(n)]
Gsnu=[[]for i in range(n)]
for i in range(m):
  u,v,a,b=map(int,input().split())
  u-=1
  v-=1
  Gyen[u].append([v,a])
  Gyen[v].append([u,a])
  Gsnu[u].append([v,b])
  Gsnu[v].append([u,b])

def dijkstra(G,s):
  que=[]
  d=[INF]*n
  d[s]=0
  visited={s}
  heappush(que,[0,s])
  while(que):
    p=heappop(que)
    v=p[1]
    visited.add(v)
    for node,cost in G[v]:
      if (node not in visited) and d[node]>d[v]+cost:
        d[node]=d[v]+cost
        heappush(que,[d[node],node])
  return d

yen=dijkstra(Gyen,s)
snu=dijkstra(Gsnu,t)
ans=10**15
ans_list=[]
for i in reversed(range(n)):
  ans=min(ans,yen[i]+snu[i])
  ans_list.append(10**15-ans)
print(*ans_list[::-1], sep='\n')

Submission status: Accepted

Solution code:
from heapq import heappop,heappush
n,m,s,t = (int(i) for i in input().split())
x,y = [[] for i in range(n+1)],[[] for i in range(n+1)]
for i in range(m):
    u,v,a,b = (int(i) for i in input().split())
    x[u].append((v,a))
    x[v].append((u,a))
    y[u].append((v,b))
    y[v].append((u,b))
def dijkstra(n,s,adj):
	dis = [float("inf") for i in range(n+1)]
	dis[s],q = 0,[[0,s]]
	while q:
		num2,num = heappop(q)
		for i,j in adj[num]:
			if dis[i]>num2+j:
				dis[i] = num2+j
				heappush(q,[dis[i],i])
	return dis
X,Y,z = dijkstra(n,s,x),dijkstra(n,t,y),[]
for i in range(1,n+1): z.append((X[i]+Y[i],i))
z,k = sorted(z),0
for i in range(n):
    while z[k][1]<=i: k+=1
    print(10**15-z[k][0])

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
from collections import defaultdict
from heapq import heappush,heappop
from itertools import accumulate
N,m,s,t=map(int,input().split())
en=[set() for i in range(N+1)]
sneek=[set() for i in range(N+1)]
for i in range(m):
    u,v,a,b=map(int,input().split())
    en[u]|={(a,v)}
    en[v]|={(a,u)}
    sneek[u]|={(b,v)}
    sneek[v]|={(b,u)}
inf=float('inf')
def makedist(first,branch):
    dist=[inf]*(N+1)
    dist[first]=0
    check=[(0,first)]
    while len(check)>0:
        d,now=heappop(check)
        if dist[now]<d:
            continue
        for lenth,nex in branch[now]:
            if d+lenth<dist[nex]:
                dist[nex]=d+lenth
                heappush(check,(d+lenth,nex))
    return dist
disten=makedist(s,en)
distsneek=makedist(t,sneek)
ans=list(accumulate([y+s for y,s in zip(disten,distsneek)][::-1],min))
big=10**15
[print(big-ans[i]) for i in range(N-1,-1,-1)]
#https://atcoder.jp/contests/soundhound2018-summer-qual/submissions/4993088

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
from collections import defaultdict
from heapq import heappush,heappop
from itertools import accumulate
N,m,s,t=map(int,input().split())
en=defaultdict(set)
sneek=defaultdict(set)
for i in range(m):
    u,v,a,b=map(int,input().split())
    en[u]|={(a,v)}
    en[v]|={(a,u)}
    sneek[u]|={(b,v)}
    sneek[v]|={(b,u)}
inf=float('inf')
def makedist(first,branch):
    dist=[inf]*(N+1)
    dist[first]=0
    check=[(0,first)]
    while len(check)>0:
        d,now=heappop(check)
        if dist[now]<d:
            continue
        for lenth,nex in branch[now]:
            if d+lenth<dist[nex]:
                dist[nex]=d+lenth
                heappush(check,(d+lenth,nex))
    return dist
disten=makedist(s,en)
distsneek=makedist(t,sneek)
ans=list(accumulate([y+s for y,s in zip(disten,distsneek)][::-1],min))
big=10**15
for i in range(N-1,-1,-1):
    print(big-ans[i])
#https://atcoder.jp/contests/soundhound2018-summer-qual/submissions/4993088

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
from collections import defaultdict
from heapq import heappush,heappop
from itertools import accumulate
N,m,s,t=map(int,input().split())
en=defaultdict(set)
sneek=defaultdict(set)
for i in range(m):
    u,v,a,b=map(int,input().split())
    en[u]|={(a,v)}
    en[v]|={(a,u)}
    sneek[u]|={(b,v)}
    sneek[v]|={(b,u)}
inf=float('inf')
def makedist(first,branch):
    dist=[inf]*(N+1)
    dist[first]=0
    check=[(0,first)]
    while len(check)>0:
        d,now=heappop(check)
        if dist[now]<d:
            continue
        for lenth,nex in branch[now]:
            if d+lenth<dist[nex]:
                dist[nex]=d+lenth
                heappush(check,(d+lenth,nex))
    return dist
disten=makedist(s,en)
distsneek=makedist(t,sneek)
x=[y+s for y,s in zip(disten,distsneek)][::-1]
ans=list(accumulate(x,min))
big=10**15
[print(big-ans[i]) for i in range(N-1,-1,-1)]

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
from collections import defaultdict
from heapq import heappush,heappop
N,m,s,t=map(int,input().split())
en=defaultdict(set)
sneek=defaultdict(set)
for i in range(m):
    u,v,a,b=map(int,input().split())
    en[u]|={(a,v)}
    en[v]|={(a,u)}
    sneek[u]|={(b,v)}
    sneek[v]|={(b,u)}
inf=float('inf')
def makedist(first,branch):
    dist=[inf]*(N+1)
    dist[first]=0
    check=[(0,first)]
    while len(check)>0:
        d,now=heappop(check)
        if dist[now]<d:
            continue
        for lenth,nex in branch[now]:
            if d+lenth<dist[nex]:
                dist[nex]=d+lenth
                heappush(check,(d+lenth,nex))
    return dist
disten=makedist(s,en)
distsneek=makedist(t,sneek)
ans=[0]*(N+1)
ans[N]=disten[N]+distsneek[N]
for i in range(N-1,0,-1):
    ans[i]=min(ans[i+1],disten[i]+distsneek[i])
big=10**15
for i in range(1,N+1):
    print(big-ans[i])

Submission status: Accepted

Solution code:
import heapq

INF = 1 << 60
MOD = 1000000007

def dijkstra(s):
    #print(s)
    global d, G, n
    d = [INF] * n
    d[s] = 0
    que = [(0, s)]
    heapq.heapify(que)

    while len(que) > 0:
        #print("que=", que)
        p = heapq.heappop(que)
        v = p[1]
        #print(v)
        if d[v] < p[0]:
            continue
        for e in G[v]:
            if d[e[0]] > d[v] + e[1]:
                d[e[0]] = d[v] + e[1]
                heapq.heappush(que, (d[e[0]], e[0]))

n, m, s, t = map(int, input().split())
u = [0] * m
v = [0] * m
a = [0] * m
b = [0] * m
G = []
for i in range(n):
    G.append([])
for i in range(m):
    u[i], v[i], a[i], b[i] = map(int, input().split())
    G[u[i] - 1].append((v[i] - 1, a[i]))
    G[v[i] - 1].append((u[i] - 1, a[i]))
#print("G=", G)
d = [0] * n
dijkstra(s - 1)
#print("d=", d)
ds = d[:]
G = []
for i in range(n):
    G.append([])
for i in range(m):
    G[u[i] - 1].append((v[i] - 1, b[i]))
    G[v[i] - 1].append((u[i] - 1, b[i]))
d = [0] * n
dijkstra(t - 1)
dst = []
for i in range(n):
    dst.append((d[i] + ds[i], i))
dst.sort()
change = 0
money = 1000000000000000
for i in range(n):
    while dst[change][1] < i:
        change += 1
    print(money - dst[change][0])

Submission status: Accepted

Solution code:
import heapq
import sys
n, m, s, t = [int(i) for i in input().split()]
s -= 1
t -= 1
snuuk_dict = dict()
yen_dict = dict()
snuuk_que = []
yen_que = []
for i in range(m):
    u, v, a, b = [int(i) for i in sys.stdin.readline().split()]
    u -= 1
    v -= 1
    if snuuk_dict.get(u) is None:
        snuuk_dict[u] = []
        yen_dict[u] = []
    if snuuk_dict.get(v) is None:
        snuuk_dict[v] = []
        yen_dict[v] = []
    snuuk_dict[u].append([b, u, v])
    snuuk_dict[v].append([b, v, u])
    yen_dict[u].append([a, u, v])
    yen_dict[v].append([a, v, u])

for i in snuuk_dict[t]:
    heapq.heappush(snuuk_que, i)
for i in yen_dict[s]:
    heapq.heappush(yen_que, i)
snuuk_ls = [-1 for i in range(n)]
yen_ls = [-1 for i in range(n)]
yen_ls[s] = 0
snuuk_ls[t] = 0
while len(yen_que) > 0:
    a, u, v = heapq.heappop(yen_que)
    if yen_ls[v] != -1:
        continue
    yen_ls[v] = a
    for i in yen_dict[v]:
        if yen_ls[i[2]] == -1:
            heapq.heappush(yen_que, [i[0] + yen_ls[v], i[1], i[2]])
while len(snuuk_que) > 0:
    b, v, u = heapq.heappop(snuuk_que)
    if snuuk_ls[u] != -1:
        continue
    snuuk_ls[u] = b
    for i in snuuk_dict[u]:
        if snuuk_ls[i[2]] == -1:
            heapq.heappush(snuuk_que,  [i[0] + snuuk_ls[u], i[1], i[2]])
sum_ls = [10** 15 - (i + j) for i, j in zip(snuuk_ls, yen_ls)]
_max = 0
for i in range(n):
    _max = sum_ls[-1-i] if sum_ls[-1-i] > _max else _max
    sum_ls[-i-1] = _max
for i in range(n):
    print(sum_ls[i])

Submission status: Accepted

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

n,m,s,t = map(int,input().split())
s-=1
t-=1
edge_a = defaultdict(set)
edge_b = defaultdict(set)
for i in range(m):
    u,v,a,b = map(int, input().split())
    u -= 1
    v -= 1
    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 djikstra(s,edges):
    n = len(edges)
    visited = {}
    q = []
    while len(visited) != n:
        if len(visited) == 0:
            next_p = s
            visited[s] = 0
        else:
            while q:
                cost, to_ = heappop(q)
                if to_ not in visited:
                    visited[to_] = cost
                    next_p = to_
                    break

        for to_, cost in edges[next_p]:
            if cost >= 0 and to_ not in visited:
                heappush(q, (visited[next_p] + cost, to_))
    return visited

cost_a = djikstra(s,edge_a)
cost_b = djikstra(t, edge_b)

ans = []
for i in range(n)[::-1]:
    nokori = 10**15 - cost_a[i] - cost_b[i]
    if len(ans) == 0:
        ans.append(nokori)
    else:
        ans.append(max(nokori, ans[-1]))
print(*ans[::-1], sep="\n")

Submission status: Accepted

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

"""
参考：https://img.atcoder.jp/soundhound2018-summer-qual/editorial.pdf
　　　https://ikatakos.com/pot/programming_algorithm/contest_history/atcoder/2018/0707_soundhound2018_summer_qual
"""

import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians, log10
if sys.version_info.minor >= 5: from math import gcd
else: from fractions import gcd 
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul, xor
from copy import copy, deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def round(x): return int((x*2+1) // 2)
def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)
def lcm_list(nums): return reduce(lcm, nums, 1)
def gcd_list(nums): return reduce(gcd, nums, nums[0])
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

# ダイクストラ(頂点数, 隣接リスト(0-indexed), 始点)
def dijkstra(N: int, nodes: list, src: int) -> list:
    # 頂点[ある始点からの最短距離]
    # (経路自体を知りたい時はここに前の頂点も持たせる)
    res = [float('inf')] * N
    # スタート位置
    que = [(0, src)]
    res[src] = 0
    # キューが空になるまで
    while len(que) != 0:
        # srcからの距離, 現在のノード
        dist, cur = heappop(que)
        # 出発ノードcurの到着ノードでループ
        for nxt, cost in nodes[cur]:
            # 今回の経路のが短い時
            if res[cur] + cost < res[nxt]:
                res[nxt] = res[cur] + cost
                # 現在の移動距離をキューの優先度として、早い方から先に処理するようにする
                heappush(que, (res[nxt], nxt))
    # ノードsrcからの最短距離リストを返却
    return res

N,M,S,T=MAP()
nodes1=[[] for i in range(N)]
nodes2=[[] for i in range(N)]
for i in range(M):
    u,v,a,b=MAP()
    # 円での始点からダイクストラ用
    nodes1[u-1].append((v-1,a))
    nodes1[v-1].append((u-1,a))
    # スヌークでの終点からダイクストラ用
    nodes2[u-1].append((v-1,b))
    nodes2[v-1].append((u-1,b))

yen=dijkstra(N,nodes1,S-1)
snuk=dijkstra(N,nodes2,T-1)

ans=[0]*N
mn=INF
# 逆順で最小値を取っていけば効率よくやれる
for i in range(N-1, -1, -1):
    ans[i]=mn=min(mn, yen[i]+snuk[i])
# 10^15から引けば答え
for i in range(N):
    print(1000000000000000-ans[i])

Submission status: Accepted

Solution code:
# coding: utf-8
import heapq
n,m,s,t=map(int,input().split())
s,t=s-1,t-1
gy=[[]for i in range(n)]
gs=[[]for i in range(n)]
for i in range(m):
    u,v,a,b=map(int,input().split())
    u,v=u-1,v-1
    gy[u].append((a,v))
    gy[v].append((a,u))
    gs[u].append((b,v))
    gs[v].append((b,u))

d_y=[9999999999999999 for i in range(n)]
d_s=[9999999999999999 for i in range(n)]
h=[(0,s)]
while len(h):
    c,x=heapq.heappop(h)
    if c<d_y[x]:
        d_y[x]=c
    else:
        continue
    for i in range(len(gy[x])):
        if gy[x][i][0]+c<d_y[gy[x][i][1]]:
            heapq.heappush(h,(gy[x][i][0]+c,gy[x][i][1]))
h=[(0,t)]
while len(h):
    c,x=heapq.heappop(h)
    if c<d_s[x]:
        d_s[x]=c
    else:
        continue
    for i in range(len(gs[x])):
        if gs[x][i][0]+c<d_s[gs[x][i][1]]:
            heapq.heappush(h,(gs[x][i][0]+c,gs[x][i][1]))
ans=[0]
for i in range(n):
    ans.append(max(10**15-d_y[n-i-1]-d_s[n-i-1],ans[i]))
for i in range(n):
    print(ans[-i-1])

Submission status: Accepted

Solution code:
import heapq
N,M,S,T = map(int,input().split())
src = [tuple(map(int,input().split())) for i in range(M)]
S,T = S-1,T-1

INF = float('inf')
def dijkstra(is_yen):
    g = [[] for i in range(N)]
    for u,v,a,b in src:
        u,v = u-1,v-1
        c = a if is_yen else b
        g[u].append((v,c))
        g[v].append((u,c))
    costs = [INF] * N
    start = S if is_yen else T
    costs[start] = 0
    hq = [(0,start)]
    heapq.heapify(hq)
    while hq:
        _,v = heapq.heappop(hq)
        for to,c in g[v]:
            if costs[v]+c >= costs[to]: continue
            costs[to] = costs[v]+c
            heapq.heappush(hq, (costs[to],to))
    return costs

yens = dijkstra(1)
snuuks = dijkstra(0)

ans = [None] * N
ans[-1] = yens[-1] + snuuks[-1]
for i in reversed(range(N-1)):
    ans[i] = min(ans[i+1], yens[i]+snuuks[i])

for a in ans:
    print(10**15 - a)

Submission status: Accepted

Solution code:
import math, string, itertools, fractions, collections, re, array, bisect, sys, random, time, copy, functools
from heapq import heappush, heappop, heappushpop, heapify, heapreplace
input = sys.stdin.readline

N, M, S, T = [int(_) for _ in input().split()]
UVAB = [[int(_) for _ in input().split()] for _ in range(M)]
G1 = collections.defaultdict(lambda: collections.defaultdict(int))
G2 = collections.defaultdict(lambda: collections.defaultdict(int))

for u, v, a, b in UVAB:
    u -= 1
    v -= 1
    G1[u][v] = G1[v][u] = a
    G2[u][v] = G2[v][u] = b


def dijkstra(V, G, start):
    INF = float('inf')
    D = [INF for _ in range(V)]
    D[start] = 0
    H = [(0, start)]
    while H:
        du, u = heappop(H)
        if D[u] < du:
            continue
        for v, d in G[u].items():
            if D[v] > du + d:
                D[v] = du + d
                heappush(H, (D[v], v))
    return D


D1 = dijkstra(N, G1, S - 1)
D2 = dijkstra(N, G2, T - 1)

D = [10**15 - sum(_) for _ in zip(D1, D2)]
for i in range(N - 1, 0, -1):
    D[i - 1] = max(D[i - 1], D[i])
print(*D, sep='\n')

Submission status: Accepted

Solution code:
import math, string, itertools, fractions, collections, re, array, bisect, sys, random, time, copy, functools
from heapq import heappush, heappop, heappushpop, heapify, heapreplace
#input = sys.stdin.readline

N, M, S, T = [int(_) for _ in input().split()]
UVAB = [[int(_) for _ in input().split()] for _ in range(M)]
G1 = collections.defaultdict(lambda: collections.defaultdict(int))
G2 = collections.defaultdict(lambda: collections.defaultdict(int))

for u, v, a, b in UVAB:
    u -= 1
    v -= 1
    G1[u][v] = G1[v][u] = a
    G2[u][v] = G2[v][u] = b


def dijkstra(V, G, start):
    INF = float('inf')
    D = [INF for _ in range(V)]
    D[start] = 0
    H = [(0, start)]
    while H:
        du, u = heappop(H)
        if D[u] < du:
            continue
        for v, d in G[u].items():
            if D[v] > du + d:
                D[v] = du + d
                heappush(H, (D[v], v))
    return D


D1 = dijkstra(N, G1, S - 1)
D2 = dijkstra(N, G2, T - 1)

D = [10**15 - sum(_) for _ in zip(D1, D2)]
for i in range(N - 1, 0, -1):
    D[i - 1] = max(D[i - 1], D[i])
print(*D, sep='\n')

Submission status: Accepted

Solution code:
import math, string, itertools, fractions, collections, re, array, bisect, sys, random, time, copy, functools
from heapq import heappush, heappop, heappushpop, heapify, heapreplace

N, M, S, T = [int(_) for _ in input().split()]
UVAB = [[int(_) for _ in input().split()] for _ in range(M)]
G1 = collections.defaultdict(lambda: collections.defaultdict(int))
G2 = collections.defaultdict(lambda: collections.defaultdict(int))

for u, v, a, b in UVAB:
    u -= 1
    v -= 1
    G1[u][v] = G1[v][u] = a
    G2[u][v] = G2[v][u] = b


def dijkstra(V, G, start):
    INF = float('inf')
    D = [INF for _ in range(V)]
    D[start] = 0
    H = [(0, start)]
    while H:
        du, u = heappop(H)
        if D[u] < du:
            continue
        for v, d in G[u].items():
            if D[v] > du + d:
                D[v] = du + d
                heappush(H, (D[v], v))
    return D


D1 = dijkstra(N, G1, S - 1)
D2 = dijkstra(N, G2, T - 1)

D = [10**15 - sum(_) for _ in zip(D1, D2)]
for i in range(N - 1, 0, -1):
    D[i - 1] = max(D[i - 1], D[i])
print(*D, sep='\n')

Submission status: Accepted

Solution code:
import heapq
from collections import defaultdict

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

graph_y = defaultdict(dict)
graph_s = defaultdict(dict)

for i in range(m):
	u, v, a, b = list(map(int, input().split()))
	graph_y[u - 1][v - 1] = a
	graph_y[v - 1][u - 1] = a
	graph_s[u - 1][v - 1] = b
	graph_s[v - 1][u - 1] = b

dist_node_ys = defaultdict(lambda: float("inf"))
dist_node_ys[s - 1] = 0

Q = []
heapq.heappush(Q, (dist_node_ys[s - 1], s - 1))

while Q: 
	dis, v = heapq.heappop(Q)
	if dist_node_ys[v] < dis:
		continue
	for i in graph_y[v]:
		u = i
		w = graph_y[v][i]
		alt = dis + w
		if dist_node_ys[u] > alt:
			dist_node_ys[u] = alt
			heapq.heappush(Q, (alt, u))


dist_node_st = defaultdict(lambda: float("inf"))
dist_node_st[t - 1] = 0

Q = []
heapq.heappush(Q, (dist_node_st[t - 1], t - 1))

while Q: 
	dis, v = heapq.heappop(Q)
	if dist_node_st[v] < dis:
		continue
	for i in graph_s[v]:
		u = i
		w = graph_s[v][i]
		alt = dis + w
		if dist_node_st[u] > alt:
			dist_node_st[u] = alt
			heapq.heappush(Q, (alt, u))

ansL = []
X = []
for i in range(n):
	heapq.heappush(X, dist_node_ys[n - 1 - i] + dist_node_st[n - 1 - i])
	ansL.append(X[0])

for i in range(1, n + 1):
	print(1000000000000000 - ansL[- i])

Submission status: Accepted

Solution code:
from heapq import heapify,heappop,heappush
N,M,s,t=map(int,input().split())
Graph1=[set() for i in range(N)]
Graph2=[set() for i in range(N)]
inf=float("inf")
for i in range(M):
  u,v,a,b=map(int,input().split())
  Graph1[u-1].add((a,v-1))
  Graph1[v-1].add((a,u-1))
  Graph2[u-1].add((b,v-1))
  Graph2[v-1].add((b,u-1))
  
def dijkstra(s,n,links):
  cost=[inf]*n
  visited=[False]*n
  cost[s]=0
  heap=[(0,s)]
  heapify(heap)
  while heap:
    hc,hp=heappop(heap)
    if not visited[hp]:
      visited[hp]=True
      for c,p in links[hp]:
        if not visited[p]:
          if c+hc<=cost[p]:
            cost[p]=c+hc
            heappush(heap,(cost[p],p))
  return cost
 
cost1=dijkstra(s-1,N,Graph1)
cost2=dijkstra(t-1,N,Graph2)

ans=[0]*N
a=inf
for i in range(N)[::-1]:
  a=min(a,cost1[i]+cost2[i])
  ans[i]=10**15-a
for i in ans:
  print(i)

Submission status: Accepted

Solution code:
import heapq
INF=10**15
class weighted_graph():
    Vertex= 1
    AdjList=[dict() for i in range(Vertex)]
    Edge=[]
    directed=False
    def __init__(self,size,directed=False):
        self.directed=directed
        self.Vertex=size
        self.AdjList=[dict() for i in range(self.Vertex)]
    def add_edge(self,start,finish,weight):
        self.AdjList[start][finish]=weight
        self.Edge.append((start,finish,weight))
        if not(self.directed):
            self.AdjList[finish][start]=weight
    def Dijkstra(self, st):
        dist=[INF for i in range(N)]
        dist[st]=0
        q=[]
        heapq.heappush(q,(0,st))
        while (len(q)!=0):
            prc,src=heapq.heappop(q)
            if dist[src]<prc:
                continue
            for dest in self.AdjList[src]:
                cost=self.AdjList[src][dest]
                if dist[dest]>dist[src]+cost:
                    dist[dest]=dist[src]+cost
                    heapq.heappush(q,(dist[dest],dest))                
        return dist
    def Warshall_Floyd(self):
        d=[[INF for i in range(self.Vertex)] for i in range(self.Vertex)]
        for seq in self.Edge:
            d[seq[0]][seq[1]]=seq[2]
            if not(self.directed):
                d[seq[1]][seq[0]]=seq[2]
        for k in range(self.Vertex):
            for i in range(self.Vertex):
                for j in range(self.Vertex):
                    if d[i][j]>d[i][k]+d[k][j]:
                        d[i][j]=d[i][k]+d[k][j]
        return d
N,M,s,t=map(int,input().split())
s-=1;t-=1
G=weighted_graph(N,directed=False)
H=weighted_graph(N,directed=False)
for _ in range(M):
    u,v,a,b=map(int,input().split())
    G.add_edge(u-1,v-1,a)
    H.add_edge(u-1,v-1,b)
dist1=G.Dijkstra(s)
dist2=H.Dijkstra(t)
tmp=[INF-dist1[i]-dist2[i] for i in range(N)]
ans=[0 for i in range(N)]
ans[-1]=tmp[-1]
for i in range(N-1)[::-1]:
    ans[i]=max(ans[i+1],tmp[i])
for i in ans:
    print(i)