Problem:


Score : 400 points

Problem Statement

Kenkoooo is planning a trip in Republic of Snuke.
In this country, there are n cities and m trains running.
The cities are numbered 1 through n, and the i-th train connects City u_i and v_i bidirectionally.
Any city can be reached from any city by changing trains.

Two currencies are used in the country: yen and snuuk.
Any train fare can be paid by both yen and snuuk.
The fare of the i-th train is a_i yen if paid in yen, and b_i snuuk if paid in snuuk.

In a city with a money exchange office, you can change 1 yen into 1 snuuk.
However, when you do a money exchange, you have to change all your yen into snuuk.
That is, if Kenkoooo does a money exchange when he has X yen, he will then have X snuuk.
Currently, there is a money exchange office in every city, but the office in City i will shut down in i years and can never be used in and after that year.

Kenkoooo is planning to depart City s with 10^{15} yen in his pocket and head for City t, and change his yen into snuuk in some city while traveling.
It is acceptable to do the exchange in City s or City t.

Kenkoooo would like to have as much snuuk as possible when he reaches City t by making the optimal choices for the route to travel and the city to do the exchange.
For each i=0,...,n-1, find the maximum amount of snuuk that Kenkoooo has when he reaches City t if he goes on a trip from City s to City t after i years.
You can assume that the trip finishes within the year.

Constraints

2 \leq n \leq 10^5

1 \leq m \leq 10^5

1 \leq s,t \leq n

s \neq t

1 \leq u_i < v_i \leq n

1 \leq a_i,b_i \leq 10^9

If i\neq j, then u_i \neq u_j  or v_i \neq v_j.

Any city can be reached from any city by changing trains.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

n m s t
u_1 v_1 a_1 b_1
:
u_m v_m a_m b_m

Output

Print n lines.
In the i-th line, print the maximum amount of snuuk that Kenkoooo has when he reaches City t if he goes on a trip from City s to City t after i-1 years.

Sample Input 1

4 3 2 3
1 4 1 100
1 2 1 10
1 3 20 1

Sample Output 1

999999999999998
999999999999989
999999999999979
999999999999897

After 0 years, it is optimal to do the exchange in City 1.

After 1 years, it is optimal to do the exchange in City 2.

Note that City 1 can still be visited even after the exchange office is closed.
Also note that, if it was allowed to keep 1 yen when do the exchange in City 2 and change the remaining yen into snuuk, we could reach City 3 with 999999999999998 snuuk, but this is NOT allowed.

After 2 years, it is optimal to do the exchange in City 3.

After 3 years, it is optimal to do the exchange in City 4.
Note that the same train can be used multiple times.

Sample Input 2

8 12 3 8
2 8 685087149 857180777
6 7 298270585 209942236
2 4 346080035 234079976
2 5 131857300 22507157
4 8 30723332 173476334
2 6 480845267 448565596
1 4 181424400 548830121
4 5 57429995 195056405
7 8 160277628 479932440
1 6 475692952 203530153
3 5 336869679 160714712
2 7 389775999 199123879

Sample Output 2

999999574976994
999999574976994
999999574976994
999999574976994
999999574976994
999999574976994
999999574976994
999999574976994



Sample input:
4 3 2 3
1 4 1 100
1 2 1 10
1 3 20 1


Sample output:
999999999999998
999999999999989
999999999999979
999999999999897

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse import csr_matrix, csgraph
n, m, s, t = map(int, input().split())
src = [list(map(int, input().split())) for _ in range(m)]
u, v, a, b = zip(*src)
pa = csgraph.dijkstra(csr_matrix((a, (u, v)), (n + 1, n + 1)), False, s)
pb = csgraph.dijkstra(csr_matrix((b, (u, v)), (n + 1, n + 1)), False, t)

dist = [-1] * (n + 1)
for i in range(1, n + 1):
    dist[i] = int(pa[i] + pb[i])
dist = sorted(enumerate(dist), key=lambda x: x[1], reverse=True)
dist.pop()

