Problem:


Score : 600 points

Problem Statement

We have N points numbered 1 to N arranged in a line in this order.

Takahashi decides to make an undirected graph, using these points as the vertices.
In the beginning, the graph has no edge. Takahashi will do M operations to add edges in this graph.
The i-th operation is as follows:

The operation uses integers L_i and R_i between 1 and N (inclusive), and a positive integer C_i. For every pair of integers (s, t) such that L_i \leq s < t \leq R_i, add an edge of length C_i between Vertex s and Vertex t.

The integers L_1, ..., L_M, R_1, ..., R_M, C_1, ..., C_M are all given as input.

Takahashi wants to solve the shortest path problem in the final graph obtained. Find the length of the shortest path from Vertex 1 to Vertex N in the final graph.

Constraints

2 \leq N \leq 10^5

1 \leq M \leq 10^5

1 \leq L_i < R_i \leq N

1 \leq C_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N M
L_1 R_1 C_1
:
L_M R_M C_M

Output

Print the length of the shortest path from Vertex 1 to Vertex N in the final graph.
If there is no shortest path, print -1 instead.

Sample Input 1

4 3
1 3 2
2 4 3
1 4 6

Sample Output 1

5

We have an edge of length 2 between Vertex 1 and Vertex 2, and an edge of length 3 between Vertex 2 and Vertex 4, so there is a path of length 5 between Vertex 1 and Vertex 4.

Sample Input 2

4 2
1 2 1
3 4 2

Sample Output 2

-1

Sample Input 3

10 7
1 5 18
3 4 8
1 3 5
4 7 10
5 9 8
6 10 5
8 10 3

Sample Output 3

28



Sample input:
4 3
1 3 2
2 4 3
1 4 6


Sample output:
5

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
A=[float('inf')]*N
idx = [float('inf')]*N

T=[]
for i in range(M):
	a,b,c=map(int,input().split())
	a-=1
	b-=1
	T.append([b,a,c])
T.sort()

A[0]=0
for t in T:
	s,g,c=t[1],t[0],t[2]
	
	mv = float('inf')
	mi = -1
	for i in range(s,g)[::-1]:
		if mi!=-1 and idx[mi]<=i:
			continue
		if A[i]!=float('inf'):
			mv = min(A[i],mv)
			mi = idx[i]

	if mv!=float('inf'):
		A[g] = min(A[g], mv + c)
		idx[g] = s+1

if A[-1]!=float('inf'):
	print(A[-1])
else:
	print(-1)

Submission status: Wrong Answer

Solution code:
import numpy as np
N, M = map(int, input().split())
LRC = sorted([list(map(int, input().split())) for i in range(M)], key=lambda x: (x[0], x[1]))

dp = np.full(N+1, 10**6)
dp[1] = 0
print(dp)
for l, r, c in LRC:
    dp[l:r+1] = np.minimum(dp[l:r+1], dp[l] + c)
    print(dp)

if dp[-1] < 10**6:
    print(dp[-1])
else:
    print(-1)

Submission status: Wrong Answer

Solution code:

import sys
def input():
	return sys.stdin.readline().strip()


N, M = list(map(int, input().split()))

LRC = []
for _ in range(M):
	LRC.append(tuple(map(int, input().split())))

LRC.sort()


class seg_tree():
	def __init__(self, N):
		# N: 処理する区間の長さ
		self.N0 = 2 ** (N - 1).bit_length()
		self.INF = 2 ** 31 - 1 #単位限的なもの(最小値なので、非常に大きい値を置いておく)
		self.data = [self.INF] * (2 * self.N0)

	# a_k の値を x に更新
	def update(self, k, x):
		#値は0始まり
		k += self.N0 - 1
		self.data[k] = x
		while k >= 0:
			k = (k - 1) // 2
			self.data[k] = min(self.data[2 * k + 1], self.data[2 * k + 2])

	# 区間[l, r)の最小値
	def query(self, l, r):
		L = l + self.N0
		R = r + self.N0
		s = self.INF
		while L < R:
			if R & 1:
				R -= 1
				s = min(s, self.data[R - 1])

			if L & 1:
				s = min(s, self.data[L - 1])
				L += 1
			L >>= 1
			R >>= 1
		return s

