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,queue,math,copy,itertools,bisect,collections,heapq

class Node:
    def __init__(self,x):
        self.data = x
        self.count = 1
        self.left = None
        self.right = None

def insert(node,x):
    if node is None: return Node(x)
    if node.data == x:
        node.count += 1
    elif x < node.data:
        node.left = insert(node.left,x)
    else:
        node.right = insert(node.right,x)
    return node

def search_min(node):
    if node.left is None: return node.data
    return search_min(node.left)

def delete_min(node):
    if node.left is None:
        if node.count > 1:
            node.count -= 1
        else:
            return node.right
    else:
        node.left = delete_min(node.left)
    return node

def delete(node,x):
    if node:
        if x == node.data:
            if node.count > 1:
                node.count -= 1
            if node.left is None:
                return node.right
            elif node.right is None:
                return node.left
            else:
                node.data = search_min(node.right)
                node.right = delete_min(node.right)
        elif x < node.data:
            node.left = delete(node.left,x)
        else:
            node.right = delete(node.right,x)
    return node


def main():
    sys.setrecursionlimit(10**7)
    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)]
    d = 0
    j = 0
    root = None
    for i in range(1,N):
        update = False
        while j < M and p[j][0] == i:
            root = insert(root,d + p[j][2])
            update = True
            r[p[j][1]].append(d + p[j][2])
            j += 1
        for z in r[i]:
            root = delete(root,z)
            update = True
        if root == None:
            print(-1)
            return
        if update:
            d = search_min(root)
    print(d)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
class Node:
    def __init__(self,x):
        self.data = x
        self.count = 1
        self.left = None
        self.right = None

def insert(node,x):
    if node is None: return Node(x)
    if node.data == x:
        node.count += 1
    elif x < node.data:
        node.left = insert(node.left,x)
    else:
        node.right = insert(node.right,x)
    return node

def search_min(node):
    if node.left is None: return node.data
    return search_min(node.left)

def delete_min(node):
    if node.left is None:
        if node.count > 1:
            node.count -= 1
        else:
            return node.right
    else:
        node.left = delete_min(node.left)
    return node

def delete(node,x):
    if node:
        if x == node.data:
            if node.count > 1:
                node.count -= 1
            if node.left is None:
                return node.right
            elif node.right is None:
                return node.left
            else:
                node.data = search_min(node.right)
                node.right = delete_min(node.right)
        elif x < node.data:
            node.left = delete(node.left,x)
        else:
            node.right = delete(node.right,x)
    return node

Submission status: Wrong Answer

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

class Node:
    def __init__(self,x):
        self.data = x
        self.count = 1
        self.left = None
        self.right = None

def insert(node,x):
    if node is None: return Node(x)
    if node.data == x:
        node.count += 1
    elif x < node.data:
        node.left = insert(node.left,x)
    else:
        node.right = insert(node.right,x)
    return node

def search_min(node):
    if node.left is None: return node.data
    return search_min(node.left)

def delete_min(node):
    if node.left is None: return node.right
    node.left = delete_min(node.left)
    return node

def delete(node,x):
    if node:
        if x == node.data:
            if node.count > 1:
                node.count -= 1
            elif node.left is None:
                return node.right
            elif node.right is None:
                return node.left
            else:
                node.data = search_min(node.right)
                node.right = delete_min(node.right)
        elif x < node.data:
            node.left = delete(node.left,x)
        else:
            node.right = delete(node.right,x)
    return node


def main():
    sys.setrecursionlimit(10**7)
    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)]
    d = 0
    j = 0
    root = None
    for i in range(1,N):
        update = False
        while j < M and p[j][0] == i:
            root = insert(root,d + p[j][2])
            update = True
            r[p[j][1]].append(d + p[j][2])
            j += 1
        for z in r[i]:
            root = delete(root,z)
            update = True
        if root == None:
            print(-1)
            return
        if update:
            d = search_min(root)
    print(d)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
import random
import string
from copy import deepcopy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

def segfunc(x, y):
    return min(x, y)

ide_ele = float('inf')

class SegTree:
    def __init__(self, init_val, segfunc, ide_ele):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