snuk = 10 ** 15
for i in range(n):
    while dist[-1][0] <= i:
        dist.pop()
    else:
        print(snuk - dist[-1][1])

Submission status: Time Limit Exceeded

Solution code:
import heapq
import numpy

def Yen(s):
    Cost = [float("inf") for i in range(n)]
    V = [False for i in range(n)]
    Q = [(0, s-1)]
    Cost[s-1] = 0
    while Q:
        tempCost, tempNode = heapq.heappop(Q)
        V[tempNode] = True
        for node in A[tempNode]:
            if V[node[1]] == False:
                if Cost[node[1]] > tempCost + node[0]:
                    Cost[node[1]] = tempCost + node[0]
                    heapq.heappush(Q, (Cost[node[1]], node[1]))
    return Cost

def Snuuk(t):
    Cost = [float("inf") for i in range(n)]
    V = [False for i in range(n)]
    Q = [(0, t-1)]
    Cost[t-1] = 0
    while Q:
        tempCost, tempNode = heapq.heappop(Q)
        V[tempNode] = True
        for node in B[tempNode]:
            if V[node[1]] == False:
                if Cost[node[1]] > tempCost + node[0]:
                    Cost[node[1]] = tempCost + node[0]
                    heapq.heappush(Q, (Cost[node[1]], node[1]))
    return Cost

n, m ,s, t = map(int, input().split())
ini = 10 ** 15
A = [[] for i in range(n)]
B = [[] for i in range(n)]
for i in range(m):
    u, v, a, b = map(int, input().split())
    u, v = u-1, v-1
    A[u].append((a, v))
    A[v].append((a, u))
    B[u].append((b, v))
    B[v].append((b, u))

totalCost = numpy.zeros((n,), dtype = int)
totalCost += Yen(s)
totalCost += Snuuk(t)

print(ini - numpy.min(totalCost))
for i in range(1, n):
    print(ini - numpy.min(totalCost[i:n]))

Submission status: Time Limit Exceeded

Solution code:
import heapq

def Yen(s):
    Cost = [float("inf") for i in range(n)]
    V = [False for i in range(n)]
    Q = [(0, s-1)]
    Cost[s-1] = 0
    while Q:
        tempCost, tempNode = heapq.heappop(Q)
        V[tempNode] = True
        for node in A[tempNode]:
            if V[node[1]] == False:
                if Cost[node[1]] > tempCost + node[0]:
                    Cost[node[1]] = tempCost + node[0]
                    heapq.heappush(Q, (Cost[node[1]], node[1]))
    return Cost

def Snuuk(t):
    Cost = [float("inf") for i in range(n)]
    V = [False for i in range(n)]
    Q = [(0, t-1)]
    Cost[t-1] = 0
    while Q:
        tempCost, tempNode = heapq.heappop(Q)
        V[tempNode] = True
        for node in B[tempNode]:
            if V[node[1]] == False:
                if Cost[node[1]] > tempCost + node[0]:
                    Cost[node[1]] = tempCost + node[0]
                    heapq.heappush(Q, (Cost[node[1]], node[1]))
    return Cost

n, m ,s, t = map(int, input().split())
ini = 10 ** 15
A = [[] for i in range(n)]
B = [[] for i in range(n)]
for i in range(m):
    u, v, a, b = map(int, input().split())
    u, v = u-1, v-1
    A[u].append((a, v))
    A[v].append((a, u))
    B[u].append((b, v))
    B[v].append((b, u))

YenCost, SnuukCost = Yen(s), Snuuk(t)
TotalCost = []
for i in range(n):
    TotalCost.append(YenCost[i] + SnuukCost[i])

print(ini - min(TotalCost))
for i in range(1, n):
    print(ini - min(TotalCost[i:n]))

Submission status: Time Limit Exceeded

Solution code:
import heapq


