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: Runtime Error

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


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


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

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

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

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


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


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


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

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

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

Submission status: Runtime Error

Solution code:
import heapq
from itertools import accumulate

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

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

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

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

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

Submission status: Runtime Error

Solution code:
from numba import jit
import queue
n,m ,start ,goal = map(int,input().split())

@jit
def dijkstra(start, num_of_node, adjacent_list):
	#initialize
	dist = [float("inf") for i in range(num_of_node)]
	dist[start] = 0
	q = queue.PriorityQueue()
	q.put([dist[start], start])
 
	while not q.empty():
		dist_u, u = q.get()
 
		if dist[u] < dist_u :
			continue
 
		for weight,v in adjacent_list[u]:
			alt = dist_u + weight
			if dist[v] > alt:
				dist[v] = alt
				q.put([alt,v])
 
	return dist
 
yen_al = [[]for i in range(n)]
snuuk_al = [[] for i in range(n)]
 
for _ in range(m):
	f, t, y, s = map(int,input().split())
	f -= 1; t -= 1
	yen_al[f].append((y,t)); yen_al[t].append((y,f))
	snuuk_al[f].append((s,t)); snuuk_al[t].append((s,f))
 
yen = dijkstra(start-1,n,yen_al)
snuuk = dijkstra(goal-1,n,snuuk_al)
 
snuuk_sum = [yen[i] + snuuk[i] for i in range(n)]
 
m = float("inf")
ans = [0 for i in range(n)]
for i in range(n-1,-1,-1):
	ans[i] = min(snuuk_sum[i],m)
	m = ans[i]
 
for i in range(n):
	print(10**15 - ans[i])

Submission status: Runtime Error

Solution code:
import heapq
import sys
from itertools import accumulate
import operator as op

n,m,s,t = map(int,next(sys.stdin).split(" "))
inf = 1000000000000000
gyen = [dict() for _ in range(n)]
gsnuk = [dict() for _ in range(n)]

for line in sys.stdin.readlines():
        u,v,a,b = map(int,line.strip().split(" "))
        gyen[u-1][v-1] = gyen[v-1][u-1] = a
        gsnuk[u-1][v-1] = gsnuk[v-1][u-1] = b

def dijkstra(graph, start):
        dist = [inf for _ in range(n)]
        dist[start] = 0
        q = [(0,start)]
        while q and rem>0:
                du, u = heapq.heappop(q)
                if dist[u] < du:
                        continue
                for i in graph[u]:
                        if dist[i[0]] > du+i[1]:
                                dist[i[0]] = du+i[1]
                                heapq.heappush(q, (dist[i[0]], i[0]))
        return dist

yen = dijkstra(gyen,s-1)
snuke = dijkstra(gsnuk,t-1)

ans = list(accumulate([y+s for y,s in zip(yen,snuke)][::-1],min))
[print(inf-ans[i]) for i in range(n-1,-1,-1)]

Submission status: Runtime Error

Solution code:
from heapq import *

INF = 10**15

def djikstra(G,s,d):
    #d = [0]*V
    que = []
    d[s] = 0
    visited = [False] * V
    heappush(que,(0,s))
    while(len(que)!=0):
        c,v = heappop(que)
        if visited[v]:
            continue
        visited[v] = True
        for i in range(len(G[v])):
            e = G[v][i]
            if visited[e[0]]:
                continue
            if d[e[0]] > d[v] + e[1]:
                d[e[0]] = d[v] + e[1]
                heappush(que,(d[e[0]],e[0]))


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

S = [INF]*V
T = [INF]*V
djikstra(Ga,s-1,S)
djikstra(Gb,t-1,T)
M = [0]*n
for i in range(n):
M[i] = INF-S[i]-T[i]
ans = [0]*n
ans[n-1] = M[n-1]
for i in range(n-2,-1,-1):
    ans[i] = max(ans[i+1],M[i])

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

Submission status: Runtime Error

Solution code:
from heapq import *
from numpy import array,inf


