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:
import sys
def input():
    return sys.stdin.readline()[:-1]
import bisect
N,M=map(int,input().split())
S = [list(map(int, input().split())) for i in range(M)]
from operator import itemgetter
S.sort(key=itemgetter(1))
x=[0]
y=[0]
for i in S:
    t=bisect.bisect_left(x,i[0]-1)
    if t!=len(x):
        x.append(i[1]-1)
        y.append(y[t]+i[2])
    else:
        print(-1)
        break
else:
    print(y[bisect.bisect_left(x,N-1)])

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
N, M = list(map(int, input().split()))

RCL = []
for _ in range(M):
    L, R, C = list(map(int, input().split()))
    L -= 1
    R -= 1
    RCL.append((-R, C, L))
RCL.sort()

# if RCL[0][0] != -(N-1):
#    print(-1)
#    sys.exit(0)


D = deque()

i = N-1

for rcl in RCL:
    r, c, l = rcl
    r = -r
    if r == N-1:
        D.append((c, l))
    else:
        nex = deque()
        while D:
            d = D.popleft()
            if l <= d[1] <= r:
                nex.append(d)
                nex.append((d[0] + c, l))

        D = nex

ans = 10**16

while D:
    d = D.popleft()
    if d[1] == 0 and ans > d[0]:
        ans = d[0]

if ans == 10**16:
    print(-1)
    sys.exit(0)
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
lrc = []
for i in range(m):
    lrc.append(list(map(int, input().split())))
lrc.sort(key = lambda x: (x[1], x[2]))
lrc.sort()
dis = [[1, 0]]
num = 0
flag = True
for i in range(m):
    l = lrc[i][0]
    r = lrc[i][1]
    c = lrc[i][2]
    while dis[num][0] < l:
        num += 1
        if num == len(dis):
            flag = False
            break
    if flag == False:
        break
    dis.append([r, dis[num][1] + c])
    dis.sort()
if flag == False:
    print(-1)
else:
    num = -1
    dis2 = []
    while dis[num][0] == n:
        dis2.append(dis[num][1])
        num -= 1
    print(min(dis2))

Submission status: Wrong Answer

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

graph = [[] for _ in range(N)]

LRC.sort(key=lambda x: x[1])

for i, (Li, Ri, Ci) in enumerate(LRC):
    graph[Li - 1].append((Ri, Ci))

for i, (Li, Ri, Ci) in enumerate(LRC):
    for idx in range(Ri - Li):
        if len(graph[(Ri - idx - 1) - 1]) > 0:
            if graph[(Ri - idx - 1) - 1][-1][0] > Ri:
                graph[Ri - 1].append(((Ri - idx - 1), 0))

# for i in range(N):
#     print("#", graph[i])
            
import heapq

inf = 10 ** 18
d = [inf] * N

q = [(0, 1)] # cost, pos
while len(q) > 0:
    cost, src = heapq.heappop(q)
    for dst, c_dst in graph[src - 1]:
        if cost + c_dst < d[dst - 1]:
            d[dst - 1] = cost + c_dst
            heapq.heappush(q, (cost + c_dst, dst))

if d[N - 1] == inf:
    print(-1)
else:
    print(d[N - 1])

Submission status: Wrong Answer

Solution code:
n, m = list(map(int, input().split()))
inf = 10 ** 10
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 numpy as np

N, M = map(int, input().split())
LRC = [list(map(int, input().split())) for _ in range(M)]
INF = 10 ** 10
LRC.sort(key=lambda x: x[2], reverse=True)
LRC.sort()
dp = np.array([INF] * (N+1)) # dp[0]は使わない
visited = 1
dp[1] = 0
for l, r, c in LRC:
    if l > visited:
        print(-1)
        exit()
    if r > visited:
        visited = r
    x = dp[l:r+1].min() + c
    dp[r] = min(dp[r], x)
if dp[N] == INF:
    print(-1)
else:
    print(dp[N])

Submission status: Wrong Answer

