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: Wrong Answer

Solution code:
n,m,s,t=list(map(int, input().strip().split()))
yen=[[float('inf')]*n for i in range(n)]
snk=[[float('inf')]*n for i in range(n)]
for i in range(n):
    yen[i][i]=0
    snk[i][i]=0
for i in range(m):
    u,v,a,b=list(map(int, input().strip().split()))
    yen[u-1][v-1]=a
    yen[v-1][u-1]=a
    snk[u-1][v-1]=b
    snk[v-1][u-1]=b
import heapq
def djcstra(frm,D):
    dist=D[frm]
    Q=[(dist[i],i) for i in range(len(D))]
    heapq.heapify(Q)
    itm=heapq.heappop(Q)
    while len(Q):
        du,u=heapq.heappop(Q)
        for i,d in enumerate(D[u]):
            if dist[i] >dist[u]+d:
                dist[i]=dist[u]+d
    return dist
yen_cost=djcstra(s-1,yen)
snk_cost=djcstra(t-1,snk)
sumyensnk=[i+j for i,j in zip(yen_cost,snk_cost)]
min_snk=[float('inf')]*n
tmp=float('inf')
for i in range(n)[::-1]:
    min_snk[i] = min(sumyensnk[i],tmp)
    tmp = min_snk[i]
for sumsnk in min_snk:
    print(10**15-sumsnk)

Submission status: Wrong Answer

Solution code:
def djcstra(frm,D):
    dist=D[frm]
    Q=sorted(range(len(D)) , key=lambda x:-dist[x])
    Q.pop(-1)
    while len(Q):
        u=Q.pop(-1)
        for i,d in enumerate(D[u]):
            if dist[i] >dist[u]+d:
                dist[i]=dist[u]+d
        Q=sorted(sorted(Q , key=lambda x:-dist[x]))
    return dist
n,m,s,t=list(map(int, input().strip().split()))
yen=[[float('inf')]*n for i in range(n)]
snk=[[float('inf')]*n for i in range(n)]
for i in range(n):
    yen[i][i]=0
    snk[i][i]=0
for i in range(m):
    u,v,a,b=list(map(int, input().strip().split()))
    yen[u-1][v-1]=a
    yen[v-1][u-1]=a
    snk[u-1][v-1]=b
    snk[v-1][u-1]=b
yen_cost=djcstra(s-1,yen)
snk_cost=djcstra(t-1,snk)
sumyensnk=[i+j for i,j in zip(yen_cost,snk_cost)]
min_snk=[float('inf')]*n
tmp=float('inf')
for i in range(n)[::-1]:
    min_snk[i] = min(sumyensnk[i],tmp)
    tmp = min_snk[i]
for s in min_snk:
    print(10**15-s)

Submission status: Wrong Answer

Solution code:
def djcstra(frm,D):
    dist=D[frm]
    Q=sorted(range(len(D)) , key=lambda x:-dist[x])
    Q.pop(-1)
    while len(Q):
        u=Q.pop(-1)
        for i,d in enumerate(D[u]):
            if dist[i] >dist[u]+d:
                dist[i]=dist[u]+d
        Q=sorted(sorted(Q , key=lambda x:-dist[x]))
    return dist
n,m,s,t=list(map(int, input().strip().split()))
yen=[[float('inf')]*n for i in range(n)]
snk=[[float('inf')]*n for i in range(n)]
for i in range(n):
    yen[i][i]=0
    snk[i][i]=0
for i in range(m):
    u,v,a,b=list(map(int, input().strip().split()))
    yen[u-1][v-1]=a
    yen[v-1][u-1]=a
    snk[u-1][v-1]=b
    snk[v-1][u-1]=b
yen_cost=djcstra(s-1,yen)
snk_cost=djcstra(t-1,snk)
sumyensnk=[i+j for i,j in zip(yen_cost,snk_cost)]
for i in range(n):
    print(10**15-min(sumyensnk[i:]))

Submission status: Wrong Answer