dist = seg_tree(N)
dist.update(0, 0)

for i in range(M):
	L, R, C = LRC[i]
	L -= 1
	R -= 1
	dist_start = dist.query(L, N)
	target_dist = dist.query(R, N)
	if dist_start + C < target_dist:
		dist.update(R, dist_start + C)


ans = dist.query(N - 1, N)
if ans == dist.INF:
	print(-1)
else:
	print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

N, M = map(int, input().split())

items = []
for _ in range(M):
	l, r, c = map(int, input().split())
	items.append([l, r, c])

items.sort()
def check():
	queue = []
	index = 0
	data = [None]
	for i in range(1, N):
		while index < M:
			l, r, c = items[index]
			if l <= i:
				heapq.heappush(queue, (c, r))
				index += 1
			else:
				break
		while True:
			if len(queue) == 0:
				return None
			c, r = queue[0]
			if r > i:
				break
			heapq.heappop(queue)
		data.append((c, r))
	return data

data = check()
if data != None:
	i = 1
	count = 0
	while i < N:
		c, r = data[i]
		count += c
		i = r
	if i == N:
		print(count)
	else:
		print(-1)
else:
	print(-1)

Submission status: Wrong Answer

Solution code:
import copy
import numpy as np
N, M = map(int, input().split())

A = []
for i in range(M):
    A.append(list(map(int, input().split())))

A = np.array(A)
A_1 = A[:, 0]
arg_A_1 = np.argsort(A_1)
new_A = A[arg_A_1]
# print(A, A_1, arg_A_1, new_A)

INF = 10**9 + 1
dp = [INF] * N
dp[0] = 0
for i in range(M):
    tmp = new_A[i]
    left = tmp[0]-1
    right = tmp[1]

    for now_l in range(left, right):
        for now_r in range(now_l+1, right):
            # print(tmp[2], now_l, now_r)
            dp[now_r] = min(dp[now_l] + tmp[2], dp[now_r])
if dp[N-1]==INF:
    print(-1)
else:
    print(dp[N-1])

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
LRC = []
for _ in range(M):
    LRC.append(list(map(int,input().split())))
LRC.sort(key=lambda x: x[1])
LRC.sort(key=lambda x: x[0])

dp=[float('inf') for _ in range(N+10)]
dp[0] = 0
dp[1] = 0

for l,r,c in LRC:
    for d in range(r-l+1):
        dp[l+d] = min(dp[l]+c,dp[l+d])
print(dp[N])

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
inf = 10 * 9
dp = [inf for i in range(N + 1)]
dp[0] = 0
dp[1] = 0
LRC = [list(map(int,input().split())) for i in range(M)]
LRC.sort()
for i in range(M):
    L = LRC[i][0]
    R = LRC[i][1]
    C = LRC[i][2]
    for i in range(L + 1, R + 1):
        dp[i] = min(C + dp[L], dp[i])
        if i == 1:
            dp[1] = 0
if dp[N] == inf:
    print(-1)
    exit()
print(dp[N])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline


def main():


    N, M = map(int, input().split())
    LRC = [list(map(int, input().split())) for _ in range(M)]

    LRC.sort(key=lambda x: (x[0], x[1]))
    # print(LRC)

    dp = [10 ** 9 + 10] * (N + 1)
    dp[1] = 0

    sml, big = LRC[0][0], LRC[0][1]

    for i in range(1, M):
        l, r, c = LRC[i]
        if l <= big:
            if big <= r:
                big = r
        else:
            print(-1)
            exit()
    if sml != 1 or big != N:
        print(0)
        exit()


    for lrc in LRC:
        l, r, c = lrc
        for i in range(l, r + 1):
            dp[i] = min(dp[i], dp[l] + c)
    print(dp[-1])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
from operator import itemgetter

N, M = map(int, input().split())
LRC = []

D = np.array([float('Inf')] * (N+1))
D[1] = 0

for m in range(M):
    l, r, c = map(int, input().split())
    LRC.append([l, r, c])

LRC.sort(key=itemgetter(0))
LRC.sort(key=itemgetter(1))

rmax = 0
for m in range(M):
    l, r, c = LRC[m][0], LRC[m][1], LRC[m][2]
    for a in range(rmax+1, r+1):
        if D[a] > D[l] + c:
            D[a:r+1] = D[l] + c
            break
    rmax = max(rmax, r)