def djikstra(s):
    que = []
    d = [inf]*V
    d[s] = 0
    visited = [False] * n
    heappush(que,(0,s))
    while(len(que)!=0):
        p = heappop(que)
        v = p[1]
        if visited[p[0]]:
            continue
        visited[p[0]] = True
        for i in range(len(G[v])):
            if visited[G[v][i][0]]:
                continue
            e = G[v][i]
            if d[e[0]] > d[v] + e[1]:
                d[e[0]] = d[v] + e[1]
                heappush(que,(d[e[0]],e[0]))
    return d


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

G = Ga
S = djikstra(s-1)
G = Gb
T = djikstra(t-1)

M = 10**15-(array(S)+array(T))
ans = [0]*n
ans[n-1] = M[n-1]
for i in range(n-2,-1,-1):
    ans[i] = max(ans[i+1],M[i])

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

Submission status: Runtime Error

Solution code:
from heapq import *
from numpy import array,inf


def djikstra(s):
    que = []
    d = [inf]*V
    d[s] = 0
    que.push((0,s))
    while(len(que)!=0):
        p = heappop(que)
        v = p[1]
        if d[v] < p[0]:
            continue
        for i in range(len(G[v])):
            e = G[v][i]
            if d[e[0]] > d[v] + e[1]:
                d[e[0]] = d[v] + e[1]
                heappush(que,(d[e[0]],e[0]))
    return d


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

G = Ga
S = djikstra(s-1)
G = Gb
T = djikstra(t-1)

M = 10**15-(array(S)+array(T))
ans = [0]*n
ans[n-1] = M[n-1]
for i in range(n-2,-1,-1):
    ans[i] = max(ans[i+1],M[i])

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

Submission status: Runtime Error

Solution code:
from heapq import *
class PriorityQueue(object):
    def __init__(self):
        self.queue = []
    def push(self, value):
        heappush(self.queue, value)
    def pop(self):
        return heappop(self.queue)
    def empty(self):
        return len(self.queue) == 0
    def size(self):
        return len(self)

from numpy import array,inf


def djikstra(s):
    que = []
    d = [inf]*V
    d[s] = 0
    que.push((0,s))
    while(not que.empty()):
        p = heappop(que)
        v = p[1]
        if d[v] < p[0]:
            continue
        for i in range(len(G[v])):
            e = G[v][i]
            if d[e[0]] > d[v] + e[1]:
                d[e[0]] = d[v] + e[1]
                heappush(que,(d[e[0]],e[0]))
    return d


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

G = Ga
S = djikstra(s-1)
G = Gb
T = djikstra(t-1)

M = 10**15-(array(S)+array(T))
ans = [0]*n
ans[n-1] = M[n-1]
for i in range(n-2,-1,-1):
    ans[i] = max(ans[i+1],M[i])

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

Submission status: Runtime Error

Solution code:
class edge():
    def __init__(self,to,cost):
        self.to = to
        self.cost = cost

from heapq import *
class PriorityQueue(object):
    def __init__(self):
        self.queue = []
    def push(self, value):
        heappush(self.queue, value)
    def pop(self):
        return heappop(self.queue)
    def empty(self):
        return len(self.queue) == 0
    def size(self):
        return len(self)

from math import inf
from numpy import array


def djikstra(s):
    que = PriorityQueue()
    d = [inf]*V
    d[s] = 0
    que.push((0,s))
    while(not que.empty()):
        p = que.pop()
        v = p[1]
        if d[v] < p[0]:
            continue
        for i in range(len(G[v])):
            e = G[v][i]
            if d[e.to] > d[v] + e.cost:
                d[e.to] = d[v] + e.cost
                que.push((d[e.to],e.to))
    return d


n,m,s,t = map(int,input().split())
V = n
Ga = {}
Gb = {}
for i in range(n):
    Ga[i]=[]
    Gb[i]=[]
for i in range(m):
    u,v,a,b = map(int,input().split())
    Ga[u-1].append(edge(v-1,a))
    Ga[v-1].append(edge(u-1,a))
    Gb[u-1].append(edge(v-1,b))
    Gb[v-1].append(edge(u-1,b))

G = Ga
S = djikstra(s-1)
G = Gb
T = djikstra(t-1)