Solution code:
from __future__ import print_function
import sys,numpy
from scipy.sparse import*
f=lambda*z:map(int,sys.stdin.readline().split())
v,e,s,t=f();a,b,c,d=zip(*map(f,[0]*e))
x=[0]*(v+1)
y=x
r=[0]*(v+1)
for i in xrange(v-1,-1,-1):r[i]=max(r[i+1],10**15-int(x[i+1]+y[i+1]))
r.pop()
print(*r,sep='\n')

Submission status: Wrong Answer

Solution code:
from __future__ import print_function
import sys,numpy
from scipy.sparse import*
f=lambda*z:map(int,sys.stdin.readline().split())
v,e,s,t=f();a,b,c,d=zip(*map(f,[0]*e))
x=csgraph.dijkstra(csr_matrix((c,(a,b)),[v+1]*2),0,s)
y=x
r=[0]*(v+1)
for i in xrange(v-1,-1,-1):r[i]=max(r[i+1],10**15-int(x[i+1]+y[i+1]))
r.pop()
print(*r,sep='\n')

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from heapq import heapify, heappop, heappush
INF = 10**15


def idreplace(pq, item):
    target_val, target_id = item
    for j, (v, i) in enumerate(pq):
        if i == target_id:
            pq.remove((v, i))
            heappush(pq, (target_val, target_id))
            break


def dijkstra(graph, start=0, inf=INF):

    num = len(graph)
    dists = [inf if node != start else 0 for node in range(num)]
    priority_queue = [(dist, node) for node, dist in zip(range(num), dists)]
    heapify(priority_queue)

    while priority_queue:
        min_dist, min_node = heappop(priority_queue)

        target_edges = graph[min_node]
        for node, dist in enumerate(target_edges):
            if dist != 0:
                dist_from_edge = dists[min_node] + dist
                if dists[node] > dist_from_edge:
                    dists[node] = dist_from_edge
                    idreplace(priority_queue, (dist_from_edge, node))

    return dists


# def dijkstra(graph, start=0, inf=INF):
#     num = len(graph)
#     dists = [inf if node != start else 0 for node in range(num)]
#     remains = dists[:]

#     for _ in range(num):
#         min_index = remains.index(min(remains))
#         remains[min_index] = inf

#         target_edges = graph[min_index]
#         for index, dist in enumerate(target_edges):
#             if dist != 0:
#                 dist_from_edge = dists[min_index] + dist
#                 if dists[index] > dist_from_edge:
#                     dists[index] = dist_from_edge
#                     remains[index] = dist_from_edge

#     return dists

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

yen_graph = [[0] * n for _ in range(n)]
snuke_graph = [[0] * n for _ in range(n)]
for i, j, yen, snuke in trains:
    yen_graph[i - 1][j - 1] = yen
    yen_graph[j - 1][i - 1] = yen
    snuke_graph[i - 1][j - 1] = snuke
    snuke_graph[j - 1][i - 1] = snuke

yen_cost = dijkstra(yen_graph, start=s - 1)
snuke_cost = dijkstra(snuke_graph, start=t - 1)
costs = [yen + snuke for yen, snuke in zip(yen_cost, snuke_cost)]

for i in range(n):
    asset = 10**15
    asset -= min(costs[i:])
    print(asset)

Submission status: Wrong Answer

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)
kae = shortest_path(su,n,t-1)
for i in range(n):
  ans.appendleft(kae[i]+tori[i])
moti = 10**15
for i in range(n):
  c = min(ans)
  print(moti-c)
  ans.popleft()

Submission status: Wrong Answer

Solution code:
import heapq
initial_cost = 10 ** 9
initial = 10 ** 15

def di(link_costs, s):
    costs = [initial] * n
    costs[s] = 0
    q = []
    heapq.heappush(q, (0, s))
    
    while(len(q) != 0):
        index_cost, index = heapq.heappop(q)
        if costs[index] < index_cost:
            continue

        for j in link_costs[index]:
            newcost = costs[index] + link_costs[index][j]
            if newcost < costs[j]:
                costs[j] = newcost
                heapq.heappush(q, (newcost, j))
    return costs
    