N, M = getNM()
seg = SegTree([float('inf')] * (N + 1), segfunc, ide_ele)
L = [getList() for i in range(M)]
L.sort()
seg.update(0, 0)

# ARC026 C - 蛍光灯と同じ　繋いで繋いでセグ木
# [0, 1, 2, 3, 4, 5]
# seg.query(0, 2): [0, 1]の最小値
# seg.query(2, 2 + 1): [2]の最小値
# seg.update(2, min(vs, opt + c)): 2をmin(vs, opt + c)に更新
for l, r, c in L:
    l -= 1
    r -= 1
    opt = seg.query(l, r)
    vs = seg.query(r, r + 1)
    seg.update(r, min(vs, opt + c))
print(seg.query(N - 1, N))

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush

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

for i in range(N-1):
    adj[i+1].append((i,0))

for i in range(M):
    L, R, C = map(int, input().split())
    adj[L-1].append((R-1,C))

q = [] # 始点のコストとindex
heappush(q,0)
INF = 10**12
d = [INF] * N
d[0] = 0

while len(q) > 0:
    u = heappop(q)
    for v in adj[u]:
        tmp = d[u] + v[1]
        if tmp < d[v[0]]:
            d[v[0]] = tmp
            heappush(q, v[0])

print(d[N-1]) if d[N-1] < INF else print(-1)

Submission status: Wrong Answer

Solution code:
import heapq

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

V = N
G = [[] for _ in range(V)]    #[[to, cost], [], ...]
s = 0

INF = float('inf')

for i in range(V-1):
    G[i+1].append([i, 0])

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

def dijkstra(s):			#始点sからの最短距離のリストを返す
    d = [INF for _ in range(V)]
    d[s] = 0
    que = []
    heapq.heappush(que, (0, s))
    
    while len(que) != 0:
        p = heapq.heappop(que)
        v = p[1]
        if d[v] < p[0]:
            continue
        for i in range(len(G[v])):
            e = G[v][i]
            if d[e[0]] > d[v] + e[1]:
                d[e[0]] = d[v] + e[1]
                heapq.heappush(que, (d[e[0]], e[0]))

    return d

L = dijkstra(s)

print(L[N-1])

Submission status: Wrong Answer

Solution code:
from heapq import *
N,M=map(int,input().split())
G=[[] for i in range(N)]
for i in range(N-1):
  G[i+1].append((i,0))
l,r,c=0,0,0
for i in range(M):
  l,r,c=map(int,input().split())
  G[l-1].append((r-1,c))
D=[0]*N
INF=10**12
def ijk(s):
  global D,INF,G
  for i in range(len(G)):
    D[i]=INF
  D[s]=0
  Q=[]
  heapify(Q)
  heappush(Q,(0,s))
  p,v,e=0,0,0
  while len(Q):
    p=heappop(Q)
    v=p[1]
    if D[v]<p[0]:
      continue
    for i in range(len(G[v])):
      e=G[v][i]
      if D[e[0]]>D[v]+e[1]:
        D[e[0]]=D[v]+e[1]
        heappush(Q,(D[e[0]],e[0]))

ijk(0)
if D[-1]>=INF:
  print(-1)
else:
  print(D[-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])
# 
inf=float('inf')
seen=[inf]*n
seen[0]=0
now=0
from heapq import heappop,heappush
from collections import deque
lrc=deque(lrc)
todo=[now]
while todo:
  v=heappop(todo)
  lst=[]
  while lrc and lrc[0][0]<=v+1:
    lst.append(lrc.popleft())
  for l,r,c in lst:
    if seen[r-1]>seen[v]+c:
      heappush(todo,r-1)
      seen[r-1]=seen[v]+c
if seen[-1]!=inf:
  print(seen[-1])
else:
  print(-1)
#print(seen)