M = array(S)+array(T)

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

Submission status: Runtime Error

Solution code:
inp = list(map(int, input().split()))
n = inp[0] # the num of node
m = inp[1] # the num of edge
s = inp[2] - 1 # start
t = inp[3] - 1 # stop

u = [] # edge (smaller)
v = [] # edge (larger)
a = [] # fare (yen)
b = [] # fare (snuke)
for i in range(m):
    inp = list(map(int, input().split()))
    u.append(inp[0] - 1)
    v.append(inp[1] - 1)
    a.append(inp[2])
    b.append(inp[3])

uu = [[] for i in range(n)]

for i in range(m):
    uu[u[i]].append([v[i], a[i], b[i]])
    uu[v[i]].append([u[i], a[i], b[i]])

# Dijkstra's Algorithm
#   fare: 1 => yen, 2 => snuke
def cheaper(start, stop, fare):

    if (start == stop):
        return 0

    flag = [0 for i in range(n)]
    distance = [-1 for i in range(n)]
    flag[start] = 1
    distance[start] = 0
    base = start
    changeList = set([])

    for i in range(n - 1):
        # update distance
        for j in len(uu[base]):
                befo = distance[uu[base][j][0]]
                afte = distance[base] + uu[base][j][fare]
                if (afte < befo or befo == -1):
                    distance[uu[base][j][0]] = afte
                    changeList.add(uu[base][j][0]])

        # update base
        base = list(changeList)[0]
        for j in changeList:
            if (distance[j] < distance[base]):
                base = j
        changeList.remove(base)

        # update flag (using updated base)
        flag[base] = 1

        # check break
        if (base == stop):
            break

    return distance[base]

totalFare = []
for ex in range(n): # ex: exchange
    totalFare.append(cheaper(s, ex, a) + cheaper(ex, t, b))

for i in range(n):
    money = 10 ** 15
    print(money - min(totalFare))
    del totalFare[0]

Submission status: Runtime Error

Solution code:
import heapq
import numpy as np

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

Yen_cost = np.ones((n, n)) * np.inf
Snuuk_cost = np.ones((n, n)) * np.inf

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


def Digkstra(Cost_list, start):   
    dist = np.ones(n) * np.inf
    dist[start] = 0
    q = []
    heapq.heappush(q, (0, start))

    while len(q) != 0:
        prov_cost, src = heapq.heappop(q)

        if dist[src] < prov_cost:
            continue

        for dest in range(n):
            cost = Cost_list[src, dest]
            if dist[dest] > dist[src] + cost:
                dist[dest] = dist[src] + cost
                heapq.heappush(q, (dist[dest], dest))
    return dist

Yen_dist = Digkstra(Yen_cost, s-1).astype(int)
Snuuk_dist = Digkstra(Snuuk_cost, t-1).astype(int)

First = 10**15
Money = []
Money.append(int(First - Yen_dist[-1] - Snuuk_dist[-1]))
for year in range(n-2, -1, -1):
    temp = First - Yen_dist[year] - Snuuk_dist[year]
    if temp > Money[-1]:
        Money.append(temp)
    else:
        Money.append(Money[-1])

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

Submission status: Runtime Error

Solution code:
import numpy as np
INF = 10**20

n,m,s,t = map(int,input().split())
u = np.zeros(m)
v = np.zeros(m)
a = np.zeros(m)
b = np.zeros(m)

i = 0
while(i < m):
    u[i],v[i],a[i],b[i] = map(int,input().split())
    i += 1

#s to i
dist = np.ones(n)*INF
dist[s-1] = 0
prev = np.ones(n)*(-1)
Q = np.arange(n)