n, m, s, t  = list(map(int, input().split()))
s -= 1
t -= 1
links_cost_en = [{} for _ in range(n)]
links_cost_sn = [{} for _ in range(n)]

for _ in range(m):
    u, v, a, b  = list(map(int, input().split()))
    u -= 1
    v -= 1
    links_cost_en[u][v] = a
    links_cost_en[v][u] = a
    links_cost_sn[u][v] = b
    links_cost_sn[v][u] = b

cost_en_from_s = di(links_cost_en, s)
cost_sn_to_t = di(links_cost_sn, t)
cost_list = [cost_en_from_s[i] + cost_sn_to_t[i] for i in range(n)]

print(cost_en_from_s)
print(cost_sn_to_t)
print(cost_list)

ans = [initial] * n
ans[-1] = cost_list[-1]
for i in list(range(n - 1))[::-1]:
    ans[i] = min(ans[i + 1], cost_list[i])
for i in range(n):
    print(initial - ans[i])

Submission status: Wrong Answer

Solution code:
import heapq
initial_cost = 10 ** 9
initial = 10 ** 15

def di(link_costs, s):
    costs = [initial_cost] * n
    costs[s] = 0
    q = []
    heapq.heappush(q, (0, s))
    
    while(len(q) != 0):
        index_cost, index = heapq.heappop(q)
        if costs[index] < index_cost:
            continue

        for j in link_costs[index]:
            newcost = costs[index] + link_costs[index][j]
            if newcost < costs[j]:
                costs[j] = newcost
                heapq.heappush(q, (newcost, j))
    return costs
    
n, m, s, t  = list(map(int, input().split()))
s -= 1
t -= 1
links_cost_en = [{} for _ in range(n)]
links_cost_sn = [{} for _ in range(n)]

for _ in range(m):
    u, v, a, b  = list(map(int, input().split()))
    u -= 1
    v -= 1
    links_cost_en[u][v] = a
    links_cost_en[v][u] = a
    links_cost_sn[u][v] = b
    links_cost_sn[v][u] = b

cost_en_from_s = di(links_cost_en, s)
cost_sn_to_t = di(links_cost_sn, t)
cost_list = [cost_en_from_s[i] + cost_sn_to_t[i] for i in range(n)]
ans = [initial] * n
ans[-1] = cost_list[-1]
for i in list(range(n - 1))[::-1]:
    ans[i] = min(ans[i + 1], cost_list[i])
for i in range(n):
    print(initial - ans[i])

Submission status: Wrong Answer

Solution code:
import heapq
initial_cost = 10 ** 9
initial = 10 ** 15

def di(link_costs, s):
    costs = [initial_cost for _ in range(n)]
    costs[s] = 0
    q = []
    heapq.heappush(q, (0, s))
    
    while(len(q) != 0):
        index_cost, index = heapq.heappop(q)
        if costs[index] < index_cost:
            continue

        for j in link_costs[index]:
            newcost = costs[index] + link_costs[index][j]
            if newcost < costs[j]:
                costs[j] = newcost
                heapq.heappush(q, (newcost, j))
    return costs
    
n, m, s, t  = list(map(int, input().split()))
s -= 1
t -= 1
links_cost_en = [{} for _ in range(n)]
links_cost_sn = [{} for _ in range(n)]

for _ in range(m):
    u, v, a, b  = list(map(int, input().split()))
    u -= 1
    v -= 1
    links_cost_en[u][v] = a
    links_cost_en[v][u] = a
    links_cost_sn[u][v] = b
    links_cost_sn[v][u] = b

cost_en_from_s = di(links_cost_en, s)
cost_sn_to_t = di(links_cost_sn, t)

trans = n - 1
costs = [initial for _ in range(n)]
for i in range(n - 1, -1, -1):
    newcost = cost_en_from_s[i] + cost_sn_to_t[i]
    if i != n - 1:
        costs[i] = min(newcost, costs[i + 1])
    else:
        costs[i] = newcost 

for i in range(n):
    print(initial - costs[i])

Submission status: Wrong Answer