Solution code:
import numpy as np
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 = map(int, input().split())
ro = [[float("inf") for i in range(n)] for i in range(n)]
lis = np.array([[int(i) for i in input().split(" ")] for i in range(m)])
lis = lis[lis[:,0].argsort(), :]
used = [[False for i in range(n)] for i in range(n)]
for i in lis:
    for j in range(i[0]-1, i[1]-1):
        for k in range(i[0], i[1]):
            if used[j][k] == False:
                ro[j][k] = i[2]
                ro[k][j] = i[2]
                used[j][k] = True
cost = ro         
te = dijkstra(0,n,n-1,cost)
if te[-1] == float("inf"):
    print(-1)
else:
    print(te[-1])

Submission status: Wrong Answer

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

query = list()
for i in range(M):
  query.append(tuple(map(int,input().split())))
  
query.sort()
dp = np.zeros(N,dtype=np.uint)
dp[1:] = 10**10
for l,r,c in query:
  dp[l-1:r] = np.minimum(dp[l-1]+c, dp[l-1:r])

print(int(dp[-1]) if dp[-1] != np.inf else -1)

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[1], x[0], x[2]))

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

t=1
p=0
while p<M:
    L=LRC[p][0]
    R=LRC[p][1]
    C=LRC[p][2]
    if t >=R:
        t = R-1
    while t < R:
        cnt[t]=min(cnt[L-1]+C,cnt[t])
        t+=1
        print(cnt)
    p+=1


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

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split(' '))

tree_list = []
for _ in range(M):
    L,R,C = map(int,input().split(' '))
    tree_list.append([R-1,L-1,C])
    '''
    if (R-1) in tree_list[L-1].keys():
        tree_list[L-1][R-1] = min(tree_list[L-1][R-1],C)
    else:
        tree_list[L-1][R-1] = C
    '''
tree_list.sort(reverse=True)
dp = [1000000000] * N
dp[N-1] = 0
for path in tree_list:
    if dp[path[1]] > dp[path[0]] + path[2]:
        for i in range(path[1],path[0]):
            dp[i] = min(dp[path[0]] + path[2],dp[i]) 
print(dp[0])

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop

n, m = map(int, input().split())
edge = [list(map(int, input().split())) for _ in range(m)]
edge.sort(key=lambda x: (x[1], x[0]))

q = [(1, 0)]
for l, r, c in edge:
    # print((l, r, c), q)

    cand = float("inf")
    while q:
        y, z = heappop(q)
        if y >= l:
            heappush(q, (y, z))
            break

    for y, z in q:
        if y < r:
            cand = min(cand, z)
        else:
            heappush(q, (y, z))
            break

    if cand != float("inf"):
        heappush(q, (r, cand + c))

# print(q)

ans = -1
for y, z in q:
    if y == n:
        if ans == -1:
            ans = z
        else:
            ans = min(ans, z)

print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().strip().split())
LRC = [list(map(int, input().strip().split())) for i in range(M)]
LRC.sort()
LRC = sorted(LRC, key=lambda h: (h[0], h[2]))
#print(LRC)

INF = -1
dp = [INF] * M
dp[0] = LRC[0][2]
for i in range(M):
    for j in range(i+1, M):
        if LRC[i][1] < LRC[j][0]:
            break
        if dp[j] == INF:
            dp[j] = dp[i] + LRC[j][2]
        else:
            dp[j] = min(dp[j], dp[i] + LRC[j][2])
#print(dp)
sol = -1
for i in range(M):
    if LRC[i][1] == N:
        if sol == -1:
            sol = dp[i]
        elif sol > dp[i]:
            sol = dp[i]
#print(dp)
print(sol)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
LRC = [list(map(int, input().split())) for _ in range(M)]
INF = 10 ** 10
LRC.sort(key=lambda x: x[2], reverse=True)
LRC.sort()
dp = [INF] * (N+1) # dp[0]は使わない
visited = 1
dp[1] = 0
for l, r, c in LRC:
    if l > visited:
        print(-1)
        exit()
    if r > visited:
        visited = r
    x = min(dp[l:r+1]) + c
    dp[r] = min(dp[r], x)