class Dijkstra:

    def __init__(self, rote_map, start_point, goal_point=None):
        self.rote_map = rote_map
        self.start_point = start_point
        self.goal_point = goal_point

    def execute(self):
        """
        :param rote_map:
        :param start_point:
        :param distance:
        :return:
        """
        num_of_city = len(self.rote_map)
        dist = [float("inf") for _ in range(num_of_city)]
        prev = [float("inf") for _ in range(num_of_city)]

        dist[self.start_point] = 0
        heap_q = []
        heapq.heappush(heap_q, (0, self.start_point))
        while len(heap_q) != 0:
            prov_cost, src = heapq.heappop(heap_q)

            if dist[src] < prov_cost:
                continue

            for dest in range(num_of_city):
                cost = self.rote_map[src][dest]
                if cost != float("inf") and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost
                    heapq.heappush(heap_q, (dist[dest], dest))
                    prev[dest] = src
        if self.goal_point is not None:
            return self.get_path(self.goal_point, prev)
        else:
            return dist

    def get_path(self, goal, prev):
        path = [goal]
        dest = goal

        while prev[dest] != float("inf"):
            path.append(prev[dest])
            dest = prev[dest]

        return list(reversed(path))


n, m, s, t = map(int, input().split())
yen_route_map = [[float("inf") for j in range(n)] for _ in range(n)]
snuuk_route_map = [[float("inf") for j in range(n)] for _ in range(n)]

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

yen_dijkstra = Dijkstra(yen_route_map, s-1).execute()
snuuk_dijkstra = Dijkstra(snuuk_route_map, t-1).execute()

from itertools import accumulate
ans = list(accumulate([y+s for y, s in zip(yen_dijkstra, snuuk_dijkstra)][::-1],min))
[print(10**15-ans[i]) for i in range(n-1,-1,-1)]

Submission status: Time Limit Exceeded

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

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

Solution code:
import Queue
n,m ,start ,goal = map(int,raw_input().split())

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 xrange(m):
	f, t, y, s = map(int,raw_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 xrange(n)]

m = float("inf")
ans = [0 for i in range(n)]
for i in xrange(n-1,-1,-1):
	ans[i] = min(snuuk_sum[i],m)
	m = ans[i]

for i in xrange(n):
	print 10**15 - ans[i]

Submission status: Time Limit Exceeded

Solution code:
from  heapq import heappush, heappop, heapify

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

nl=[ [ ] for j in range(n+1) ] 

for i in range(m):
	u,v,a,b=map(int,raw_input().split())
	nl[u].append( (v,a,b) )
	nl[v].append( (u,a,b) )

#print nl

v=2


def dij(v,type):
	d=[ float("inf") for i  in range(n+1)]
	d[v]=0

	Q=[]
	heappush(Q,v)

	while len(Q)>0:
		u=heappop(Q)
		for v,yen,snuuk in nl[u]:
			if type=="y":alt=d[u]+yen
			elif type=="s":alt=d[u]+snuuk

			if d[v]> alt:
				d[v]=alt
				heappush(Q,v)
	return d

d_y=dij(s,"y")
d_s=dij(t,"s")

val=float("inf")

A=[]
for i in range(n,0,-1):
	tmp=d_y[i]+d_s[i]
	val=min(val, tmp)
	A.append(val)

for i in reversed(A):
	print 10**15-i

Submission status: Time Limit Exceeded

Solution code:
from  heapq import heappush, heappop, heapify

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

nl=[ [ ] for j in range(n+1) ] 

for i in range(m):
	u,v,a,b=map(int,raw_input().split())
	nl[u].append( (v,a,b) )
	nl[v].append( (u,a,b) )

#print nl

v=2


def dij(v,type):
	d=[ float("inf") for i  in range(n+1)]
	d[v]=0

	Q=[]
	heappush(Q,v)

	while len(Q)>0:
		u=heappop(Q)
		for v,yen,snuuk in nl[u]:
			if type=="y":alt=d[u]+yen
			elif type=="s":alt=d[u]+snuuk

			if d[v]> alt:
				d[v]=alt
				heappush(Q,v)
	return d