Solution code:
import heapq
dif = 10 ** 6
initial_cost = 10 ** 9
initial = 10 ** 15

def di(link_costs, s):
    costs = [initial_cost for _ in range(n)]
    costs[s] = 0
    node_list = []
    serched_node = set()
    heapq.heappush(node_list, (0, s))
    
    while(len(node_list) != 0):
        index_cost, index = heapq.heappop(node_list)
        if index in serched_node:
            continue
        serched_node.add(index)
        for j in link_costs[index]:
            if j in serched_node:
                continue
        
            newcost = costs[index] + link_costs[index][j]
            if newcost < costs[j]:
                costs[j] = newcost
                heapq.heappush(node_list, (newcost, j))
    return costs
    
n, m, s, t  = list(map(int, input().split()))
s -= 1
t -= 1
links_cost_en = [{} for _ in range(n)]
links_cost_sn = [{} for _ in range(n)]

for _ in range(m):
    u, v, a, b  = list(map(int, input().split()))
    links_cost_en[u - 1][v - 1] = a
    links_cost_en[v - 1][u - 1] = a
    links_cost_sn[u - 1][v - 1] = b
    links_cost_sn[v - 1][u - 1] = b

cost_en_from_s = di(links_cost_en, s)
cost_sn_to_t = di(links_cost_sn, t)

trans = n - 1
costs = [initial for _ in range(n)]
for i in range(n - 1, -1, -1):
    newcost = cost_en_from_s[i] + cost_sn_to_t[i]
    if newcost < costs[trans]:
        trans = i
        costs[i] = newcost
        continue
    
    costs[i] = costs[trans]
    
for cost in costs:
    print(int(initial - cost))

Submission status: Wrong Answer

Solution code:
import heapq
dif = 10 ** 6
initial_cost = 10 ** 9
initial = 10 ** 15

def di(link_costs, s):
    costs = [initial_cost for _ in range(n)]
    costs[s] = 0
    node_list = []
    serched_node = set()
    heapq.heappush(node_list, (0, s))
    
    while(len(node_list) != 0 and len(serched_node) != n):
        index_cost, index = heapq.heappop(node_list)
        if index in serched_node:
            continue
        serched_node.add(index)
        for j in link_costs[index]:
            if j in serched_node:
                continue
        
            newcost = costs[index] + link_costs[index][j]
            if newcost < costs[j]:
                costs[j] = newcost
                heapq.heappush(node_list, (newcost, j))
    return costs
    
n, m, s, t  = list(map(int, input().split()))
s -= 1
t -= 1
links = [set() for _ in range(n)]
links_cost_en = [{} for _ in range(n)]
links_cost_sn = [{} for _ in range(n)]

for _ in range(m):
    u, v, a, b  = list(map(int, input().split()))
    links_cost_en[u - 1][v - 1] = a
    links_cost_en[v - 1][u - 1] = a
    links_cost_sn[u - 1][v - 1] = b
    links_cost_sn[v - 1][u - 1] = b

cost_en_from_s = di(links_cost_en, s)
cost_sn_to_t = di(links_cost_sn, t)

trans = n - 1
costs = [initial_cost for _ in range(n)]
for i in range(n - 1, -1, -1):
    newcost = cost_en_from_s[i] + cost_sn_to_t[i]
    if newcost < costs[trans]:
        trans = i
        costs[i] = newcost
        continue
    
    costs[i] = costs[trans]
    
for cost in costs:
    print(int(initial - cost))

Submission status: Wrong Answer

Solution code:

import heapq
dif = 10 ** 6
initial = 10 ** 15

def di(link_costs, s):
    costs = [initial] * n
    costs[s] = 0
    node_list = []
    serched_node = set()
    heapq.heappush(node_list, s)
    while(len(node_list) != 0 and len(serched_node) != n):
        index = heapq.heappop(node_list) % dif
        if index in serched_node:
            continue
        serched_node.add(index)
        link = links[index]
        for j in link:
            if j in serched_node:
                continue
        
            cost = link_costs[index][j]
            newcost =  costs[index] + cost
            if newcost < costs[j]:
                costs[j] = newcost
                heapq.heappush(node_list, newcost * dif + j)
    return costs
    