if dp[N] == INF:
    print(-1)
else:
    print(dp[N])

Submission status: Wrong Answer

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

query = list()
for i in range(M):
  query.append(tuple(map(int,input().split())))
  
query.sort()
dp = np.zeros(N,dtype=np.uint)
dp[1:] = 10**6
for l,r,c in query:
  dp[l-1:r] = np.minimum(dp[l-1]+c, dp[l-1:r])

print(int(dp[-1]) if dp[-1] != np.inf else -1)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
LRC = [list(map(int, input().split())) for _ in range(M)]
INF = 10 ** 10
LRC.sort(key=lambda x: x[2], reverse=True)
LRC.sort()
dp = [INF] * (N+1) # dp[0]は使わない
visited = 1
dp[1] = 0
for l, r, c in LRC:
    if l > visited:
        print(-1)
        exit()
    if r > visited:
        visited = r
    x = dp[l] + c
    dp[r] = min(dp[r], x)
if dp[N] == INF:
    print(-1)
else:
    print(dp[N])

Submission status: Wrong Answer

Solution code:
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_r in range(left+1, right):
        # print(tmp[2], now_l, now_r)
        dp[now_r] = min(min(dp[left:now_r]) + tmp[2], dp[now_r])
if dp[N-1]==INF:
    print(-1)
else:
    print(dp[N-1])

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
import heapq
n,m=map(int,input().split())

D=[0]
P=[]
ans=float("inf")

for i in range(m):
  l,r,c=map(int,input().split())
  P.append((l,r,c))
P.sort(key=lambda x:x[0])
heapq.heappush(D,1*10**15+0)
for l,r,c in P:
  while D:
    ld=heapq.heappop(D)
    ll=ld//(10**15)
    dd=ld%(10**15)
    if ll<l:
      continue
    else:
      break
  if ll>=l:
    heapq.heappush(D,r*10**15+dd+c)
  heapq.heappush(D,ll*10**15+dd)
while D:
  ld=heapq.heappop(D)
  ll=ld//(10**15)
  dd=ld%(10**15)
  if ll==n:
    ans=min(ans,dd)
print(-1 if ans==float("inf") else ans)

Submission status: Wrong Answer

Solution code:
import collections
import heapq


class Dijkstra:
    def __init__(self):
        self.e = collections.defaultdict(list)

    def add(self, u, v, d):
        self.e[u].append([v, d])
        self.e[v].append([u, d])

    def delete(self, u, v):
        self.e[u] = [_ for _ in self.e[u] if _[0] != v]
        self.e[v] = [_ for _ in self.e[v] if _[0] != u]

    def search(self, s):
        """
        :param s: 始点
        :return: 始点から各点までの最短経路
        """
        d = collections.defaultdict(lambda: float('inf'))
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True

            for uv, ud in self.e[u]:
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    heapq.heappush(q, (vd, uv))

        return d


N, M = map(int,input().split())
graph = Dijkstra()
for i in range(M):
    L, R, C = map(int, input().split())
    for j in range(L-1, R-1):
        for k in range(j+1, R):
            graph.add(j, k, C)
      
ans = graph.search(0)

if ans[N-1] > 10*15:
    print(-1)
else:
    print(ans[N-1])

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
import heapq
n,m=map(int,input().split())

D=[0]
P=[]
ans=float("inf")

for i in range(m):
  l,r,c=map(int,input().split())
  P.append((l,r,c))
P.sort(key=lambda x:x[0])
heapq.heappush(D,1*10**15+0)
for l,r,c in P:
  while D:
    ld=heapq.heappop(D)
    ll=ld//(10**15)
    dd=ld%(10**15)
    if ll<l:
      continue
    else:
      break
  if ll>=l:
    heapq.heappush(D,r*10**15+dd+c)
  heapq.heappush(D,ll*10**15+dd)