while(np.sum(Q == -1) < n):
    #print("hoge")
    dist_argsorted = np.argsort(dist)
    i = 0
    while(1):
        dijk_u = dist_argsorted[i]
        i += 1
        if(Q[dijk_u] != -1):
            break

    Q[dijk_u] = -1
    queue = list(np.concatenate((u[np.where(v == dijk_u + 1)],v[np.where(u == dijk_u + 1)]),axis=0) -1)
    #print(queue)
    for dijk_v in queue:
        #print(dijk_u, dijk_v)
        small = np.min(np.array([dijk_u, dijk_v]))
        big = np.max(np.array([dijk_u, dijk_v]))
        raw = np.intersect1d(np.where(u == small+1),np.where(v == big+1))[0]
        #print(row)
        dijk_u = int(dijk_u)
        dijk_v = int(dijk_v)
        if (dist[dijk_v] > dist[dijk_u] + a[raw]):
            dist[dijk_v] = dist[dijk_u] + a[raw]
            prev[dijk_v] = dijk_u


yens = dist.copy()

#t to i
dist = np.ones(n)*INF
dist[t-1] = 0
prev = np.ones(n)*(-1)
Q = np.arange(n)

while(np.sum(Q == -1) < n):
    #print("hoge")
    dist_argsorted = np.argsort(dist)
    i = 0
    while (1):
        dijk_u = dist_argsorted[i]
        i += 1
        if (Q[dijk_u] != -1):
            break
    Q[dijk_u] = -1
    queue = list(np.concatenate((u[np.where(v == dijk_u + 1)], v[np.where(u == dijk_u + 1)]), axis=0) - 1)
    for dijk_v in queue:
        #print(dijk_u, dijk_v)
        small = np.min(np.array([dijk_u, dijk_v]))
        big = np.max(np.array([dijk_u, dijk_v]))
        raw = np.intersect1d(np.where(u == small+1),np.where(v == big+1))[0]
        dijk_u = int(dijk_u)
        dijk_v = int(dijk_v)
        if (dist[dijk_v] > dist[dijk_u] + b[raw]):
            dist[dijk_v] = dist[dijk_u] + b[raw]
            prev[dijk_v] = dijk_u

snuuks = dist.copy()

total_costs = yens + snuuks
#print(yens)

for i in range(n):
    print(int(10**15 - np.min(total_costs[i::])))

Submission status: Runtime Error

Solution code:
import numpy as np
INF = 10**20

n,m,s,t = map(int,input().split())
u = np.zeros(m)
v = np.zeros(m)
a = np.zeros(m)
b = np.zeros(m)

i = 0
while(i < m):
    u[i],v[i],a[i],b[i] = map(int,input().split())
    i += 1

#s to i
dist = np.ones(n)*INF
dist[s-1] = 0
prev = np.ones(n)*(-1)
Q = np.arange(n)

while(np.sum(Q == -1) < n):
    #print("hoge")
    dist_argsorted = np.argsort(dist)
    i = 0
    while(1):
        dijk_u = dist_argsorted[i]
        i += 1
        if(Q[dijk_u] != -1):
            break

    Q[dijk_u] = -1
    queue = list(np.concatenate((u[np.where(v == dijk_u + 1)],v[np.where(u == dijk_u + 1)]),axis=0) -1)
    #print(queue)
    for dijk_v in queue:
        #print(dijk_u, dijk_v)
        small = np.min(np.array([dijk_u, dijk_v]))
        big = np.max(np.array([dijk_u, dijk_v]))
        row = np.intersect1d(np.where(u == small+1),np.where(v == big+1))[0]
        #print(row)
        dijk_u = int(dijk_u)
        dijk_v = int(dijk_v)
        if (dist[dijk_v] > dist[dijk_u] + a[row]):
            dist[dijk_v] = dist[dijk_u] + a[row]
            prev[dijk_v] = dijk_u


yens = dist.copy()

#t to i
dist = np.ones(n)*INF
dist[t-1] = 0
prev = np.ones(n)*(-1)
Q = np.arange(n)

while(np.sum(Q == -1) < n):
    #print("hoge")
    dist_argsorted = np.argsort(dist)
    i = 0
    while (1):
        dijk_u = dist_argsorted[i]
        i += 1
        if (Q[dijk_u] != -1):
            break
    Q[dijk_u] = -1
    queue = list(np.concatenate((u[np.where(v == dijk_u + 1)], v[np.where(u == dijk_u + 1)]), axis=0) - 1)
    for dijk_v in queue:
        #print(dijk_u, dijk_v)
        small = np.min(np.array([dijk_u, dijk_v]))
        big = np.max(np.array([dijk_u, dijk_v]))
        row = np.intersect1d(np.where(u == small+1),np.where(v == big+1))[0]
        dijk_u = int(dijk_u)
        dijk_v = int(dijk_v)
        if (dist[dijk_v] > dist[dijk_u] + b[row]):
            dist[dijk_v] = dist[dijk_u] + b[row]
            prev[dijk_v] = dijk_u