n, m, s, t  = list(map(int, input().split()))
s -= 1
t -= 1
links = [set() for _ in range(n)]
links_cost_en = [[-1 for j in range(n)] for i in range(n)]
links_cost_sn = [[-1 for j in range(n)] for i in range(n)]

for _ in range(m):
    u, v, a, b  = list(map(int, input().split()))
    links[u-1].add(v-1)
    links[v-1].add(u-1)
    links_cost_en[u - 1][v - 1] = a
    links_cost_en[v - 1][u - 1] = a
    links_cost_sn[v - 1][u - 1] = b
    links_cost_sn[u - 1][v - 1] = b

print(links)
print(links_cost_en)
print(links_cost_sn)
cost_en_from_s = di(links_cost_en, s)
cost_sn_to_t = di(links_cost_sn, t)

trans = n - 1
costs = [initial] * n
for i in range(n - 1, -1, -1):
    newcost = cost_en_from_s[i] + cost_sn_to_t[i]
    if newcost < costs[trans]:
        trans = i
        costs[i] = newcost
        continue
    
    costs[i] = costs[trans]
    
for cost in costs:
    print(initial - cost)

Submission status: Wrong Answer

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(list)
    for u, v, a, b in UVAB:
        g[u].append((v, (a, b)))
        g[v].append((u, (a, b)))

    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 =[]
        heapq.heappush(q, (dist[s], s))
        while q:
            c, u = heapq.heappop(q)
            if dist[u] > c:
                continue
            for v, cost in g[u]:
                alt = dist[u] + cost[ck]
                if dist[v] > alt:
                    dist[v] = alt
                    heapq.heappush(q, (alt, v))
        return dist

    dist0 = d(s, 0)
    dist1 = d(t, 1)


        

    ans = [sys.maxsize] * (n+1)
    
    for i in range(n-1, -1, -1):
        # print(i)
        ans[i] = min(ans[i], dist1[i+1] + dist0[i+1])
    c = 10**15
    return '\n'.join(map(lambda x: str(c-x), ans[:-1]))


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: Wrong Answer

Solution code:
from collections import defaultdict 
import sys
import heapq

sys.setrecursionlimit(10**8)

#N:頂点数   M:辺数
N,M,s,t = map(int,input().split())


#root[n] -> nからいけるlist
roots = defaultdict(set)

#weight[a] = start -> a のコスト 未探索->-1
weight_yen = [-1 for i in range(N+1)]
weight_snu = [-1 for i in range(N+1)]
weight_yen[s] = 0
weight_snu[t] = 0


for i in range(M):
	u,v,a,b = list(map(int,input().split())) #

	roots[u].add((v,a,b))
	roots[v].add((u,a,b))
		
	
def search_yen (n,w_0): #nから更新 w_0:確定コスト
	global weight_yen
		
	for root in list(roots[n]):
		i = root[0]
		w = w_0 + root[1]
		if weight_yen[i] == -1 or weight_yen[i] > w: #未探索orより小さい
			heapq.heappush(q, [w,i])
			weight_yen[i] = w
			
def search_snu (n,w_0): #nから更新 w_0:確定コスト
	global weight_snu
		
	for root in list(roots[n]):
		i = root[0]
		w = w_0 + root[1]
		if weight_snu[i] == -1 or weight_snu[i] > w: #未探索orより小さい
			heapq.heappush(q, [w,i])
			weight_snu[i] = w

#q = 次に探索する(確定する)もの q[0]=[w,n]
q = [[0,s]]
heapq.heapify(q)
			
while q:
	w,n = heapq.heappop(q)
	search_yen(n,w)
	
q = [[0,t]]
	
while q:
	w,n = heapq.heappop(q)
	search_snu(n,w)
	

finalans = float('inf')
ans_li = []

for i in range(0,N):
	ans = weight_yen[N-i] + weight_snu[N-i]
	finalans = min(finalans, ans)
	ans_li.append(finalans)
	