d_y=dij(s,"y")
d_s=dij(t,"s")

D=[]

for i in range(1,n+1):
	D.append( (d_y[i]+d_s[i], i ) ) 



D.sort(key=lambda x: x[0])


t=1
for x,N in D:
	for j in range(t,N+1):
		#print j,x
		print 10**15-x
		t+=1
		if t==n+1:
			quit()

Submission status: Time Limit Exceeded

Solution code:
import  heapq

n,m,s,t=map(int,raw_input().split())
src = [ tuple( map( int, raw_input().split() ) )   for i in range(m)]

nl=[ [ ] for j in range(n+1) ] 

for u,v,a,b in src:
	nl[u].append( (v,a,b) )
	nl[v].append( (u,a,b) )

#Dijkstra yen
d_y=[ float("inf") ]*(n+1)
d_y[s]=0

Q=[]
heapq.heappush(Q,s)

while Q:
	u=heapq.heappop(Q)
	for v,yen,snuuk in nl[u]:
		alt=d_y[u]+yen
		if d_y[v]> alt:
			d_y[v]=alt
			heapq.heappush(Q,v)

#Dijkstra snuuk
d_s=[ float("inf")]*(n+1)
d_s[t]=0

Q=[]
heapq.heappush(Q,t)

while Q:
	u=heapq.heappop(Q)
	for v,yen,snuuk in nl[u]:
		alt=d_s[u]+snuuk
		if d_s[v]> alt:
			d_s[v]=alt
			heapq.heappush(Q,v)


val=float("inf")
A=[]
for i in range(n,0,-1):
	tmp=d_y[i]+d_s[i]
	val=min(val, tmp)
	A.append(val)

for i in reversed(A):
	print 10**15-i

Submission status: Time Limit Exceeded

Solution code:
import  heapq

n,m,s,t=map(int,raw_input().split())
src = [ tuple( map( int, raw_input().split() ) )   for i in range(m)]

nl=[ [ ] for j in range(n+1) ] 

for u,v,a,b in src:
	nl[u].append( (v,a,b) )
	nl[v].append( (u,a,b) )

#Dijkstra yen
d_y=[ float("inf") ]*(n+1)
d_y[s]=0

Q=[]
heapq.heappush(Q,s)

while Q:
	u=heapq.heappop(Q)
	for i in nl[u]:
		v=i[0]
		yen=i[1]
		alt=d_y[u]+yen
		if d_y[v]> alt:
			d_y[v]=alt
			heapq.heappush(Q,v)

#Dijkstra snuuk
d_s=[ float("inf")]*(n+1)
d_s[t]=0

Q=[]
heapq.heappush(Q,t)

while Q:
	u=heapq.heappop(Q)
	for i in nl[u]:
		v=i[0]
		snuuku=i[2]
		alt=d_s[u]+snuuku
		if d_s[v]> alt:
			d_s[v]=alt
			heapq.heappush(Q,v)


val=float("inf")
A=[]
for i in range(n,0,-1):
	tmp=d_y[i]+d_s[i]
	val=min(val, tmp)
	A.append(val)

for i in reversed(A):
	print 10**15-i

Submission status: Time Limit Exceeded

Solution code:
import  heapq

n,m,s,t=map(int,raw_input().split())
src = [ tuple( map( int, raw_input().split() ) )   for i in range(m)]

nl=[ [ ] for j in range(n+1) ] 

for u,v,a,b in src:
	nl[u].append( (v,a,b) )
	nl[v].append( (u,a,b) )


def dij(v,type):
	d=[ float("inf")]*(n+1)
	d[v]=0

	Q=[]
	heapq.heappush(Q,v)

	while Q:
		u=heapq.heappop(Q)
		for i in nl[u]:
			v=i[0]
			yen=i[1]
			sunuku=i[2]
			if type=="y":alt=d[u]+yen
			elif type=="s":alt=d[u]+sunuku

			if d[v]> alt:
				d[v]=alt
				heapq.heappush(Q,v)
	return d