if D[N] < float('Inf'):
    print(int(D[N]))
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
inf = 10 * 9
dp = [inf for i in range(N + 1)]
dp[0] = 0
dp[1] = 0
LRC = [list(map(int,input().split())) for i in range(M)]
LRC.sort()
for i in range(M):
    L = LRC[i][0]
    R = LRC[i][1]
    C = LRC[i][2]
    for i in range(L + 1, R + 1):
        dp[i] = min(C + dp[L], dp[i])
        if i == 1:
            dp[1] = 0
if dp[N] == inf:
    print(-1)
    exit()
print(dp[N])

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
ls=[]
for i in range(M):
  ls.append(list(map(int,input().split())))
ls.sort()
print(ls)

Submission status: Wrong Answer

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


class SegmentTree():
    '''
    非再帰
    segment tree
    '''

    def __init__(self, n, func, init=float('inf')):
        '''
        n->配列の長さ
        func:func(a,b)->val,　func=minだとRMQになる
        木の高さhとすると,
        n:h-1までのノード数。h段目のノードにアクセスするために使う。
        data:ノード。
        parent:k->child k*2+1とk*2+2
        '''
        self.n = 2**(n-1).bit_length()
        self.init = init
        self.data = [init]*(2*self.n)
        self.func = func

    def set(self, k, v):
        '''
        あたいの初期化
        '''
        self.data[k+self.n-1] = v

    def build(self):
        '''
        setの後に一斉更新
        '''
        for k in reversed(range(self.n-1)):
            self.data[k] = self.func(self.data[k*2+1], self.data[k*2+2])

    def update(self, k, a):
        '''
        list[k]=aに更新する。
        更新ぶんをrootまで更新
        '''
        k += self.n-1
        self.data[k] = a

        while k > 0:
            k = (k-1)//2
            self.data[k] = self.func(self.data[k*2+1], self.data[k*2+2])

    def query(self, l, r):
        '''
        [l,r)のfuncを求める
        '''
        L = l+self.n
        R = r+self.n
        ret = self.init
        while L < R:
            if R & 1:
                R -= 1
                ret = self.func(ret, self.data[R-1])
            if L & 1:
                ret = self.func(ret, self.data[L-1])
                L += 1
            L >>= 1
            R >>= 1
        return ret


N, C = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(C)]
L = sorted(L, key=lambda x: (x[1], -x[2], x[0]), reverse=True)

Seg = SegmentTree(N+1, func=lambda a, b: min(a, b))
Seg.set(N, 0)
Seg.build()

dist = [float("inf")]*(N+1)
dist[-1] = 0
for l, r, c in L:
    new = Seg.query(l, r+1)+c
    Seg.set(l, new)
    Seg.build()
ans = Seg.query(1, 2)
if ans == float('inf'):
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

N, M = map(int, input().split())

items = []
for _ in range(M):
	l, r, c = map(int, input().split())
	items.append([l, r, c])

items.sort()
def check():
	queue = []
	index = 0
	data = [None]
	for i in range(1, N):
		while index < M:
			l, r, c = items[index]
			if l <= i:
				heapq.heappush(queue, (c, r))
				index += 1
			else:
				break
		while queue:
			c, r = queue[0]
			if r > i:
				break
			heapq.heappop(queue)
		if len(queue) == 0:
			return None
		data.append((c, r))
	return data

data = check()
if data != None:
	i = 1
	count = 0
	while i < N:
		c, r = data[i]
		count += c
		i = r
	if i == N:
		print(count)
	else:
		print(-1)
else:
	print(-1)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
lrc=[list(map(int,input().split())) for _ in range(m)]
lrc.sort(key=lambda x:x[0])
lrc.sort(key=lambda x:x[1])

l=[1]
r=[1]
c=[0]
for i in range(m):
    ll,rr,cc=lrc[i]
    l.append(ll)
    r.append(rr)
    c.append(cc)

if l[0]!=1:
    print(-1)
    exit()



import bisect

for i in range(1,m+1):
    x=bisect.bisect_left(r,l[i])
    if x>=i:
        continue
    c[i]+=min(c[x:i])