for i in range(N):
	print(10**15 - ans_li[N-i-1])

Submission status: Wrong Answer

Solution code:
import sys

n, m, s, t = map(int, next(sys.stdin).split(" "))

u = [0 for _ in range(m+1)]
v = [0 for _ in range(m+1)]
a = [0 for _ in range(m+1)]
b = [0 for _ in range(m+1)]
matrix = [[None for _ in range(n+1)] for _ in range(n+1)]

for i in range(1, m+1):
    u[i], v[i], a[i], b[i] = map(int, next(sys.stdin).split(" "))
    matrix[u[i]][v[i]] = matrix[v[i]][u[i]] = i

def dijkstra(start, goal, costs):
    def adjacent_cities(reached_cities):
        cities = set()
        for city in reached_cities:
            cities |= set(filter(lambda i: matrix[city][i] is not None, range(1, n+1)))
            cities -= reached_cities
        return cities

    def nearest_adjacent(reached_cities):
        nearest_adj = None
        nearest_adj_cost = 10**9
        nearest_adj_border = None
        for adj in adjacent_cities(reached_cities):
            borders = set(filter(lambda i: matrix[adj][i] is not None, range(1, n+1))) \
                      & reached_cities
            border = min(borders, key=lambda b: costs[matrix[b][adj]])
            if costs[matrix[border][adj]] <= nearest_adj_cost:
                nearest_adj = adj
                nearest_adj_cost = costs[matrix[border][adj]]
                nearest_adj_border = border
        return nearest_adj, nearest_adj_border, nearest_adj_cost

    neccesary_costs = [None for _ in range(n+1)]
    reached_cities = { start }
    unreached_cities = set(range(1,n+1)) - reached_cities
    neccesary_costs[start] = 0

    while unreached_cities != set():
        city, border, cost = nearest_adjacent(reached_cities)
        reached_cities.add(city)
        neccesary_costs[city] = neccesary_costs[border] + cost
        unreached_cities.remove(city)

    return neccesary_costs

yen_costs = dijkstra(s, t, a)
snuke_costs = dijkstra(t, s, b)

for i in range(n):
    min_cost = 10**15
    for j in range(i+1, n+1):
        if yen_costs[j] + snuke_costs[j] < min_cost:
            min_cost = yen_costs[j] + snuke_costs[j]
    print(10**15 - min_cost)

Submission status: Wrong Answer

Solution code:
n, m, s, t = map(int, input().split())
c = 10**15
from collections import defaultdict
from heapq import heappop, heappush
graph = defaultdict(list)
for _ in range(m):
  u, v, a, b = map(int, input().split())
  graph[u].append((v, a, b))
  graph[v].append((u, a, b))

def dijkstra(s, year, t):
  d = defaultdict(lambda:float("INF"))
  d[(s, 0)] = 0
  q = []
  heappush(q, (0, (s, 0)))

  while len(q):
    #print(q)
    cost, v = heappop(q)
    cur, m = v[0], v[1]

    for to, a, b in graph[cur]:
      if cur>year:
        if m==1 and d[(cur, 0)]>cost:
          d[(cur, 0)]=cost
          heappush(q, (cost, (cur, 1)))
          heappush(q, (cost, (cur, 0)))
        if m==0 and d[(cur, 1)]>cost:
          d[(cur, 1)]=cost
          heappush(q, (cost, (cur, 0)))
          heappush(q, (cost, (cur, 1)))
        if d[(to, 0)]>cost+a:
          d[(to, 0)]=cost+a
          heappush(q, (cost+a, (to, 0)))
        if d[(to, 1)]>cost+b:
          d[(to, 1)]=cost+b
          heappush(q, (cost+b, (to, 1)))
      else:
        if m == 0:
          if d[(to, 0)]>cost+a:
            d[(to, 0)]=cost+a
            heappush(q, (cost+a, (to, 0)))
        else:
          if d[(to, 1)]>cost+b:
            d[(to, 1)]=cost+b
            heappush(q, (cost+b, (to, 1)))
  
  #print(d)
  return d[(t, 1)]