print(D)
while D:
  ld=heapq.heappop(D)
  ll=ld//(10**15)
  dd=ld%(10**15)
  if ll==n:
    ans=min(ans,dd)
print(-1 if ans==float("inf") else ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
LRC = [list(map(int, input().split())) for _ in range(M)]
INF = 10 ** 10
LRC.sort(key=lambda x: x[2], reverse=True)
LRC.sort()
dp = [INF] * (N+1) # dp[0]は使わない
visited = set([1])
dp[1] = 0
for l, r, c in LRC:
    if l not in visited:
        print(-1)
        exit()
    for i in range(l, r+1):
        visited.add(i)
        dp[i] = min(dp[i], dp[l]+c)
if dp[N] == INF:
    print(-1)
else:
    print(dp[N])

Submission status: Wrong Answer

Solution code:
def main():    
    n,m = map(int,input().split())
    lrc = [tuple(map(int,input().split())) for _ in range(m)]
    lcr = sorted([(i[0]-1,i[2],i[1]-1) for i in lrc],reverse=True)
    INF = float('inf')
    dist = [INF]*n
    check = [False]*n
    check[0] = True
    dist[0] = 0
    mx_v = 0
    enable = True
    while lcr:
        route = lcr.pop(-1)
        mn = route[0]
        mx = route[-1]
        if not check[mn]:
            enable = False
            break
        else:
            d = route[1]+dist[mn]
            for i in range(mx,mn,-1):
                if dist[i] >= d:
                    dist[i] = d
                    check[i] = True
                else:
                    break
    if enable:
        print(dist[-1])
    else:
        print(-1)
    
if __name__ == '__main__':
    main()

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[1], x[2], x[0]))

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

t=1
p=0
while p<M:
    L=LRC[p][0]
    R=LRC[p][1]
    C=LRC[p][2]
    if t >=R:
        t = R-1
    while t < R:
        cnt[t]=min(cnt[L-1]+C,cnt[t])
        t+=1
    p+=1


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

Submission status: Wrong Answer

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

path = [([int(1e9 + 1)] * N) for i in range(N)]
DP = [0] * N

for _ in range(M):
    L, R, C = map(int, input().split())
    if path[L-1][R-1] > C:
        path[L-1][R-1] = C

for i in range(N-1):
    for j in range(N-1, i+1, -1):
        if path[i][j] < path[i][j-1]:
            path[i][j-1] = path[i][j]
        if path[i][j] < path[i+1][j]:
            path[i+1][j] = path[i][j]

DP[1] = path[0][1]
for i in range(2, N):
    l = [DP[j] + path[j][i] for j in range(1, i) if path[j][i] != int(1e9 + 1)]
    if len(l) == 0:
        print(-1)
        exit()    
    m = min(l)
    DP[i] = min(path[0][i], m)

print(DP[-1])

Submission status: Wrong Answer

Solution code:

def main():
    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 = [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(-1)
        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:
[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[1], x[2], x[0]))

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

t=1
p=0
while p<M:
    L=LRC[p][0]
    R=LRC[p][1]
    C=LRC[p][2]
    if t >=R:
        t = R-1
    while t < R:
        cnt[t]=cnt[L-1]+C
        t+=1
    p+=1


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

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
lrc_list = []
for _ in range(M):
    lrc_list.append(tuple(map(int, input().split())))
lrc_list.sort()
way = [float('inf')] * N
way[0] = 0
print(lrc_list)
for lrc in lrc_list:
    for i in range(lrc[0], lrc[1]):
        way[i] = min(way[i], way[lrc[0] - 1] + lrc[2])

if way[N - 1] != float('inf'):
    print(way[N - 1])
else:
    print(-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())))