d_y=dij(s,"y")
d_s=dij(t,"s")

val=float("inf")

A=[]
for i in range(n,0,-1):
	tmp=d_y[i]+d_s[i]
	val=min(val, tmp)
	A.append(val)

for i in reversed(A):
	print 10**15-i

Submission status: Time Limit Exceeded

Solution code:
import  heapq

n,m,s,t=map(int,raw_input().split())
src = [ tuple( map( int, raw_input().split() ) )   for i in range(m)]

nl=[ [ ] for j in range(n+1) ] 

for u,v,a,b in src:
	nl[u].append( (v,a,b) )
	nl[v].append( (u,a,b) )


def dij(v,type):
	d=[ float("inf") for i  in range(n+1)]
	d[v]=0

	Q=[]
	heapq.heappush(Q,v)

	while Q:
		u=heapq.heappop(Q)
		for i in nl[u]:
			v=i[0]
			yen=i[1]
			sunuku=i[2]
			if type=="y":alt=d[u]+yen
			elif type=="s":alt=d[u]+sunuku

			if d[v]> alt:
				d[v]=alt
				heapq.heappush(Q,v)
	return d

d_y=dij(s,"y")
d_s=dij(t,"s")

val=float("inf")

A=[]
for i in range(n,0,-1):
	tmp=d_y[i]+d_s[i]
	val=min(val, tmp)
	A.append(val)

for i in reversed(A):
	print 10**15-i

Submission status: Time Limit Exceeded

Solution code:
import  heapq

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

nl=[ [ ] for j in range(n+1) ] 

for i in range(m):
	u,v,a,b=map(int,raw_input().split())
	nl[u].append( (v,a,b) )
	nl[v].append( (u,a,b) )


def dij(v,type):
	d=[ float("inf") for i  in range(n+1)]
	d[v]=0

	Q=[]
	heapq.heappush(Q,v)

	while Q:
		u=heapq.heappop(Q)
		for i in nl[u]:
			v=i[0]
			yen=i[1]
			sunuku=i[2]
			if type=="y":alt=d[u]+yen
			elif type=="s":alt=d[u]+sunuku

			if d[v]> alt:
				d[v]=alt
				heapq.heappush(Q,v)
	return d

d_y=dij(s,"y")
d_s=dij(t,"s")

val=float("inf")

A=[]
for i in range(n,0,-1):
	tmp=d_y[i]+d_s[i]
	val=min(val, tmp)
	A.append(val)

for i in reversed(A):
	print 10**15-i

Submission status: Time Limit Exceeded

Solution code:
from  heapq import heappush, heappop, heapify

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

nl=[ [ ] for j in range(n+1) ] 

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


def dij(v,type):
	d=[ float("inf") for i  in range(n+1)]
	d[v]=0

	Q=[]
	heappush(Q,v)

	while Q:
		u=heappop(Q)
	#	print u, nl[u]
		for i in nl[u]:
			#print "i::",i
			v=i[0]
			yen=i[1]
			sunuku=i[2]
		#	print v,yen,sunuku,d
			if type=="y":alt=d[u]+yen
			elif type=="s":alt=d[u]+sunuku

			if d[v]> alt:
				d[v]=alt
				heappush(Q,v)
	return d

d_y=dij(s,"y")
d_s=dij(t,"s")

val=float("inf")

A=[]
for i in range(n,0,-1):
	tmp=d_y[i]+d_s[i]
	val=min(val, tmp)
	A.append(val)

for i in reversed(A):
	print(10**15-i)

Submission status: Time Limit Exceeded

Solution code:
from  heapq import heappush, heappop, heapify

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

nl=[ [ ] for j in range(n+1) ] 

for i in range(m):
	u,v,a,b=map(int,raw_input().split())
	nl[u].append( (v,a,b) )
	nl[v].append( (u,a,b) )