for i in range(n):
  tt = dijkstra(s, i, t)
  print(c-tt)

Submission status: Wrong Answer

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
ans[-1] = d0[t]
for i in xrange(n - 2, -1, -1):
    ans[i] = min(ans[i + 1], d0[i] + d1[i])

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

Submission status: Wrong Answer

Solution code:
n,m,s,t=map(int,input().split())
TRAIN=[None]*m

for i in range(m):
    TRAIN[i]=list(map(int,input().split()))


YEN=[10**16]*(n+1)#sから国iまで行くときの最小円
SNOOK=[10**16]*(n+1)#国iからtまで行くときの最小スヌーク
YEN[s]=0
SNOOK[t]=0


YENTRAIN=sorted(TRAIN,key=lambda x:x[2])
SNOOKTRAIN=sorted(TRAIN,key=lambda x:x[3])

YENTOWN={s}


i=1
while i!=n:
    for j in YENTRAIN:

        if len({j[0],j[1]} & YENTOWN)==1:
            if j[0] in YENTOWN and YEN[j[1]]>YEN[j[0]]+j[2]:
                YEN[j[1]]=YEN[j[0]]+j[2]
                YENTOWN=YENTOWN|{j[1]}

            elif j[1] in YENTOWN and YEN[j[0]]>YEN[j[1]]+j[2]:
                YEN[j[0]]=YEN[j[1]]+j[2]
                YENTOWN=YENTOWN|{j[0]}

            i+=1

            break
    #print(YEN,YENTOWN)
    

SNOOKTOWN={t}

i=1
while i!=n:
    for j in SNOOKTRAIN:
        if len({j[0],j[1]} & SNOOKTOWN)==1:
            if j[0] in SNOOKTOWN and SNOOK[j[1]]>SNOOK[j[0]]+j[3]:
                SNOOK[j[1]]=SNOOK[j[0]]+j[3]
                SNOOKTOWN=SNOOKTOWN|{j[1]}

            elif j[1] in SNOOKTOWN and SNOOK[j[0]]>SNOOK[j[1]]+j[3]:
                SNOOK[j[0]]=SNOOK[j[1]]+j[3]
                SNOOKTOWN=SNOOKTOWN|{j[0]}

            i+=1

            break




MONEY=[None]*(n+1)

for i in range(1,n+1):
    MONEY[i]=YEN[i]+SNOOK[i]


for i in range(1,n+1):
    print(10**15-min(MONEY[i:]))

Submission status: Wrong Answer

Solution code:
import bisect
import heapq

n,m,s,t=[int(x) for x in raw_input().split()]
A=[[] for i in range(n+1)]
B=[[] for i in range(n+1)]
for k in range(m):
    u,v,a,b=[int(x) for x in raw_input().split()]
    A[u].append([v,a])
    A[v].append([u,a])
    B[u].append([v,b])
    B[v].append([u,b])
bignum=1e15
Da=[bignum for x in range(n+1)]
Db=[bignum for x in range(n+1)]
Ca=[0 for i in range(n+1)]
Cb=[0 for i in range(n+1)]

Da[s]=0
Ca[s]=1
tmpset=[(bignum,0)]
tmpp=s
for i in range(n):
    for p in A[tmpp]:
        rfrs=Da[tmpp]+p[1]
        if Da[p[0]] >rfrs:
            Da[p[0]]= rfrs
            bisect.insort(tmpset, (rfrs, p[0]) )
    while(1):
        p=heapq.heappop(tmpset)
        if Ca[p[1]]==0:
            tmpp=p[1]
            break
    Ca[tmpp]=1


Db[t]=0
Cb[t]=1
tmpset=[(bignum,0)]
tmpp=t
for i in range(n):
    for p in B[tmpp]:
        rfrs=Db[tmpp]+p[1]
        if Db[p[0]] >rfrs:
            Db[p[0]]= rfrs
            bisect.insort(tmpset, (rfrs, p[0]) )
    while(1):
        p=heapq.heappop(tmpset)
        if Cb[p[1]]==0:
            tmpp=p[1]
            break
    Ca[tmpp]=1