Submission status: Wrong Answer

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
from functools import lru_cache
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7 

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    N, M = read_values()
    T = read_lists(M)
    T.sort()

    S = []
    C = [10 ** 10] * N
    C[0] = 0
    t = 0
    for i in range(N):
        if i != 0 and len(S) == 0:
            print(-1)
            return

        c, r = (0, 0) if len(S) == 0 else S[0]
        while t < M:
            ll, rr, cc = T[t]
            ll -= 1
            rr -= 1
            if ll > i:
                break
                
            C[rr] = min(C[rr], c + cc)
            heapq.heappush(S, (C[rr], rr))
            t += 1

        while S:
            if S[0][1] > i:
                break
            heapq.heappop(S)

    print(C[-1])


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
from functools import lru_cache
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7 

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    N, M = read_values()
    T = read_lists(M)
    T.sort()

    S = []
    C = [10 ** 10] * N
    C[0] = 0
    t = 0
    for i in range(N - 1):
        if i != 0 and len(S) == 0:
            print(-1)
            return

        c, r = (0, 0) if len(S) == 0 else S[0]
        while t < M:
            ll, rr, cc = T[t]
            ll -= 1
            rr -= 1
            if ll > i:
                break
                
            C[rr] = min(C[rr], c + cc)
            heapq.heappush(S, (C[rr], rr))
            t += 1

        while S:
            if S[0][1] > i:
                break
            heapq.heappop(S)

    print(C[-1])


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
from functools import lru_cache
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7 

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    N, M = read_values()
    T = read_lists(M)
    T.sort()

    S = []
    G = set()

    t = 0
    i = 0
    res = 0
    while i < N - 1:
        while t < M and T[t][0] - 1 <= i:
            heapq.heappush(S, (T[t][2], T[t][1] - 1))
            G.add(t)
            t += 1
        
        while S:
            if S[0][1] > i:
                break
            heapq.heappop(S)

        if len(S) == 0:
            print(-1)
            return
        
        res += S[0][0]
        i = S[0][1]

    print(res)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:

Submission status: Wrong Answer

Solution code:
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

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

# (L,R)の組が重複？ 除外する
edge_d_dict = dict()
for i in range(M):
    L, R, C = map(int, input().split())
    if (L, R) in edge_d_dict:
        edge_d_dict[(L, R)] = min(edge_d_dict[(L, R)], C)
    else:
        edge_d_dict[(L, R)] = C
edge_d = np.array([(L, R, C) for (L, R), C in edge_d_dict.items()], dtype=np.int64)

edge_n = np.vstack([np.arange(2, N + 1, dtype=np.int64),
                    np.arange(1, N, dtype=np.int64),
                    np.zeros(N - 1, dtype=np.int64)]).T
edge = np.concatenate([edge_d, edge_d[:, [1, 0, 2]], edge_n]).T

matr = csr_matrix((edge[2], (edge[:2] - 1)), (N, N))
ans = dijkstra(matr, indices=0)[-1]
if ans == np.inf:
    ans = -1
print(int(ans))

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
input = sys.stdin.readline

INF = 10 ** 15

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

LRCs = [tuple(map(int, input().split())) for _ in range(M)]
LRCs.sort(key = lambda t: (t[1], t[0]))

dp = np.full(N, INF)
dp[0] = 0
for L, R, C in LRCs:
    while dp[R-1] > dp[L-1] + C:
        dp[R-1] = dp[L-1] + C
        R -= 1

if dp[-1] == INF:
    print(-1)
else:
    print(dp[-1])

Submission status: Wrong Answer

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import time
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))

N,M=map(int,input().split())
LRC=[list(map(int,input().split())) for i in range(M)]
RLC=[[r,l,c] for l,r,c in LRC]
RLC.sort()
stack=[[0,1,0]]
idle_max=10**18
visited=[idle_max for i in range(N+1)]
visited2=[0 for i in range(N+1)]
while stack:
    m,a,p=heappop(stack)
    if a==N:
        print(m)
        break
    if not visited2[a]:
        visited2[a]=1
        for i in range(p,M):
            r,l,c=RLC[i]
            if l>a:
                break
            elif a<r:
                _m=m+c
                if _m<visited[r]:
                    visited[r]=_m
                    heappush(stack,[_m,r,i+1])
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import time
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()
N,M=map(int,input().split())
LRC=[list(map(int,input().split())) for i in range(M)]
s=1
pres=0
while s!=pres:
    pres=s
    for l,r,c in LRC:
        if l<=s<r:
            s=r
    if s==N:
        break
else:
    print(-1)
    exit()