import heapq
heapq.heapify(lrc)
arrive = [[1,0]]
heapq.heapify(arrive)
#print(arrive)
while True:
  if arrive == []:
    print(-1)
    break
  point,dis = heapq.heappop(arrive)
  if point == n:
    print(dis)
    break
  if arrive != []:
    if dis >= arrive[0][1]:
      continue
  while True:
    if lrc == []:
      break
    if lrc[0][0] <= point:
      l,r,c = heapq.heappop(lrc)
      if r > point:
        heapq.heappush(arrive,[r,dis+c])
    else:
      break

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:
N, M = map(int, input().split())
LRC = [list(map(int, input().split())) for _ in range(M)]
INF = 10 ** 10
graph = [[INF] * (N+1) for _ in range(N+1)]
for i in range(N+1):
    graph[i][i] = 0
LRC.sort(key=lambda x: x[2], reverse=True)
LRC.sort()
dp = [INF] * (N+1) # dp[0]は使わない
visited = 1
dp[1] = 0
for l, r, c in LRC:
    if l > visited:
        print(-1)
        exit()
    visited = r
    x = dp[l] + c
    for i in range(l, r+1):
        dp[i] = min(dp[i], x)
if dp[N] == INF:
    print(-1)
else:
    print(dp[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,m=map(int,input().split())#n:頂点数　w:辺の数

edge = [[] for i in range(n)] #edge[i] : iから出る道の[重み,行先]の配列

l=[list(map(int,input().split())) for i in range(m)]
for i in range(m):
    x,y,z =l[i][0],l[i][1],l[i][2]
    x-=1
    y-=1
    edge[x].append([z,y])
    edge[y].append([z,x]) 
#print(edge)
#print(dijkstra_heap(0))
a=dijkstra_heap(0)
for i in range(n-2,-1,-1):
    if a[i]>a[i+1]:
        a[i]=a[i+1]
#print(a)
l=sorted(l, key=lambda x: x[1])
l=l[::-1]
for i in range(m):
    if l[i][1]==n:
        a[-1]=min(a[-1],a[l[i][0]-1]+l[i][2])
    else:
        break
if a[-1]==float('inf'):
    print(-1)
else:
    print(a[-1])

Submission status: Wrong Answer

Solution code:
import bisect
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
Rs = [0]
for L, R, C in LRCs:
  i = bisect.bisect_left(Rs, L)
  if i == len(Rs):
    continue
  L = Rs[i]
  #print(L, Rs)
  if Ds[R] < 0:
    Ds[R] = Ds[L]+C
  else:
    Ds[R] = min(Ds[R], Ds[L]+C)
  bisect.insort_left(Rs, R)
r = Ds[-1]
print(r)

Submission status: Wrong Answer

Solution code:
def main():    
    n,m = map(int,input().split())
    lrc = [tuple(map(int,input().split())) for _ in range(m)]
    lcr = sorted([(i[0]-1,i[2],i[1]-1) for i in lrc],reverse=True)
    INF = float('inf')
    dist = [INF]*n
    dist[0] = 0
    mx_v = 0
    enable = True
    while lcr:
        route = lcr.pop(-1)
        mn = route[0]
        mx = route[-1]
        if mn > mx_v:
            enable = False
            break
        else:
            d = route[1]+dist[mn]
            for i in range(mx,mn,-1):
                if dist[i] >= d:
                    dist[i] = d
                else:
                    break
        mx_v = max([mx,mx_v])
    if enable:
        print(dist[-1])
    else:
        print(-1)
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N,M=[int(s) for s in input().split()]
ls=[[int(s) for s in input().split()] for i in range(M)]
ls.sort()
#print(ls)
dp=[10**14]*(N+1)
dp[0]=0
dp[1]=0
for e in ls:
  for i in range(e[0]+1,e[1]+1):
    dp[i]=min([dp[i],dp[e[0]]+e[2]])
#  print(dp)
print(dp[N])

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
lrc = []
for _ in range(m):
  lrc.append(list(map(int,input().split())))
import heapq
heapq.heapify(lrc)
arrive = [[1,0]]
heapq.heapify(arrive)
#print(arrive)
try:
  while True:
    point,dis = heapq.heappop(arrive)
    if point == n:
      print(dis)
      break
    if arrive != []:
      if dis >= arrive[0][1]:
        continue
    while True:
      if lrc == []:
        break
      if lrc[0][0] <= point:
        l,r,c = heapq.heappop(lrc)
        if r > point:
          heapq.heappush(arrive,[r,dis+c])
      else:
        break
except:
  print(-1)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())

edge=[]
v=[]
rss=[0]
inf=float('inf')

for i in range(m):
    l,r,c=map(int,input().split())
    edge.append((l-1,r-1,c))
    #rs.append(l-1)
    rss.append(r-1)

edge.sort()
rss.sort()
rs=[rss[0]]
for i in range(1,m+1):
    #print(rs)
    if rs[-1]!=rss[i]:
        rs.append(rss[i])
dp=[inf]*(len(rs))
dp[0]=0

import bisect
for i in range(m):
    l,r,c=edge[i]
    idx=bisect.bisect_left(rs,r)
    idx2=bisect.bisect_left(rs,l)
    dp[idx]=min(dp[idx],dp[idx2]+c)
print(dp[-1] if dp[-1]!=inf else -1)

Submission status: Wrong Answer

Solution code:
import collections
import heapq


class Dijkstra:
    def __init__(self):
        self.e = collections.defaultdict(list)

    def add(self, u, v, d):
        self.e[u].append([v, d])
        self.e[v].append([u, d])

    def delete(self, u, v):
        self.e[u] = [_ for _ in self.e[u] if _[0] != v]
        self.e[v] = [_ for _ in self.e[v] if _[0] != u]

    def search(self, s):
        """
        :param s: 始点
        :return: 始点から各点までの最短経路
        """
        d = collections.defaultdict(lambda: float('inf'))
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True

            for uv, ud in self.e[u]:
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    heapq.heappush(q, (vd, uv))

        return d


N, M = map(int,input().split())
graph = Dijkstra()
for i in range(M):
    L, R, C = map(int, input().split())
    for j in range(L-1, R-1):
        for k in range(j+1, R):
            graph.add(j, k, C)
      
ans = graph.search(0)

print(ans[N-1])

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
LRC = [list(map(int, input().split())) for i in range(M)]
LRC = sorted(LRC)
#print(LRC)
A = [10**16] * N
A[0] = 0

for i in range(M):
  L, R, C = LRC[i][0] - 1, LRC[i][1] - 1, LRC[i][2]
  if C < A[R] - A[L]:
    x = (R + L) //2
    if C < A[x] - A[L]:
      for j in range(x, R+1):
        A[j] = min(A[j], A[L] + C)
    else:
      for j in range(L+1, R+1):
        A[j] = min(A[j], A[L] + C)

#出力
ans = A[-1]
if ans > 10 ** 15:
  ans = -1
  
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect,insort
inf=float("inf")
n,m=map(int,input().split())
lrc=[list(map(int,input().split())) for i in range(m)]
lrc.sort()
data=[[1,0]]
h=1
for u in lrc:
    l,r,c=u
    a=bisect(data,[l])
    if a==h:
        print(-1)
        break
    b=data[a][1]
    insort(data,[r,b+c])
    h+=1
else:
    ans=inf
    for u in data:
        if u[0]==n:
            ans=min(ans,u[1])
    if ans==inf:
        print(-1)
    else:
        print(ans)

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
for l, r, c in LRC:
    dp[l:r+1] = np.minimum(dp[l:r+1], dp[l] + c)

if dp[-1] < 10**6:
    print(dp[-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])
rr=1
ll=10**5+1
for l,r,c in lrc:
    if rr<l:
        print(-1)
        exit()
    ll=min(l,ll)
    rr=max(rr,r)

if not (ll==1 and rr==n):
    print(-1)
    exit()

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)