D = sorted ( [ (Da[i]+Db[i],i) for i in range(n+1)], key=lambda x:x[0] )
k=0
for i in range(n):
    while D[k][1]<=i:
        k+=1
    print 1000000000000000 - D[k][0]

Submission status: Wrong Answer

Solution code:
n,m,s,t=map(int,input().split())
TRAIN=[None]*m

for i in range(m):
    TRAIN[i]=list(map(int,input().split()))


YEN=[None]*(n+1)#sから国iまで行くときの最小円
SNOOK=[None]*(n+1)#国iからtまで行くときの最小スヌーク
YEN[s]=0
SNOOK[t]=0


YENTRAIN=sorted(TRAIN,key=lambda x:x[2])
SNOOKTRAIN=sorted(TRAIN,key=lambda x:x[3])

YENTOWN={s}


i=1
while i!=n:
    for j in YENTRAIN:

        if len({j[0],j[1]} & YENTOWN)==1:
            if j[0] in YENTOWN:
                YEN[j[1]]=YEN[j[0]]+j[2]
                YENTOWN=YENTOWN|{j[1]}

            elif j[1] in YENTOWN:
                YEN[j[0]]=YEN[j[1]]+j[2]
                YENTOWN=YENTOWN|{j[0]}

            i+=1

            break
    #print(YEN,YENTOWN)
    

SNOOKTOWN={t}

i=1
while i!=n:
    for j in SNOOKTRAIN:
        if len({j[0],j[1]} & SNOOKTOWN)==1:
            if j[0] in SNOOKTOWN:
                SNOOK[j[1]]=SNOOK[j[0]]+j[3]
                SNOOKTOWN=SNOOKTOWN|{j[1]}

            elif j[1] in SNOOKTOWN:
                SNOOK[j[0]]=SNOOK[j[1]]+j[3]
                SNOOKTOWN=SNOOKTOWN|{j[0]}

            i+=1

            break




MONEY=[None]*(n+1)

for i in range(1,n+1):
    MONEY[i]=YEN[i]+SNOOK[i]


for i in range(1,n+1):
    print(10**15-min(MONEY[i:]))

Submission status: Wrong Answer

Solution code:
import bisect
import heapq

n,m,s,t=[int(x) for x in raw_input().split()]
A=[[] for i in range(n+1)]
B=[[] for i in range(n+1)]
for k in range(m):
    u,v,a,b=[int(x) for x in raw_input().split()]
    A[u].append([v,a])
    A[v].append([u,a])
    B[u].append([v,b])
    B[v].append([u,b])
bignum=1e15
Da=[bignum for x in range(n+1)]
Db=[bignum for x in range(n+1)]
Ca=[0 for i in range(n+1)]
Cb=[0 for i in range(n+1)]

Da[s]=0
Ca[s]=1
tmpset=[(bignum,0)]
tmpp=s
for i in range(n):
    for p in A[tmpp]:
        rfrs=Da[tmpp]+p[1]
        if Da[p[0]] >rfrs:
            Da[p[0]]= rfrs
            heapq.heappush(tmpset, (rfrs, p[0]) )
    while(1):
        p=heapq.heappop(tmpset)
        if Ca[p[1]]==0:
            tmpp=p[1]
            break
    Ca[tmpp]=1


Db[t]=0
Cb[t]=1
tmpset=[(bignum,0)]
tmpp=t
for i in range(n):
    for p in B[tmpp]:
        rfrs=Db[tmpp]+p[1]
        if Db[p[0]] >rfrs:
            Db[p[0]]= rfrs
            heapq.heappush(tmpset, (rfrs, p[0]) )
    while(1):
        p=heapq.heappop(tmpset)
        if Cb[p[1]]==0:
            tmpp=p[1]
            break
    Ca[tmpp]=1

D = sorted ( [ (Da[i]+Db[i],i) for i in range(n+1)], key=lambda x:x[0] )
k=0
for i in range(n):
    while D[k][1]<=i:
        k+=1
    print 10000000000000000 - D[k][0]