snuuks = dist.copy()

total_costs = yens + snuuks
#print(yens)

for i in range(n):
    print(int(10**15 - np.min(total_costs[i::])))

Submission status: Runtime Error

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,y=[csgraph.dijkstra(csr_matrix((c,(a,b)),[v+1]*2),0,s,limit=1e9)for(c,s)in[(c,s),(d,t)]]
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: Runtime Error

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


def dijkstra(graph, start=0):

    num = len(graph)
    remains = [node for node in range(num)]
    dists = [math.inf if node != start else 0 for node in range(num)]

    while remains:
        min_index = min(remains, key=lambda x: dists[x])
        remains.remove(min_index)

        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

    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: Runtime Error

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


def dijkstra(graph, start=0, goal=None, verbose=0):
    '''
    sample input:
    graph = [[0, 2, 5, 4, 0, 0], # node 0
             [2, 0, 0, 3, 6, 0], # node 1
             [5, 0, 0, 2, 0, 6], # node 2
             [4, 3, 2, 0, 2, 0], # node 3
             [0, 6, 0, 2, 0, 4], # node 4
             [0, 0, 6, 0, 4, 0]  # node 5
    ]
    (
    1. distance from a node itself should be 0,
    2. if there is no edge between nodes, the distance between them should be 0
    3. weights can be negative
    )
    '''

    num = len(graph)
    remains = [node for node in range(num)]
    dists = [math.inf if node != start else 0 for node in range(num)]
    prevs = [-1 for node in range(num)]
    if goal is None:
        goal = num - 1

    while remains:
        min_index = min(remains, key=lambda x: dists[x])
        remains.remove(min_index)

        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
                    prevs[index] = min_index

    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: Runtime Error

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


def dijkstra(graph, start=0, goal=None, verbose=0):
    '''
    sample input:
    graph = [[0, 2, 5, 4, 0, 0], # node 0
             [2, 0, 0, 3, 6, 0], # node 1
             [5, 0, 0, 2, 0, 6], # node 2
             [4, 3, 2, 0, 2, 0], # node 3
             [0, 6, 0, 2, 0, 4], # node 4
             [0, 0, 6, 0, 4, 0]  # node 5
    ]
    (
    1. distance from a node itself should be 0,
    2. if there is no edge between nodes, the distance between them should be 0
    3. weights can be negative
    )
    '''

    num = len(graph)
    remains = [node for node in range(num)]
    dists = [math.inf if node != start else 0 for node in range(num)]
    prevs = [-1 for node in range(num)]
    if goal is None:
        goal = num - 1

    while remains:
        min_index = min(remains, key=lambda x: dists[x])
        remains.remove(min_index)

        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
                    prevs[index] = min_index

    min_route = []
    prev = goal
    cnt = 0
    while prev != start:
        min_route.append(prev)
        prev = prevs[prev]

        cnt += 1
        if prev == -1 or cnt > num:
            raise NoRouteError(
                'There is no possible route in this graph \ngraph: {} \nstart: {} \ngoal: {}'.
                format(graph, start, goal))

    else:
        min_route.append(prev)
    min_route = min_route[::-1]
    min_dist = dists[goal]

    if verbose:
        print('---route---')
        for node in min_route[:-1]:
            print('{} -> '.format(node), end='')
        else:
            print(min_route[-1])

        print('---distance---')
        print(min_dist)

    return dists, min_route


class NoRouteError(Exception):
    pass


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_dist, min_route = dijkstra(yen_graph, start=s - 1)
snuke_dist, min_route = dijkstra(snuke_graph, start=t - 1)