x=bisect.bisect_left(r,n)
if x==m:
    print(-1)
    exit()
ans=min(c[x:])


lrc.sort(key=lambda x:x[0])
ll=lrc[0][0]
rr=lrc[0][1]
for i in range(1,m):
    l,r,c=lrc[i]
    if rr<l:
        print(-1)
        exit()
    rr=r

print(ans)

Submission status: Wrong Answer

Solution code:
[N,M] = list(map(int,input().split()))

LRC = []
for i in range(M):
    tmp = list(map(int,input().split()))
    LRC.append((tmp[0],tmp[1],tmp[2]))

LRC = sorted(LRC, key=lambda x: (x[0], x[1]))

cnt = [2*10**9]*N
cnt[0] = 0

for i in range(M):
    Lt = LRC[i][0]
    Rt = LRC[i][1]
    Ct = LRC[i][2]
    cnt[Rt-1]=min(min(cnt[(Lt-1):(Rt-1)])+Ct,cnt[Rt-1])

if cnt[-1]==2*10**9:
    print(-1)
else:
    print(cnt[-1])

Submission status: Wrong Answer

Solution code:
n, m = list(map(int, input().split()))
inf = 10 ** 9
path_data = []
for i in range(m):
    path_data.append(list(map(int, input().split())))
path_data.sort()
dp = [inf] * (n + 1)
dp[0] = 0
dp[1] = 0
for i in range(m):
    l = path_data[i][0]
    r = path_data[i][1]
    c = path_data[i][2]
    for j in range(l, r+1):
        dp[j] = min(dp[j], dp[l] + c)
if dp[-1] == inf:
    print(-1)
else:
    print(dp[-1])

Submission status: Wrong Answer

Solution code:
import heapq
n, m = [int(i) for i in input().split()]
lrc = []
for _ in range(m):
    l, r, c = [int(i) for i in input().split()]
    lrc.append([l-1, r-1, c])
lrc.sort()
a = []
j = 0
for i in range(n-1):
    new = []
    while j < m and lrc[j][0] == i:
        new.append(lrc[j])
        j += 1
    if i == 0:
        now = 0
    else:
        while True:
            if len(a) == 0:
                print(-1)
                exit()
            now = heapq.heappop(a)
            if now[1] >= i:
                heapq.heappush(a, now)
                break
        now = now[0]
    for k in new:
        a.append([now + k[2], k[1]])


while True:
    if len(a) == 0:
        print(-1)
        exit()
    now = heapq.heappop(a)
    if now[1] >= n-1:
        heapq.heappush(a, now)
        break
now = now[0]
print(now)

Submission status: Wrong Answer

Solution code:
import numpy as np
from operator import itemgetter

N, M = map(int, input().split())
LRC = []

D = np.array([float('Inf')] * (N+1))
D[1] = 0

for m in range(M):
    l, r, c = map(int, input().split())
    LRC.append([l, r, c])

LRC.sort(key=itemgetter(1))

rmax = 0
for m in range(M):
    l, r, c = LRC[m][0], LRC[m][1], LRC[m][2]
    for a in range(rmax+1, r+1):
        if D[a] > D[l] + c:
            D[a:r+1] = D[l] + c
            break
    rmax = max(rmax, r)

if D[N] < float('Inf'):
    print(int(D[N]))
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline


def main():
    N, M = map(int, input().split())
    A = []
    for _ in range(M):
        A.append(list(map(int, input().split())))
    A.sort(key=lambda x: x[1])
    A.sort(key=lambda x: x[0])
#    print(A)
    dp = [[float("inf")]*N for _ in range(M+1)]
    dp[0][0] = 0
    for i, (s, t, c) in enumerate(A):
        for j in range(t+1):
            if j < s:
                dp[i+1][j-1] = dp[i][j-1]
            else:
                dp[i+1][j-1] = min(dp[i][j-1], dp[i][s-1] + c)
    ans = dp[M][N-1]
#    for x in dp:
#        print(x)
    if ans == float("inf"):
        print(-1)
    else:
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
LRC = [list(map(int, input().split())) for _ in range(M)]

LRC.sort(key=lambda x: (x[0], x[1]))
# print(LRC)