def dij(v,type):
	d=[ float("inf") for i  in range(n+1)]
	d[v]=0

	Q=[]
	heappush(Q,v)

	while Q:
		u=heappop(Q)
	#	print u, nl[u]
		for i in nl[u]:
			#print "i::",i
			v=i[0]
			yen=i[1]
			sunuku=i[2]
		#	print v,yen,sunuku,d
			if type=="y":alt=d[u]+yen
			elif type=="s":alt=d[u]+sunuku

			if d[v]> alt:
				d[v]=alt
				heappush(Q,v)
	return d

d_y=dij(s,"y")
d_s=dij(t,"s")

val=float("inf")

A=[]
for i in range(n,0,-1):
	tmp=d_y[i]+d_s[i]
	val=min(val, tmp)
	A.append(val)

for i in reversed(A):
	print 10**15-i

Submission status: Time Limit Exceeded

Solution code:
from  heapq import heappush, heappop, heapify

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

nl=[ [ ] for j in range(n+1) ] 

for i in range(m):
	u,v,a,b=map(int,raw_input().split())
	nl[u].append( (v,a,b) )
	nl[v].append( (u,a,b) )


def dij(v,type):
	d=[ float("inf") for i  in range(n+1)]
	d[v]=0

	Q=[]
	heappush(Q,v)

	while len(Q)>0:
		u=heappop(Q)
	#	print u, nl[u]
		for i in nl[u]:
			#print "i::",i
			v=i[0]
			yen=i[1]
			sunuku=i[2]
		#	print v,yen,sunuku,d
			if type=="y":alt=d[u]+yen
			elif type=="s":alt=d[u]+sunuku

			if d[v]> alt:
				d[v]=alt
				heappush(Q,v)
	return d

d_y=dij(s,"y")
d_s=dij(t,"s")

val=float("inf")

A=[]
for i in range(n,0,-1):
	tmp=d_y[i]+d_s[i]
	val=min(val, tmp)
	A.append(val)

for i in reversed(A):
	print 10**15-i

Submission status: Time Limit Exceeded

Solution code:
from  heapq import heappush, heappop, heapify

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

nl=[ [ ] for j in range(n+1) ] 

for i in range(m):
	u,v,a,b=map(int,raw_input().split())
	nl[u].append( (v,a,b) )
	nl[v].append( (u,a,b) )

#print nl

v=2


def dij(v,type):
	d=[ float("inf") for i  in range(n+1)]
	d[v]=0

	Q=[]
	heappush(Q,v)

	while len(Q)>0:
		u=heappop(Q)
	#	print u, nl[u]
		for i in nl[u]:
			#print "i::",i
			v=i[0]
			yen=i[1]
			sunuku=i[2]
		#	print v,yen,sunuku,d
			if type=="y":alt=d[u]+yen
			elif type=="s":alt=d[u]+sunuku

			if d[v]> alt:
				d[v]=alt
				heappush(Q,v)
	return d

d_y=dij(s,"y")
d_s=dij(t,"s")

D=[]

for i in range(1,n+1):
	D.append( (d_y[i]+d_s[i], i ) ) 



D.sort(key=lambda x: x[0])


t=1
for x,N in D:
	for j in range(t,N+1):
		#print j,x
		print 10**15-x
		t+=1
		if t==n+1:
			quit()

Submission status: Time Limit Exceeded

Solution code:
import heapq
from itertools import accumulate

n,m,s,t = map(int,input().split())
inf = 1000000000000000
gyen = [[] for _ in range(n)]
gsnuk = [[] for _ in range(n)]

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

def dijkstra(graph, start):
        dist = [inf for _ in range(n)]
        dist[start] = 0
        q = [(0,start)]
        rem = n-1
        while q and rem>0:
                du, u = heapq.heappop(q)
                if dist[u] < du:
                        continue
                rem -= 1
                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: Time Limit Exceeded

Solution code:
import heapq
from itertools import accumulate

n,m,s,t = map(int,input().split())
inf = 1000000000000000
gyen = [[] for _ in range(n)]
gsnuk = [[] for _ in range(n)]

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