exit()
stack=[[0,-1]]
idle_max=10**18
visited=[idle_max for i in range(N+1)]
visited2=[0 for i in range(N+1)]
while stack:
    m,a=heappop(stack)
    a=-a
    if a==N:
        print(m)
        break
    if not visited2[a]:
        visited2[a]=1
        for l,r,c in LRC:
            if l<=a<r:
                _m=m+c
                if _m<visited[r]:
                    visited[r]=_m
                    heappush(stack,[_m,-r])
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import time
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()
N,M=map(int,input().split())
LRC=[list(map(int,input().split())) for i in range(M)]
s=1
pres=0
while s!=pres:
    print(s,pres)
    pres=s
    for l,r,c in LRC:
        if l<=s<r:
            s=max(s,r)
    if s==N:
        break
else:
    print(-1)
    exit()
stack=[[0,-1]]
idle_max=10**18
visited=[idle_max for i in range(N+1)]
visited2=[0 for i in range(N+1)]
while stack:
    m,a=heappop(stack)
    a=-a
    if a==N:
        print(m)
        break
    if not visited2[a]:
        visited2[a]=1
        for l,r,c in LRC:
            if l<=a<r:
                _m=m+c
                if _m<visited[r]:
                    visited[r]=_m
                    heappush(stack,[_m,-r])
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import time
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()
N,M=map(int,input().split())
LRC=[list(map(int,input().split())) for i in range(M)]
s=1
pres=0
while s!=pres:
    print(s,pres)
    pres=s
    for l,r,c in LRC:
        if l<=s<r:
            s=r
    if s==N:
        break
else:
    print(-1)
    exit()
stack=[[0,-1]]
idle_max=10**18
visited=[idle_max for i in range(N+1)]
visited2=[0 for i in range(N+1)]
while stack:
    m,a=heappop(stack)
    a=-a
    if a==N:
        print(m)
        break
    if not visited2[a]:
        visited2[a]=1
        for l,r,c in LRC:
            if l<=a<r:
                _m=m+c
                if _m<visited[r]:
                    visited[r]=_m
                    heappush(stack,[_m,-r])
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import time
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))

N,M=map(int,input().split())
LRC=[list(map(int,input().split())) for i in range(M)]
LRC.sort()
stack=[[0,1]]
idle_max=10**18
visited=[idle_max for i in range(N+1)]
visited2=[0 for i in range(N+1)]
while stack:
    m,a=heappop(stack)
    if a==N:
        print(m)
        break
    if not visited2[a]:
        visited2[a]=1

        for i in range(bisect_left(LRC,[a,0,0])-1,M):
            l,r,c=LRC[i]
            if l<=a<r:
                _m=m+c
                if _m<visited[r]:
                    visited[r]=_m
                    heappush(stack,[_m,r])
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

N, M = map(int, input().split())
edge_d = np.array([input().split() for _ in range(M)], dtype=np.int64)
edge_n = np.vstack([np.arange(2, N + 1, dtype=np.int64),
                   np.arange(1, N, dtype=np.int64),
                   np.zeros(N - 1, dtype=np.int64)]).T
edge = np.concatenate([edge_d, edge_d[:, [1, 0, 2]], edge_n]).T

matr = csr_matrix((edge[2], (edge[:2] - 1)), (N, N))
ans = dijkstra(matr, indices=0)[-1]
if ans == np.inf:
    ans = -1
print(int(ans))

Submission status: Wrong Answer

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

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

# 最小値を求めるセグメント木
def init_min(init_min_val):
    #set_val
    for i in range(n):
        seg_min[i+num_min-1]=init_min_val[i]
    #built
    for i in range(num_min-2,-1,-1) :
        seg_min[i]=min(seg_min[2*i+1],seg_min[2*i+2])

def update_min(k,x):
    k += num_min-1
    seg_min[k] = x
    while k:
        k = (k-1)//2
        seg_min[k] = min(seg_min[k*2+1],seg_min[k*2+2])