dp = [float('inf')] * (N + 1)
dp[1] = 0

sml, big = LRC[0][0], LRC[0][1]

for i in range(1, M):
    l, r, c = LRC[i]
    if l <= big:
        if big <= r:
            big = r
    else:
        print(-1)
        exit()
if sml != 1 or big != N:
    print(0)
    exit()



for lrc in LRC:
    l, r, c = lrc
    for i in range(l, r + 1):
        dp[i] = min(dp[i], dp[l] + c)
print(dp[-1])

Submission status: Wrong Answer

Solution code:
n, m = [int(x) for x in input().split(' ')]

x = []
for i in range(m):
    x.append([int(x) for x in input().split(' ')])

data = [10 ** 9] * (n + 1)
data[1] = 0

for l, r, c in sorted(x):
    for j in range(l, r):
        for k in range(j + 1, r + 1):
            v = data[j] + c
            if v < data[k]:
                data[k] = v

if data[n] == 10 ** 9:
    print(-1)
else:
    print(data[n])

Submission status: Wrong Answer

Solution code:
import heapq
import sys

input = sys.stdin.readline

def dijkstra_heap(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

n,w=map(int,input().split())#n:頂点数　w:辺の数

edge = [[] for i in range(n)] #edge[i] : iから出る道の[重み,行先]の配列
for i in range(w):
    x,y,z = map(int,input().split())
    x-=1
    y-=1
    for j in range(x+1,y+1):
        edge[x].append([z,j])
    for k in range(x,y):
        edge[y].append([z,k]) 
#print(edge)
print(dijkstra_heap(0)[-1])

Submission status: Wrong Answer

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import bisect

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))
N, M = LI()
dp = [[mod for i in range(N)] for i in range(N)]
for i in range(N):
    dp[i][i] = 0
for m in range(M):
    L,R,c = LI()
    L -= 1
    R -= 1
    for l in range(L,R):
        for r in range(l+1,R+1):
            dp[l][r] = min(dp[l][r], c)

# print(dp)
dp2 = [mod for i in range(N)]
dp2[0] = 0
for i in range(N):
    for j in range(i):
        print(i,j)
        dp2[i] = min(dp2[i], dp2[j] + dp[j][i])
if dp2[-1] == mod:
    print(-1)
else:
    print(dp2[-1])

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
LRC = [list(map(int, input().split())) for _ in range(M)]

LRC.sort(key=lambda x: (x[0], x[1]))
# print(LRC)

dp = [float('inf')] * (N + 1)
dp[1] = 0

sml, big = LRC[0][0], LRC[0][1]

for i in range(1, M):
    l, r, c = LRC[i]
    if l <= big:
        if big <= r:
            big = r
    else:
        print(-1)
        exit()
if sml != 1 or big != N:
    print(0)
    exit()



for lrc in LRC:
    l, r, c = lrc
    for i in range(l, r + 1):
        dp[i] = min(dp[i], dp[l] + c)
print(dp[-1])

Submission status: Wrong Answer

Solution code:
import bisect
import sys
input = sys.stdin.readline


n, m = map(int, input().split())
edges = []
for _ in range(m):
    l, r, c = map(int, input().split())
    edges.append([l-1, r-1, c])

edges.sort()

DP = [[0, 0]]
#DP = [float('INF')] * n
#DP[0] = 0

#for l, r, c in edges:
#    for i in range(l+1, r+1):
#        DP[i] = min(DP[i], DP[l]+c)

for l, r, c in edges:
    idx = bisect.bisect_left(DP, [l, 0])
    if idx == len(DP):
        print(-1)
        exit()
    dist = DP[idx][1] + c
    nidx = bisect.bisect_left(DP, [r, 0])
    if len(DP) == nidx:
        DP.append([r, dist])
    elif DP[nidx][0] == r:
        if dist < DP[nidx][1]:
            DP[nidx][1] = dist
    else:
        DP.insert(nidx, [r, dist])

v, d = DP[-1]
if v == n-1:
    print(d)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
import bisect
n,m=map(int,input().split())
#bitの構築
n_max=10**5
nn=n_max.bit_length()+1
BIT=[0]*(2**nn)
BIT.insert(0,0)