import bisect

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

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

Submission status: Wrong Answer

Solution code:
import sys
import re
import heapq

# グラフの初期化
def initialize_graph():
    graph = {}
    n, edge_list = read_file()
    for edge_inf in edge_list:
        node1 = edge_inf[0]
        node2 = edge_inf[1]
        cost = edge_inf[2]
        # ノードの設定と無向エッジのコスト設定
        graph = set_new_node(graph, node1, node2)
        graph[node1][node2] = cost
        graph[node2][node1] = cost
    return n, graph

def set_new_node(graph, node1, node2):
    if not node1 in graph.keys():
        graph[node1] = {}
    if not node2 in graph.keys():
        graph[node2] = {}
    return graph

# ダイクストラ法によって最短経路問題を解く
def solve_by_dijkstra(graph, n):
    # ノード毎のSTARTからの最小コスト
    min_dist_dict = {}
    # ノードに最小コストで辿り着く場合の直前のノード
    prev_node_dict = {}
    q = []
    heapq.heappush(q, (0, 1))
    
    prev_node = ''

    while True:
        # 確定したノードから遷移可能なノードのうち
        # 最小のコストと遷移先ノードをmin_dist_dictとprev_node_dictに設定
        if q == []:
            return None, None
        dist, node = heapq.heappop(q)
        min_dist_dict[node] = dist
        prev_node_dict[node] = prev_node
        # もしGOALノードの最小コストが確定したらループを抜ける
        if node == n: 
            return min_dist_dict, prev_node_dict
        prev_node = node
        # 確定したノードから遷移可能なノードについて
        # コストを計算し，キュー(q)に追加する
        culc_min_dist_and_put(graph, q, node, min_dist_dict, prev_node_dict)
    return None, None