for i in range(n):
    asset = 10**15
    asset -= min(
        [yen + snuke for yen, snuke in zip(yen_dist[i:], snuke_dist[i:])])
    print(asset)

Submission status: Runtime Error

Solution code:
import heapq
# dijkstra
# edges = |V|のリスト
# 頂点iから頂点jにコストwで移動可能な場合：edges[i] = [(j, w)]

def dijkstra(n, edges, start):
    INF = float('inf')
    vertices = [INF] * n # 初期化
    vertices[start] = 0 # スタートの距離はゼロ
    hq = [(0, start)]
    heapq.heapify(hq)

    while q:
        cost, v = heapq.heappop(hq)
        
        for to, w in edges[v]:
            if cost + w >= vertices[to]:
                continue
            vertices[to] = cost + w
            heapq.heappush(hq, (vertices[to], to))
    
    return vertices

# input
n, m, s, t = map(int, input().split())
G = [list(map(int, input().split())) for _ in range(m)]

G_yen = [[] for _ in range(n)]
G_snu = [[] for _ in range(n)]

s, t = s - 1, t - 1

for u, v, a, b in G:
    G_yen[u - 1].append((v - 1, a))
    G_yen[v - 1].append((u - 1, a))
    G_snu[u - 1].append((v - 1, b))
    G_snu[v - 1].append((u - 1, b))

yen = dijkstra(n, G_yen, s)
snu = dijkstra(n, G_snu, t)

ans = [INF]

for i in reversed(range(n)):
    tmp = snu[i] + yen[i]
    ans.append(min(ans[-1], tmp))

for i in reversed(ans[1:]):
    print(10 ** 15 - a)

Submission status: Runtime Error

Solution code:
import networkx as nx
import math

nmst = [int(i) for i in input().split()]
n, m, s, t = nmst[0], nmst[1], nmst[2], nmst[3]

#trainの無向グラフ作成(yen, snookそれぞれ)
graphY = nx.Graph()
graphS = nx.Graph()
graphY.add_nodes_from(range(1, n + 1))
graphS.add_nodes_from(range(1, n + 1))

for i in range(m):
    train = input().split()
    c1, c2 = int(train[0]), int(train[1])
    yen, snook = int(train[2]), int(train[3])
    graphY.add_edge(c1, c2, weight=yen)
    graphS.add_edge(c1, c2, weight=snook)

#都市sからiへのminYen, tからiへのminSnookを求める
ansList = []
for i in range(1, n + 1):
    yen = nx.dijkstra_path_length(graphY, s, i)
    snook = nx.dijkstra_path_length(graphS, t, i)
    ans = yen + snook
    ansList.append(ans)

for i in range(i):
    ans = 1000000000000000 - min(ansList)
    print(ans)
    ansList.pop(0)

Submission status: Runtime Error

Solution code:
import numpy as np


def read():
    n, m, s, t = list(map(int, input().split()))
    #pythonのindexに合わせる
    s -= 1
    t -= 1

    W_a = np.zeros((n, n))
    W_b = np.zeros((n, n))

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

    return n, s, t, W_a, W_b

def dijkstra(s, t, n, W):
    cost = np.zeros(n) - 1
    cost[s] = 0
    flag = (cost == -1)
    processNode = s
    nextNode = [0, 10**15]
    while(True):
        if(processNode == t):
            break

        for i in np.where(flag)[0]:
            mycost = cost[processNode]
            if W[processNode, i] > 0 and (cost[i] == -1 or (mycost + W[processNode, i]) < cost[i]):
                cost[i] = mycost + W[processNode, i]

            if cost[i] > 0 and cost[i] < nextNode[1]:
                nextNode = [i, cost[i]]

        processNode = nextNode[0]
        nextNode = [0, 10**15]
        flag[processNode] = False

    return cost[t]

def main():
    n, s, t, W_a, W_b = read()
    cost = np.zeros(n)
    for i in range(n):
        cost[i] = dijkstra(s, i, n, W_a) + dijkstra(t, i, n, W_b)

    for i in range(n):
        print("{0:15.0f}".format(10**15 - np.min(cost[i:])))

main()