# i が与えられたとき a1~aiまでの和を計算する( O(log n) )
def bitsum(BIT,i):
  s=0
  while i>0:
    s+=BIT[i]
    i-=i&(-i)
  return s

# i と x が与えられたとき ai += x とする ( O(log n) )
def bitadd(BIT,i,x):
  while i<=2**nn:
    BIT[i]+=x
    i+=i&(-i)
  return BIT
D=[0]
P=[]
ans=float("inf")
bitadd(BIT,1,1)
for i in range(m):
  l,r,c=map(int,input().split())
  P.append((l,r,c))
P.sort(key=lambda x:x[1])
for l,r,c in P:
  if l==1:
    ind=0
  else:
    ind=bitsum(BIT,l-1)
  if ind<len(D) and D[ind]+c>D[-1]:
    D.append(D[ind]+c)
    bitadd(BIT,r,1)
    if r==n:
      ans=min(ans,D[-1])
print(-1 if ans==float("inf") else ans)

Submission status: Wrong Answer

Solution code:
def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
                v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
            break
        used[v] = True
            
        for j in range(n):
            d[j] = min(d[j],d[v]+cost[v][j])
    return d

n, m = [int(x) for x in input().split()]

cost = [[float("inf") for i in range(n)] for i in range(n)] 
#cost[u][v] : 辺uvのコスト(存在しないときはinf この場合は10**10)
for i in range(m):
    l,r,z = map(int,input().split())
    for j in range(l, r):
        for k in range(j+1, r+1):
            cost[j-1][k-1] = min(z, cost[j-1][k-1])
            cost[k-1][j-1] = min(z, cost[k-1][j-1])
ret = dijkstra(0,n,m,cost)
if (ret[-1] == 'inf'):
    print(-1)
else:
    print(ret[-1])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline


def main():
    N, M = map(int, input().split())
    A = []
    for _ in range(M):
        A.append(list(map(int, input().split())))
    A.sort(key=lambda x: x[1])
    A.sort(key=lambda x: x[0])
    dp = [[float("inf")]*(N+1) for _ in range(M+1)]
    dp[0][0] = 0
    for i, (s, t, c) in enumerate(A):
        for j in range(s, t+1):
            dp[i+1][j-1] = min(dp[i][j-1], dp[i][s-1] + c)
    ans = dp[M][N-1]
    if ans == float("inf"):
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
                v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
            break
        used[v] = True
            
        for j in range(n):
            d[j] = min(d[j],d[v]+cost[v][j])
    return d
n, m = [int(x) for x in input().split()]

cost = [[float("inf") for i in range(n)] for i in range(n)] 
#cost[u][v] : 辺uvのコスト(存在しないときはinf この場合は10**10)
for i in range(m):
    l,r,z = map(int,input().split())
    for j in range(l, r):
        for k in range(j+1, r+1):
            cost[j-1][k-1] = min(z, cost[j-1][k-1])
            cost[k-1][j-1] = min(z, cost[k-1][j-1])
print(dijkstra(0,n,m,cost))

Submission status: Wrong Answer

Solution code:
import heapq
n, m = [int(i) for i in input().split()]
lrc = []
for _ in range(m):
    l, r, c = [int(i) for i in input().split()]
    lrc.append([l-1, r-1, c])
lrc.sort()
a = []
j = 0
for i in range(n):
    new = []
    while j < m and lrc[j][0] == i:
        new.append(lrc[j])
        j += 1
    if i == 0:
        now = 0
    else:
        while True:
            if len(a) == 0:
                print(-1)
                exit()
            now = heapq.heappop(a)
            if now[1] >= i:
                heapq.heappush(a, now)
                break
        now = now[0]
    for k in new:
        a.append([now + k[2], k[1]])
if len(a) == 0:
    print(-1)
else:
    while True:
        if len(a) == 0:
            print(-1)
            exit()
        now = heapq.heappop(a)
        if now[1] >= n-1:
            heapq.heappush(a, now)
            break
    now = now[0]
    print(now)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
LRCs = []
for i in range(M):
  L, R, C = map(int, input().split())
  L, R = L-1, R-1
  LRCs.append((L, R, C))