def dijkstra(graph, start):
        dist = [inf for _ in range(n)]
        dist[start] = 0
        q = [(0,start)]
        while q:
                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: Time Limit Exceeded

Solution code:
import heapq

n,m,s,t = map(int,input().split())
inf = 1000000000000000
gyen = [[] for _ in range(n)]
gsnuuk = [[] for _ in range(n)]

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

def dijkstra(graph, start):
        dist = [inf for _ in range(n)]
        dist[start] = 0
        q = [(0,start)]
        while q:
                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

dist_from_start = dijkstra(gyen,s-1)
dist_from_goal = dijkstra(gsnuuk,t-1)

ans = [0 for _ in range(n)]
ans[n-1] = dist_from_start[n-1]+dist_from_goal[n-1]
for i in range(n-1):
        ans[n-2-i] = min(ans[n-1-i],dist_from_start[n-2-i]+dist_from_goal[n-2-i])
[print(inf-ans[i]) for i in range(n)]

Submission status: Time Limit Exceeded

Solution code:
import heapq

n,m,s,t = map(int,input().split())
inf = 1000000000000000
gyen = [[] for _ in range(n)]
gsnuuk = [[] for _ in range(n)]

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

def dijkstra(graph, start):
        dist = [inf for _ in range(n)]
        dist[start] = 0
        q = [(0,start)]
        while q:
                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

dist_from_start = dijkstra(gyen,s-1)
dist_from_goal = dijkstra(gsnuuk,t-1)

ans = [0 for _ in range(n)]
ans[n-1] = dist_from_start[n-1]+dist_from_goal[n-1]
for i in range(n-1):
        ans[n-2-i] = min(ans[n-1-i],dist_from_start[n-2-i]+dist_from_goal[n-2-i])
for i in range(n):
        print(inf-ans[i])

Submission status: Time Limit Exceeded

Solution code:
import heapq

n,m,s,t = map(int,input().split())
inf = 1000000000000000
gyen = [[] for _ in range(n)]
gsnuuk = [[] for _ in range(n)]

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

def dijkstra(graph, start):
        dist = [inf for _ in range(n)]
        dist[start] = 0
        q = [(0,start)]
        while q:
                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

dist_from_start = dijkstra(gyen,s-1)
dist_from_goal = dijkstra(gsnuuk,t-1)

for i in range(n):
        ans = inf
        for j in range(i,n):
                tmp = dist_from_start[j] + dist_from_goal[j]
                if tmp < ans:
                        ans = tmp
        print(inf - ans)

Submission status: Time Limit Exceeded

Solution code:
n,m,s,t = map(int,input().split())
infinit = 1000000000000000
gyen = [[] for _ in range(n)]
gsnuuk = [[] for _ in range(n)]

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

def dijkstra(graf, start):
        distance = [infinit for _ in range(n)]
        distance[start] = 0
        pre = start
        q = []
        q.extend(range(n))
        q.remove(start)
        while q:
                for i in graf[pre]:
                        distance[i[0]] = min(distance[pre]+i[1],distance[i[0]])
                tmp = infinit
                for i in q:
                        if distance[i] <= tmp:
                                tmp = distance[i]
                                pre = i
                q.remove(pre)
        return distance

distance_from_start = dijkstra(gyen,s-1)
distance_from_goal = dijkstra(gsnuuk,t-1)

for i in range(n):
        ans = infinit
        for j in range(i,n):
                tmp = distance_from_start[j] + distance_from_goal[j]
                if tmp < ans:
                        ans = tmp
        print(infinit - ans)

Submission status: Time Limit Exceeded

Solution code:
n, m, s, t = map(int, input().split())
route = []
for i in range(m):
    route.append(list(map(int, input().split())))