def culc_min_dist_and_put(graph, q, departure_node, min_dist_dict, prev_node_dict):
    # 直前に確定したノードから遷移可能なすべてのノードについて繰り返し
    for arrival_node in graph[departure_node].keys():
        # 遷移可能なノードについて，直前に確定したノードから遷移した場合のコストを計算
        tmp_d = min_dist_dict[departure_node] + graph[departure_node][arrival_node]
        # 過去に遷移先ノードの最小コストを計算済みかどうか
        if arrival_node in min_dist_dict.keys():
            # 過去に計算していたSTARTからの最小コストより直前に確定したノードから遷移した場合の
            # コストが小さかった場合，最小コストを更新
            if tmp_d < min_dist_dict[arrival_node]:
                min_dist_dict[arrival_node] = tmp_d
                heapq.heappush(q, (min_dist_dict[arrival_node], arrival_node))
        else:
            min_dist_dict[arrival_node] = tmp_d
            heapq.heappush(q, (min_dist_dict[arrival_node], arrival_node))

def main():
    n, graph = initialize_graph()
    out = -1
    #jmin_dist_dict, prev_node_dict = solve_by_dijkstra(graph, n)
    #jif min_dist_dict is not None:
    #j    out = min_dist_dict[n]
    #jelse:
    #j    out = -1
    print(out)

def read_file():
    #file_name = 'edge_inf.csv'
    #edge_list = []
    #with open(file_name,'r',encoding='utf-8') as fin:
    #    for line in fin.readlines():
    #        edge_list.append(re.sub(r'[\r\n]','',line))

    M = 10 ** 10
    n, m = map(int, input().split(" "))
    ws = [[M for _ in range(n+1)] for _ in range(n+1)]

    pairs = []
    for _ in range(m):
        l, r, w = map(int, input().split(" "))
        #print("i", _, l, r, w)
        for s in range(l, r+1):
            for t in range(s+1, r+1):
                #print((s, t))
                ws[s][t] = min(ws[s][t], w)
                pairs.append((s, t))

    set_pairs = set(pairs)
    #print(pairs, set_pairs)
    edge_list = []
    for s, t in set_pairs:
        w = ws[s][t]
        edge_list.append([s, t, w])

    #print("edge_list", edge_list)
    return n, edge_list


if __name__ == '__main__':
    main()
    sys.exit(0)

Submission status: Wrong Answer

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

inf = 10**18
dp = np.ones(n+1, dtype=np.int32)*inf
dp[n] = 0

for r, l, c in lrc:
    for i in range(r, 0, -1):
        if dp[i] != inf:
            break

    dp[l] = min(dp[l], dp[i] + c)


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