LRCs.sort()
#print(LRCs)
Ds = [-1]*N
Ds[0] = 0
for L, R, C in LRCs:
  for i in range(L, N):
    if not Ds[i] < 0:
      L = i
      break
  if Ds[L] < 0:
    continue
  if Ds[R] < 0:
    Ds[R] = Ds[L]+C
  else:
    Ds[R] = min(Ds[R], Ds[L]+C)
r = Ds[-1]
print(r)

Submission status: Wrong Answer

Solution code:
[N,M] = list(map(int,input().split()))

LRC = []
for i in range(M):
    tmp = list(map(int,input().split()))
    LRC.append((tmp[0],tmp[1],tmp[2]))

LRC = sorted(LRC, key=lambda x: (x[0], x[1]))

cnt = [2*10**9]*N
cnt[0] = 0

for i in range(M):
    Lt = LRC[i][0]
    Rt = LRC[i][1]
    Ct = LRC[i][2]
    for j in range(Rt-Lt):
        if cnt[Lt-1]+Ct < cnt[Lt+j]:
            cnt[Lt+j] = cnt[Lt-1]+Ct

if cnt[-1]==2*10**9:
    print(-1)
else:
    print(cnt[-1])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
#第二回全国統一プログラミング王決定戦予選 D

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,m = LI()
lrc = [LI() for _ in range(m)]
h = []
for l,r,c in lrc:
    heappush(h,(c,l,r))

now = 0
ans = 0
for i in range(n):
    tmp = []
    while h:
        c,l,r = heappop(h)
        if l-1 <= now <= r-1:
            ans += c
            now = r-1
            if now == n-1:
                print(ans)
                quit()
            break
        else:
            tmp.append((c,l,r))
    if len(h) == 0:
        print(-1)
        quit()
    for x in tmp:
        heappush(h,x)

Submission status: Wrong Answer

Solution code:
import numpy as np
n, m = map(int, input().split())
lrc = []
for _ in range(m):
    lrc.append(tuple(map(int, input().split())))
lrc.sort()

inf = 10**9
dp = np.ones(n, dtype=int)*inf
dp[0] = 1

for l, r, c in lrc:
    l -= 1
    r -= 1
    if dp[l] == 0:
        break
    d = dp[l] + c if l != 0 else c
    dp[l + 1: r + 1] = np.minimum(dp[l + 1: r + 1], d)

if dp[n - 1] == inf:
    ans = -1
else:
    ans = dp[n - 1]
print(ans)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
A=[float('inf')]*N

f=True
T=[]
for i in range(M):
	a,b,c=map(int,input().split())
	a-=1
	b-=1
	T.append([b,a,c])
T.sort()

A[0]=0
for t in T:
	k = min(A[t[1]:t[0]])
	if k==float('inf'):
		f=False
		break
	if A[t[0]]==float('inf'):
		A[t[0]] = k + t[2]
	else:
		A[t[0]] = min(A[t[0]], k + t[2])

if f and A[-1]!=float('inf'):
	print(A[-1])
else:
	print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    N,M = LI()
    p = [LI() for _ in range(M)]

    p.sort()

    r = [[] for _ in range(N+1)]
    x = []
    d = 0
    j = 0
    for i in range(1,N+1):
        while j < M and p[j][0] == i:
            x.append(d + p[j][2])
            r[p[j][1]].append(d + p[j][2])
            j += 1
        for z in r[i]:
            x.remove(z)
        if i == N: break
        if x == []:
            print(-1)
            return
        else:
            d = min(x)
    print(d)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import heapq

def main():
    n, m = map(int, input().split())
    dics = [{} for _ in range(n)]
    for _ in range(m):
        l, r, c = map(int, input().split())
        ky = r-1
        if ky in dics[l-1]:
            if c < dics[l-1][ky]:
                dics[l-1][ky] = c
        else:
            dics[l-1][ky] = c
    dist = [float("inf")]*n
    dist[0] = 0
    hq = []
    heapq.heappush(hq, [0, 0])
    idx = 0
    while len(hq) > 0:
        v, p = heapq.heappop(hq)
        if p < idx:
            continue
        if p == n-1:
            break
        for i in range(idx, p):
            if len(dics[i]) > 0:
                for ky in dics[i].keys():
                    if ky in dics[p]:
                        if dics[p][ky] > dics[i][ky]:
                            dics[p][ky] = dics[i][ky]
                    else:
                        if p < ky:
                            dics[p][ky] = dics[i][ky]
        idx = p
        for r in dics[p].keys():
            if dist[r] > v + dics[p][r]:
                dist[r] = v + dics[p][r]
                heapq.heappush(hq, [v + dics[p][r], r])
    if dist[n-1] == float("inf"):
        print(-1)
    else:
        print(dist[n-1])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import heapq