def dijkstra(n, s, t, route, a_or_b):
    if a_or_b == "a":
        kane = 2
    else:
        kane = 3

    cost = {}
    for i in range(n):
        cost[i+1] = float("inf")

    decision = {s:0}
    cost[s] = 0

    while(not t in decision):
        for i in route:
            if (i[0] in decision) and (i[1] not in decision):
                cost[i[1]] = min(cost[i[1]], cost[i[0]] + i[kane])
            elif (i[1] in decision) and (i[0] not in decision):
                cost[i[0]] = min(cost[i[0]], cost[i[1]] + i[kane])

        min_tosi = [0,float("inf")]
        for i in range(n):
            if i+1 not in decision:
                if min_tosi[1] > cost[i+1]:
                    min_tosi = [i+1, cost[i+1]]
        decision[min_tosi[0]] = min_tosi[1]

    return cost[t]


min_cost = float("inf")
li = []
for year in reversed(range(n)):
    min_cost = min(min_cost, dijkstra(n, s, year+1, route, "a") + dijkstra(n, year+1, t, route, "b"))

    li.append(10**15 - min_cost)

for i in reversed(li):
    print(i)

Submission status: Time Limit Exceeded

Solution code:
n, m, s, t = map(int, input().split())
route = []
for i in range(m):
    route.append(list(map(int, input().split())))


def dijkstra(n, s, t, route, a_or_b):
    if a_or_b == "a":
        kane = 2
    else:
        kane = 3

    cost = {}
    for i in range(n):
        cost[i+1] = float("inf")

    decision = {s:0}
    cost[s] = 0

    while(not t in decision):
        for i in route:
            if (i[0] in decision) and (i[1] not in decision):
                cost[i[1]] = min(cost[i[1]], cost[i[0]] + i[kane])
            elif (i[1] in decision) and (i[0] not in decision):
                cost[i[0]] = min(cost[i[0]], cost[i[1]] + i[kane])

        min_tosi = [0,float("inf")]
        for i in range(n):
            if i+1 not in decision:
                if min_tosi[1] > cost[i+1]:
                    min_tosi = [i+1, cost[i+1]]
        decision[min_tosi[0]] = min_tosi[1]

    return cost[t]

# print(dijkstra(n, s, t, rout, "b"))
min_cost_dic = {}
for year in range(n):
    min_cost = float("inf")
    for i in range(year,n):
        if i not in min_cost_dic:
            min_cost_dic[i] = dijkstra(n, s, i+1, route, "a") + dijkstra(n, i+1, t, route, "b")

        min_cost = min(min_cost, min_cost_dic[i])

    print(10**15 - min_cost)

Submission status: Time Limit Exceeded

Solution code:
n, m, s, t = map(int, input().split())
route = []
for i in range(m):
    route.append(list(map(int, input().split())))


def dijkstra(n, s, t, route, a_or_b):
    if a_or_b == "a":
        kane = 2
    else:
        kane = 3

    cost = {}
    for i in range(n):
        cost[i+1] = float("inf")

    decision = {s:0}
    cost[s] = 0

    while(not t in decision):
        for i in route:
            if (i[0] in decision) and (i[1] not in decision):
                cost[i[1]] = min(cost[i[1]], cost[i[0]] + i[kane])
            elif (i[1] in decision) and (i[0] not in decision):
                cost[i[0]] = min(cost[i[0]], cost[i[1]] + i[kane])

        min_tosi = [0,float("inf")]
        for i in range(n):
            if i+1 not in decision:
                if min_tosi[1] > cost[i+1]:
                    min_tosi = [i+1, cost[i+1]]
        decision[min_tosi[0]] = min_tosi[1]

    return cost[t]

# print(dijkstra(n, s, t, rout, "b"))
min_cost_dic = {}
for year in range(n):
    min_cost = float("inf")
    for i in range(year,n):
        if i in min_cost_dic:
            min_cost = min(min_cost, min_cost_dic[i])
        else:
            min_cost_dic[i] = dijkstra(n, s, i+1, route, "a") + dijkstra(n, i+1, t, route, "b")
            min_cost = min(min_cost, min_cost_dic[i])

    print(10**15 - min_cost)