def query_min(p,q):
    if q<=p:
        return ide_ele_min
    p += num_min-1
    q += num_min-2
    res=ide_ele_min
    while q-p>1:
        if p&1 == 0:
            res = min(res,seg_min[p])
        if q&1 == 1:
            res = min(res,seg_min[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = min(res,seg_min[p])
    else:
        res = min(min(res,seg_min[p]),seg_min[q])
    return res

#####単位元######
ide_ele_min = 10**10

#num_min:n以上の最小の2のべき乗
# num_max =2**(n-1).bit_length()
num_min = 2**(len(str(bin(n-1))) -2)
seg_min=[ide_ele_min]*2*num_min

update_min(0,0)

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

rlc.sort()

for tmp in rlc:
    r,l,c = tmp
    l = l-1
    r = r-1
    update_min( r, min( query_min(l,r) + c , query_min(r,r+1)) )

ans = query_min(n-1,n)
if(ans == ide_ele_min):
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
# shortest path on line

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

graph = {i: {} for i in range(1, n + 1)}

for i in range(1, n):
    graph[i + 1][i] = 0

for _ in range(m):
    l, r, c = map(int, input().split())
    graph[l][r] = c


###############################################################

import heapq

def dijkstra(s, graph, n):
    # ｓからのグラフの最短最短距離をまとめたデータを返す
    dist = [10**20 for i in range(n + 1)]
    dist[s] = 0
    pq = []
    heapq.heapify(pq)
    # 全ての接点を一度優先度付きキューに挿入する
    heapq.heappush(pq, (0, s))
    while pq:
        x = heapq.heappop(pq)
        node, mini_dis = x[1], x[0]
        for point in graph[node].keys():
            w = graph[node][point]
            # nodeからpointに対して伸びる辺の長さ
            newlen = dist[node] + w
            if newlen < dist[point]:
                heapq.heappush(pq, (newlen, point))
                dist[point] = newlen

    return dist
###############################################################


A = dijkstra(1, graph, n)
print(A[n])

Submission status: Wrong Answer

Solution code:
# shortest path on line

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

graph = {i: {} for i in range(1, n + 1)}

for i in range(1, n):
    graph[i + 1][i] = 0

for _ in range(m):
    l, r, c = map(int, input().split())
    graph[l][r] = c


###############################################################

import heapq

def dijkstra(s, graph, n):
    # ｓからのグラフの最短最短距離をまとめたデータを返す
    dist = [10**20 for i in range(n + 1)]
    dist[s] = 0
    pq = []
    heapq.heapify(pq)
    # 全ての接点を一度優先度付きキューに挿入する
    heapq.heappush(pq, (0, s))
    while pq:
        x = heapq.heappop(pq)
        node, mini_dis = x[1], x[0]
        for point in graph[node].keys():
            w = graph[node][point]
            # nodeからpointに対して伸びる辺の長さ
            newlen = dist[node] + w
            if newlen < dist[point]:
                heapq.heappush(pq, (newlen, point))
                dist[point] = newlen

    return dist
###############################################################


a = dijkstra(1, graph, n)
if a[n]>=10**20:
    print(-1)
else:
    print(a[n])

Submission status: Wrong Answer

Solution code:


# shortest path on line

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

graph = {i: {} for i in range(1, n + 1)}

for i in range(1, n):
    graph[i + 1][i] = 0

for _ in range(m):
    l, r, c = map(int, input().split())
    graph[l][r] = c
    graph[r][l] = c

###############################################################

import heapq

def dijkstra(s, graph, n):
    # ｓからのグラフの最短最短距離をまとめたデータを返す
    dist = [10**20 for i in range(n + 1)]
    dist[s] = 0
    pq = []
    heapq.heapify(pq)
    # 全ての接点を一度優先度付きキューに挿入する
    heapq.heappush(pq, (0, s))
    while pq:
        x = heapq.heappop(pq)
        node, mini_dis = x[1], x[0]
        for point in graph[node].keys():
            w = graph[node][point]
            # nodeからpointに対して伸びる辺の長さ
            newlen = dist[node] + w
            if newlen < dist[point]:
                heapq.heappush(pq, (newlen, point))
                dist[point] = newlen

    return dist
###############################################################


a = dijkstra(1, graph, n)
if a[n]>10**19:
    print(-1)
else:
    print(a[n])

Submission status: Wrong Answer

Solution code:


# shortest path on line

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

graph = {i: {} for i in range(1, n + 1)}

for i in range(1, n):
    graph[i + 1][i] = 0

for _ in range(m):
    l, r, c = map(int, input().split())
    graph[l][r] = c
    graph[r][l] = c

###############################################################

import heapq

def dijkstra(s, graph, n):
    # ｓからのグラフの最短最短距離をまとめたデータを返す
    dist = [10**20 for i in range(n + 1)]
    dist[s] = 0
    pq = []
    heapq.heapify(pq)
    # 全ての接点を一度優先度付きキューに挿入する
    heapq.heappush(pq, (0, s))
    while pq:
        x = heapq.heappop(pq)
        node, mini_dis = x[1], x[0]
        for point in graph[node].keys():
            w = graph[node][point]
            # nodeからpointに対して伸びる辺の長さ
            newlen = dist[node] + w
            if newlen < dist[point]:
                heapq.heappush(pq, (newlen, point))
                dist[point] = newlen

    return dist
###############################################################


a = dijkstra(1, graph, n)
if a[n]>10**20:
    print(-1)
else:
    print(a[n])

Submission status: Wrong Answer

Solution code:


# shortest path on line

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

graph = {i: {} for i in range(1, n + 1)}

for i in range(1, n):
    graph[i + 1][i] = 0

for _ in range(m):
    l, r, c = map(int, input().split())
    graph[l][r] = c
    graph[r][l] = c

###############################################################

import heapq

def dijkstra(s, graph, n):
    # ｓからのグラフの最短最短距離をまとめたデータを返す
    dist = [10**20 for i in range(n + 1)]
    dist[s] = 0
    pq = []
    heapq.heapify(pq)
    # 全ての接点を一度優先度付きキューに挿入する
    heapq.heappush(pq, (0, s))
    while pq:
        x = heapq.heappop(pq)
        node, mini_dis = x[1], x[0]
        for point in graph[node].keys():
            w = graph[node][point]
            # nodeからpointに対して伸びる辺の長さ
            newlen = dist[node] + w
            if newlen < dist[point]:
                heapq.heappush(pq, (newlen, point))
                dist[point] = newlen

    return dist
###############################################################


a = dijkstra(1, graph, n)
if a[n]>10**10:
    print(-1)
else:
    print(a[n])

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
LRC=sorted([list(map(int,input().split())) for i in range(M)],key=lambda x:(x[1],x[0]))
class rmq:
    def __init__(self,N):
        self.N0=2**(N-1).bit_length()
        self.INF=2**31-1
        self.data=[self.INF]*(2*self.N0)
        self.lazy=[None]*(2*self.N0)
    def gindex(self,l, r):
        L = l + self.N0; R = r + self.N0
        lm = (L // (L & -L)) >> 1
        rm = (R // (R & -R)) >> 1
        while L < R:
            if R <= rm:
                yield R
            if L <= lm:
                yield L
            L >>= 1; R >>= 1
        while L:
            yield L
            L >>= 1
    def propagates(self,*ids):
        for i in reversed(ids):
            v = self.lazy[i-1]
            if v is None:
                continue
            self.lazy[2*i-1] = self.data[2*i-1] = self.lazy[2*i] = self.data[2*i] = v
            self.lazy[i-1] = None
    def update(self,l, r, x):
        *ids, = self.gindex(l, r)
        self.propagates(*ids)
        L = self.N0 + l; R = self.N0 + r
        while L < R:
            if R & 1:
                R -= 1
                self.lazy[R-1] = self.data[R-1] = x
            if L & 1:
                self.lazy[L-1] = self.data[L-1] = x
                L += 1
            L >>= 1; R >>= 1
        for i in ids:
            self.data[i-1] = min(self.data[2*i-1], self.data[2*i])
    def rmin(self,l, r):
        self.propagates(*self.gindex(l, r))
        L = self.N0 + l; R = self.N0 + r
        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
d=rmq(N)
d.update(0,1,0)
for l,r,c in LRC:
    d.update(r-1,r,min(d.data[d.N0+r-2],d.rmin(l-1,r-1)+c))
a=d.rmin(N-1,N)
print(a if a<d.INF else -1)