def main():
    n, m = map(int, input().split())
    dics = [{} for _ in range(n)]
    rmky = [set() for _ in range(n)]
    for _ in range(m):
        l, r, c = map(int, input().split())
        ky = (l-1, r-1)
        if ky in dics[l-1]:
            if c < dics[l-1][ky]:
                dics[l-1][ky] = c
        else:
            dics[l-1][ky] = c
        if r < n:
            rmky[r].add(ky)
    dist = [float("inf")]*n
    dist[0] = 0
    hq = []
    heapq.heappush(hq, [0, 0])
    idx = 0
    while len(hq) > 0:
        v, p = heapq.heappop(hq)
        if v > dist[p]:
            continue
        if p == n-1:
            break
        for i in range(idx, p):
            if len(dics[i]) > 0:
                dics[p].update(dics[i])
            if len(rmky[i]) > 0:
                for ky in rmky[i]:
                    dics[p].pop(ky)
        idx = p
        for l, r in dics[p].keys():
            if dist[r] > v + dics[p][(l, r)]:
                heapq.heappush(hq, [v + dics[p][(l, r)], r])
            for i in reversed(range(l, r+1)):
                if dist[i] > v + dics[p][(l, r)]:
                    dist[i] = v + dics[p][(l, r)]
                else:
                    break
    if dist[n-1] == float("inf"):
        print(-1)
    else:
        print(dist[n-1])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import heapq

def main():
    n, m = map(int, input().split())
    dics = [{} for _ in range(n)]
    rmky = [set() for _ in range(n)]
    for _ in range(m):
        l, r, c = map(int, input().split())
        ky = (l-1, r-1)
        if ky in dics[l-1]:
            if c < dics[l-1][ky]:
                dics[l-1][ky] = c
        else:
            dics[l-1][ky] = c
        if r < n:
            rmky[r].add(ky)
    for i in range(1, n):
        dics[i].update(dics[i-1])
        for v in rmky[i]:
            dics[i].pop(v)
    dist = [float("inf")]*n
    dist[0] = 0
    hq = []
    heapq.heappush(hq, [0, 0])
    while len(hq) > 0:
        v, p = heapq.heappop(hq)
        if v > dist[p]:
            continue
        if p == n-1:
            break
        for l, r in dics[p].keys():
            if dist[r] > v + dics[p][(l, r)]:
                heapq.heappush(hq, [v + dics[p][(l, r)], r])
            for i in reversed(range(l, r+1)):
                if dist[i] > v + dics[p][(l, r)]:
                    dist[i] = v + dics[p][(l, r)]
                else:
                    break
    if dist[n-1] == float("inf"):
        print(-1)
    else:
        print(dist[n-1])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import heapq

def main():
    n, m = map(int, input().split())
    dic = {}
    for _ in range(m):
        l, r, c = map(int, input().split())
        ky = (l-1, r-1)
        if ky in dic:
            if c < dic[ky]:
                dic[ky] = c
        else:
            dic[ky] = c
    dist = [float("inf")]*n
    dist[0] = 0
    hq = []
    heapq.heappush(hq, [0, 0])
    while len(hq) > 0:
        v, p = heapq.heappop(hq)
        if v > dist[p]:
            continue
        if p == n-1:
            break
        rm = set()
        for l, r in dic.keys():
            u = dic[(l, r)]
            if l <= p <= r:
                rm.add((l, r))
                for i in range(l, r+1):
                    if i == p:
                        continue
                    if dist[i] > dist[p] + u:
                        dist[i] = dist[p] + u
                        heapq.heappush(hq, [dist[i], i])
        for ky in rm:
            dic.pop(ky)
    if dist[n-1] == float("inf"):
        print(-1)
    else:
        print(dist[n-1])

if __name__ == "__main__":
    main()