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: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, m = LI()
G = [[] for _ in range(n)]
for _ in range(m):
    l, r, c = LI()
    G[l - 1] += [(r - 1, c)]


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


def dijkstra(G, s=0):
    hq = [(0, s)]
    dist = [INF] * n
    dist[s] = 0
    checked = [0] * n
    while hq:
        min_dist, u = heappop(hq)
        if checked[u]:
            continue
        checked[u] = 1
        for v, c in G[u]:
            if checked[v]:
                continue
            elif dist[u] + c < dist[v]:
                dist[v] = dist[u] + c
                heappush(hq, (dist[u] + c, v))
    return dist


ans = dijkstra(G)[-1]
if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
class lheapq:
    def __init__(self, p):
        self.l = []
        if p:
            for sp in p:
                self.heappush(sp)

    def heappush(self, a):
        n = len(self.l)
        self.l.append(a)
        t = n
        while t != 0:
            if self.l[t][1] < self.l[(t - 1) // 2][1]:
                self.l[t], self.l[(t - 1) // 2] = self.l[(t - 1) // 2], self.l[t]
                t = (t - 1) // 2
            else:
                break

    def heappop(self):
        n = len(self.l)
        if n == 0:
            return [-1, 0]
        if n == 1:
            return self.l.pop()
        ret = self.l[0]
        self.l[0] = self.l.pop()
        n -= 1
        t = 0
        while t < n:
            child1 = t * 2 + 1
            child2 = t * 2 + 2
            if child1 >= n:
                break
            elif child2 >= n:
                if self.l[t][1] > self.l[child1][1]:
                    self.l[t], self.l[child1] = self.l[child1], self.l[t]
                    t = child1
                else:
                    break
            else:
                if self.l[child2][1] < self.l[child1][1]:
                    child1, child2 = child2, child1
                if self.l[t][1] > self.l[child1][1]:
                    self.l[t], self.l[child1] = self.l[child1], self.l[t]
                    t = child1
                elif self.l[t][1] > self.l[child2][1]:
                    self.l[t], self.l[child2] = self.l[child2], self.l[t]
                    t = child2
                else:
                    break
        return ret

    def isnotblank(self):
        if self.l:
            return True
        else:
            return False


def dijkstra(g, n):
    # グラフgの点0から点n-1までの最短距離を求める。
    # グラフは隣接行列で[[[目的地、辺の重み],[目的地、辺の重み]],[],...]

    f = [-1 for _ in range(n)]

    s = 0
    f[0] = 0
    q = lheapq(g[0])
    while True:
        kakutei = q.heappop()
        if kakutei[0] == -1:
            return f
        while f[kakutei[0]] != -1:
            kakutei = q.heappop()
            if kakutei[0] == -1:
                return f
        s = kakutei[0]
        f[s] = kakutei[1]
        for sg, sl in g[s]:
            if f[sg] == -1:
                q.heappush([sg, sl + f[s]])


n, m = map(int, input().split())
g = [[] for _ in range(n)]
for i in range(n - 1):
    g[i + 1].append([i, 0])
for i in range(m):
    a, b, l = map(int, input().split())
    g[a - 1].append([b - 1, l])

print(dijkstra(g, n)[-1])

Submission status: Accepted

Solution code:
from heapq import heappush,heappop
n,m=map(int,input().split())
a=[[[i-1,0]]for i in range(n+1)]
a[0]=[]
for i in range(m):
    l,r,c=map(int,input().split())
    a[l].append([r,c])
q=[float("INF")]*(n+1)
q[1]=0
c=[]
heappush(c,[0,1])
while c:
    s,t=heappop(c)
    if t==n:
        print(s)
        break
    for i,j in a[t]:
        if q[i]>s+j:
            q[i]=s+j
            heappush(c,[s+j,i])
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(pow(10, 6))

from heapq import heappop, heappush


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

    d = [float("inf") for _ in range(n)]
    d[0] = 0
    h = [(0, 0)]
    while len(h) > 0:
        tmpd, tmpi = heappop(h)
        for toi, tod in edges[tmpi]:
            if d[toi] > tmpd + tod:
                d[toi] = tmpd + tod
                heappush(h, (d[toi], toi))
    
    if d[n - 1] == float("inf"):
        print(-1)
    else:
        print(d[n - 1])
    


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class SegmentTree():
    def __init__(self, array, f, ti):
        """
        Parameters
        ----------
        array : list
            to construct segment tree from
        f : func
            binary operation of the monoid
        ti : 
            identity element of the monoid
        """
        self.f = f
        self.ti = ti
        self.n = n = 2**(len(array).bit_length())
        self.dat = dat = [ti] * n + array + [ti] * (n - len(array))
        for i in range(n - 1, 0, -1):  # build
            dat[i] = f(dat[i << 1], dat[i << 1 | 1])

    def update(self, p, v):  # set value at position p (0-indexed)
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = v
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def query(self, l, r):  # result on interval [l, r) (0-indexed)
        f, ti, n, dat = self.f, self.ti, self.n, self.dat
        res = ti
        l += n
        r += n
        while l < r:
            if l & 1:
                res = f(res, dat[l])
                l += 1
            if r & 1:
                r -= 1
                res = f(dat[r], res)
            l >>= 1
            r >>= 1
        return res


I = [int(_) for _ in open(0).read().split()]
N, M = I[:2]
L, R, C = I[2::3], I[3::3], I[4::3]
ti = float('inf')
ST = SegmentTree([0] * 2 + [ti] * (N - 1), min, ti)
for l, r, c in sorted(zip(L, R, C)):
    ST.update(r, min(ST.query(r, r + 1), ST.query(l, r) + c))
ans = ST.query(N, N + 1)
print(-1 if ans == ti else ans)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

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

INF = float('inf')
def dijkstra(s,n,g): # sからの最短距離 頂点数n g[v]=[(u1,w1),(u2,w2)....]:vからuへの有向辺があり、重みw
  que = []
  d = [INF for _ in range(n)]
  d[s] = 0
  heappush(que,(0,s))
  while len(que) > 0:
    p = heappop(que)
    v = p[1]
    if d[v] < p[0]:
      continue
    for u,w in g[v]:
      if d[u] > d[v]+w:
        d[u] = d[v]+w
        heappush(que,(d[u],u))
  return d

G = [[] for _ in range(N)]
for i in range(N-1):
  G[i+1].append((i,0))
for l,r,c in LRC:
  l -= 1
  r -= 1
  G[l].append((r,c))

p = dijkstra(0,N,G)[N-1]
print(p if p != INF else -1)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

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

INF = float('inf')
def dijkstra(s,n,g): # sからの最短距離 頂点数n g[v]=[(u1,w1),(u2,w2)....]:vからuへの有向辺があり、重みw
  que = []
  d = [INF for _ in range(n)]
  d[s] = 0
  heappush( que,(0,s) )
  while len(que)>0:
    p =  heappop(que)
    v = p[1]
    if d[v] < p[0]:
      continue
    for i in range(len(g[v])):
      edge = g[v][i]
      if d[edge[0]] > d[v] + edge[1]:
        d[edge[0]] = d[v] + edge[1]
        heappush( que,(d[edge[0]] , edge[0]) )
  return d

G = [[] for _ in range(N)]
for i in range(N-1):
  G[i+1].append((i,0))
for l,r,c in LRC:
  l -= 1
  r -= 1
  G[l].append((r,c))

p = dijkstra(0,N,G)[N-1]
print(p if p != INF else -1)

Submission status: Accepted

Solution code:
class SegmentTree:
  def __init__(self, size, default, op = min):
    self.size = 2**size.bit_length()
    self.dat = [default]*(self.size*2)
    self.op = op

  def update(self, i, x):
    i += self.size
    self.dat[i] = x
    while i > 0:
      i >>= 1
      self.dat[i] = self.op(self.dat[i*2], self.dat[i*2+1])

  def add(self, i, x):
    i += self.size
    self.dat[i] = self.op(self.dat[i], x)
    while i > 0:
      i >>= 1
      self.dat[i] = self.op(self.dat[i], x)

  def get(self, a, b = None):
    if b is None:
      b = a + 1
    l, r = a + self.size, b + self.size
    res = None
    while l < r:
      if l & 1:
        if res is None:
          res = self.dat[l]
        else:
          res = self.op(res, self.dat[l])
        l += 1

      if r & 1:
        r -= 1
        if res is None:
          res = self.dat[r]
        else:
          res = self.op(res, self.dat[r])
      l >>= 1
      r >>= 1
    return res

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)

INF = 10**18
dp = SegmentTree(N,INF,min)
dp.update(0,0)
#print(dp.get(0,1))

for l,r,c in LRC:
  p = dp.get(l-1,r-1)+c
  # cf.https://ikatakos.com/pot/programming_algorithm/contest_history/atcoder/2019/1109_nikkei2019-2-qual
  #for i in range(l,r):
  #  if p < dp.get(i):
  #    dp.update(i,p)
  if p < dp.get(r-1):
    dp.update(r-1,p)
print(dp.get(N-1) if dp.get(N-1) != INF else -1)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
import sys
input = sys.stdin.readline


# def dijkstra(graph: list, node: int, start: int) -> list:
#     # graph[node] = [(cost, to)]
#     INF = float('inf')
#     dist = [INF] * node
#
#     dist[start] = 0
#     heap = [(0, start)]
#     while heap:
#         cost, thisNode = heappop(heap)
#         for NextCost, NextNode in graph[thisNode]:
#             dist_cand = dist[thisNode] + NextCost
#             if dist_cand < dist[NextNode]:
#                 dist[NextNode] = dist_cand
#                 heappush(heap, (dist[NextNode], NextNode))
#     return dist
#     # dist = [costs to nodes]
def dijkstra(graph: list, n: int, v_s: int, INF: int = float('inf')) -> list:
    # graph[v_from] = [(cost, v_to), ...]
    dist = [INF] * n

    dist[v_s] = 0
    heap = [(0, v_s)]  # heap = [(dist[v], v), ...]
    while heap:
        _, v_from = heappop(heap)
        for cost, v_to in graph[v_from]:
            dist_cand = dist[v_from] + cost
            if dist_cand < dist[v_to]:
                dist[v_to] = dist_cand
                heappush(heap, (dist[v_to], v_to))
    return dist
    # dist = [costs to nodes]


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

INF = 10**15
dist = dijkstra(edge, n, 0, INF=INF)
ans = dist[-1] if dist[-1] != INF else -1

print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
import sys
input = sys.stdin.readline


# def dijkstra(graph: list, node: int, start: int) -> list:
#     # graph[node] = [(cost, to)]
#     INF = float('inf')
#     dist = [INF] * node
#
#     dist[start] = 0
#     heap = [(0, start)]
#     while heap:
#         cost, thisNode = heappop(heap)
#         for NextCost, NextNode in graph[thisNode]:
#             dist_cand = dist[thisNode] + NextCost
#             if dist_cand < dist[NextNode]:
#                 dist[NextNode] = dist_cand
#                 heappush(heap, (dist[NextNode], NextNode))
#     return dist
#     # dist = [costs to nodes]
def dijkstra(graph: list, n: int, v_s: int, INF: int = float('inf')) -> list:
    # graph[v_from] = [(cost, v_to), ...]
    dist = [INF] * n

    dist[v_s] = 0
    heap = [(0, v_s)]  # heap = [(dist[v], v), ...]
    while heap:
        _, v_from = heappop(heap)
        for cost, v_to in graph[v_from]:
            dist_cand = dist[v_from] + cost
            if dist_cand < dist[v_to]:
                dist[v_to] = dist_cand
                heappush(heap, (dist[v_to], v_to))
    return dist
    # dist = [costs to nodes]


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

dist = dijkstra(edge, n, 0)
ans = dist[-1] if dist[-1] != float("inf") else -1

print(ans)

Submission status: Accepted

Solution code:
import heapq

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

inf = 1 << 60
dp = [0] + [inf] * (n - 1)
queue = [(0, 0)]
check = [False] * n
while queue and not check[-1]:
  dist, act = heapq.heappop(queue)
  check[act] = True
  for cost, vertex in edge[act]:
    if check[vertex]:
      continue
    d = dist + cost
    if dp[vertex] > d:
      heapq.heappush(queue, (d, vertex))
      dp[vertex] = d
if dp[-1] < inf:
  print(dp[-1])
else:
  print(-1)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])
def sortx(x,n,k):
    if k == 0:x.sort(key=lambda y:y[1,n])
    else:x.sort(reversed=True, key=lambda y:y[1,n])
def graph():
    n=inp()
    g=[[] for _ in range(n)]
    for i in range(n):
        a=inp()
        a-=1
        g[i].append(a)
        g[a].append(i)
    return n,g
def graphm():
    n,m=inpm()
    g=[[] for _ in range(n)]
    for _ in range(m):
        a,b,w=inpm()
        a-=1
        b-=1
        g[a].append((b,w))
        g[b].append((a,w))
    return n,m,g

def dijkstra(s,n,g): # sからの最短距離 頂点数n
    s -= 1
    que = []
    d = [10**15 for _ in range(n)]
    d[s] = 0
    heappush( que,(0,s) )
    while len(que)>0:
        p =  heappop(que)
        v = p[1]
        if d[v] < p[0]:
            continue
        for i in range(len(g[v])):
            edge = g[v][i]
            if d[edge[0]] > d[v] + edge[1]:
                d[edge[0]] = d[v] + edge[1]
                heappush( que,(d[edge[0]] , edge[0]) )
    return d

def main():
    n,m,g=graphm()
    s=1
    for i in range(n-1):
        a=i+1
        b=i
        g[a].append((b,0))
    
    dis=dijkstra(s,n,g)
    if dis[n-1]==10**15:
        print(-1)
    else:
        print(dis[n-1])
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# from collections import Counter,defaultdict,deque
import sys
# import bisect
# import math
# import itertools
# import string
import queue
# import copy
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])
def sortx(x,n,k):
    if k == 0:x.sort(key=lambda y:y[1,n])
    else:x.sort(reversed=True, key=lambda y:y[1,n])
def graph():
    n=inp()
    g=[[] for _ in range(n)]
    for i in range(n):
        a=inp()
        a-=1
        g[i].append(a)
        g[a].append(i)
    return n,g
def graphm():
    n,m=inpm()
    g=[[] for _ in range(n)]
    for _ in range(m):
        a,b,w=inpm()
        a-=1
        b-=1
        g[a].append((b,w))
        g[b].append((a,w))
    return n,m,g

def dijkstra(s,n,g): # sからの最短距離 頂点数n
    s -= 1
    que = queue.Queue()
    d = [10**15 for _ in range(n)]
    d[s] = 0
    que.put( (0,s) )
    while not que.empty():
        p = que.get()
        v = p[1]
        if d[v] < p[0]:
            continue
        for i in range(len(g[v])):
            edge = g[v][i]
            if d[edge[0]] > d[v] + edge[1]:
                d[edge[0]] = d[v] + edge[1]
                que.put( (d[edge[0]] , edge[0]) )
    return d

def dijkstra1(s,n,g): # sからの最短距離 頂点数n
    s -= 1
    que = []
    d = [10**15 for _ in range(n)]
    d[s] = 0
    heappush( que,(0,s) )
    while len(que)>0:
        p =  heappop(que)
        v = p[1]
        if d[v] < p[0]:
            continue
        for i in range(len(g[v])):
            edge = g[v][i]
            if d[edge[0]] > d[v] + edge[1]:
                d[edge[0]] = d[v] + edge[1]
                heappush( que,(d[edge[0]] , edge[0]) )
    return d

def main():
    n,m,g=graphm()
    s=1
    for i in range(n-1):
        a=i+1
        b=i
        g[a].append((b,0))
    
    dis=dijkstra1(s,n,g)
    if dis[n-1]==10**15:
        print(-1)
    else:
        print(dis[n-1])
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra
import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines

N, M = map(int, readline().split())
lines = readlines()
edge = np.array([line.split() for line in lines], dtype = np.int64)
edge = sorted(edge,key=lambda x:(x[0],x[1],x[2]))

for i in range(1,M):
  if edge[i][0] == edge[i-1][0] and edge[i][1] == edge[i-1][1]:
    edge[i][2] = 0
#print(edge)
x = np.arange(N,1,-1)
y = np.arange(N-1,0,-1)
z = np.zeros(N-1,int)
X = np.vstack([x,y,z]).T
edge = np.concatenate([X,edge]).T
graph = csr_matrix((edge[2], (edge[:2] - 1)), (N, N))
distance_mat = dijkstra(graph, directed = True, indices = 0)
#print(distance_mat)
print(-1 if distance_mat[-1] == float("inf") else int(distance_mat[-1]))

Submission status: Accepted

Solution code:
import heapq


class Dijkstra:

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

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

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

            if dist[src] < prev_cost:
                continue

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

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

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

        return list(reversed(path))

n,m=map(int, input().split()) 
route_map = [dict() for _ in range(n)]

for i in range(m):
    u, v, a = map(int, input().split())
    u, v = u - 1, v - 1
    if v in route_map[u].keys():
        a = min(a, route_map[u][v])
    route_map[u][v] = a


    
for i in range(n-1):
    u, v = i+1, i
    route_map[u][v] = 0
    

# ゴールまでの最短経路
dijkstra_result = Dijkstra(route_map,0).execute()


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

else:
    print(-1)

Submission status: Accepted

Solution code:
# min の実験
from functools import reduce, partial
min = partial(reduce, lambda x, y: x if x < y else y)

class Rmq:
    # 平方分割
    # 値を変更すると元のリストの値も書き換わる
    # 検証: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3990681
    def __init__(self, a, sqrt_n=150, inf=(1<<31)-1):
        self.sqrt_n = sqrt_n
        if hasattr(a, "__iter__"):
            from itertools import zip_longest
            self.n = len(a)
            self.layer0 = [min(values) for values in zip_longest(*[iter(a)]*sqrt_n, fillvalue=inf)]
            self.layer1 = a
        elif isinstance(a, int):
            self.n = a
            self.layer0 = [inf] * ((a - 1) // sqrt_n + 1)
            self.layer1 = [inf] * a
        else:
            raise TypeError

    def get_min(self, l, r):
        sqrt_n = self.sqrt_n
        parent_l, parent_r = l//sqrt_n+1, (r-1)//sqrt_n
        if parent_l < parent_r:
            return min([min(self.layer0[parent_l:parent_r]),
                       min(self.layer1[l:parent_l*sqrt_n]),
                       min(self.layer1[parent_r*sqrt_n:r])])
        else:
            return min(self.layer1[l:r])

    def set_value(self, idx, val):
        self.layer1[idx] = val
        idx0 = idx // self.sqrt_n
        idx1 = idx0 * self.sqrt_n
        self.layer0[idx0] = min(self.layer1[idx1:idx1+self.sqrt_n])

    def chmin(self, idx, val):
        if self.layer1[idx] > val:
            self.layer1[idx] = val
            idx //= self.sqrt_n
            self.layer0[idx] = min([self.layer0[idx], val])

    def debug(self):
        print("layer0=", self.layer0)
        print("layer1=", self.layer1)

    def __getitem__(self, item):
        return self.layer1[item]

    def __setitem__(self, key, value):
        self.set_value(key, value)


from operator import itemgetter
def main():
    inf = 10**18
    N, M, *LRC = map(int, open(0).read().split())
    LRC = list(zip(*[iter(LRC)]*3))
    LRC.sort(key=itemgetter(0))

    idx_LRC = 0
    q = []

    seg = Rmq(N+1, inf=inf)

    seg.set_value(1, 0)
    for v in range(1, N + 1):
        d = seg.get_min(v, N + 1)
        while idx_LRC < M:
            l, r, c = LRC[idx_LRC]
            if l <= v:
                seg.chmin(r, d+c)
                idx_LRC += 1
            else:
                break
    ans = seg[N]
    print(ans if ans != inf else -1)

main()

Submission status: Accepted

Solution code:
from heapq import heappop, heappush, heapify
import sys
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))

#####  動的計画法（DP）による解法  #####
N, M = inpl()
LRC = sorted([inpl() for _ in range(M)])
# L,Rとして登場する点だけを取り出す。中間点が寄与することはない。
points = sorted(list({lrc[i] for i in range(2) for lrc in LRC}))
# 1またはNが無ければ終了。
if points[0] > 1 or points[-1] < N:
    print(-1)
    exit()

# 各経路の(1からの距離、有効範囲の限界点)ペアをヒープに格納。
# 初期状態は「(距離0、点1まで)」。
dq = [(0,1)]
m = 0 # エッジ群の番号。開始点の順にソートされている。
# DPループ。
# DP部分の計算量は O(M log M)。ヒープを叩くのは総計M+M回なので。Nにはよらない。
# 上のソート等も O(M log M) なので全体の計算量も同じ。
for i in points:
    # 有効範囲が終了したものを捨てる。
    # 距離が長いものは捨てずに放置しておいてもOK。
    while dq and dq[0][1] < i:
        heappop(dq)
    # 現在の点まで到達する経路が無ければ終了。
    if not dq:
        print(-1)
        break
    # 点1から現在の点までの最短距離。
    d = dq[0][0]
    # 現在の点から始まる各エッジ群による(距離、限界点)を順に格納。
    while m < M and LRC[m][0] == i:
        heappush(dq, (d+LRC[m][2], LRC[m][1]))
        m += 1
else:
    # 最後の点Nまで正常に終了した場合。
    print(d)

Submission status: Accepted

Solution code:
# いろいろ高速化
# https://atcoder.jp/contests/nikkei2019-2-qual/submissions/8436413
class Rmq:
    # 平方分割
    # 値を変更すると元のリストの値も書き換わる
    # 検証: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3990681
    def __init__(self, a, sqrt_n=150, inf=(1<<31)-1):
        self.sqrt_n = sqrt_n
        if hasattr(a, "__iter__"):
            from itertools import zip_longest
            self.n = len(a)
            self.layer0 = [min(values) for values in zip_longest(*[iter(a)]*sqrt_n, fillvalue=inf)]
            self.layer1 = a
        elif isinstance(a, int):
            self.n = a
            self.layer0 = [inf] * ((a - 1) // sqrt_n + 1)
            self.layer1 = [inf] * a
        else:
            raise TypeError

    def get_min(self, l, r):
        sqrt_n = self.sqrt_n
        parent_l, parent_r = l//sqrt_n+1, (r-1)//sqrt_n
        if parent_l < parent_r:
            return min(min(self.layer0[parent_l:parent_r]),
                       min(self.layer1[l:parent_l*sqrt_n]),
                       min(self.layer1[parent_r*sqrt_n:r]))
        else:
            return min(self.layer1[l:r])

    def set_value(self, idx, val):
        self.layer1[idx] = val
        idx0 = idx // self.sqrt_n
        idx1 = idx0 * self.sqrt_n
        self.layer0[idx0] = min(self.layer1[idx1:idx1+self.sqrt_n])

    def chmin(self, idx, val):
        if self.layer1[idx] > val:
            self.layer1[idx] = val
            idx //= self.sqrt_n
            self.layer0[idx] = min(self.layer0[idx], val)

    def debug(self):
        print("layer0=", self.layer0)
        print("layer1=", self.layer1)

    def __getitem__(self, item):
        return self.layer1[item]

    def __setitem__(self, key, value):
        self.set_value(key, value)


from operator import itemgetter
def main():
    N, M, *LRC = map(int, open(0).read().split())
    LRC = list(zip(*[iter(LRC)]*3))
    LRC.sort(key=itemgetter(0))

    idx_LRC = 0
    q = []

    inf = 10**18
    seg = Rmq(N+1, inf=inf)

    seg.set_value(1, 0)
    for v in range(1, N + 1):
        d = seg.get_min(v, N + 1)
        while idx_LRC < M:
            l, r, c = LRC[idx_LRC]
            if l <= v:
                seg.chmin(r, d+c)
                idx_LRC += 1
            else:
                break
    ans = seg[N]
    print(ans if ans != inf else -1)

main()

Submission status: Accepted

Solution code:
# いろいろ高速化
class Rmq:
    # 平方分割
    # 値を変更すると元のリストの値も書き換わる
    # 検証: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3990681
    def __init__(self, a, sqrt_n=150, inf=(1<<31)-1):
        self.sqrt_n = sqrt_n
        if hasattr(a, "__iter__"):
            from itertools import zip_longest
            self.n = len(a)
            self.layer0 = [min(values) for values in zip_longest(*[iter(a)]*sqrt_n, fillvalue=inf)]
            self.layer1 = a
        elif isinstance(a, int):
            self.n = a
            self.layer0 = [inf] * ((a - 1) // sqrt_n + 1)
            self.layer1 = [inf] * a
        else:
            raise TypeError

    def get_min(self, l, r):
        sqrt_n = self.sqrt_n
        parent_l, parent_r = l//sqrt_n+1, (r-1)//sqrt_n
        if parent_l < parent_r:
            return min(min(self.layer0[parent_l:parent_r]),
                       min(self.layer1[l:parent_l*sqrt_n]),
                       min(self.layer1[parent_r*sqrt_n:r]))
        else:
            return min(self.layer1[l:r])

    def set_value(self, idx, val):
        self.layer1[idx] = val
        idx0 = idx // self.sqrt_n
        idx1 = idx0 * self.sqrt_n
        self.layer0[idx0] = min(self.layer1[idx1:idx1+self.sqrt_n])

    def chmin(self, idx, val):
        if self.layer1[idx] > val:
            self.layer1[idx] = val
            idx //= self.sqrt_n
            self.layer0[idx] = min(self.layer0[idx], val)

    def debug(self):
        print("layer0=", self.layer0)
        print("layer1=", self.layer1)

    def __getitem__(self, item):
        return self.layer1[item]

    def __setitem__(self, key, value):
        self.set_value(key, value)


from operator import itemgetter

N, M, *LRC = map(int, open(0).read().split())
LRC = list(zip(*[iter(LRC)]*3))
LRC.sort(key=itemgetter(0))

idx_LRC = 0
q = []

inf = 10**18
seg = Rmq(N+1, inf=inf)

seg.set_value(1, 0)
for v in range(1, N + 1):
    d = seg.get_min(v, N + 1)
    while idx_LRC < M:
        l, r, c = LRC[idx_LRC]
        if l <= v:
            seg.chmin(r, d+c)
            idx_LRC += 1
        else:
            break
ans = seg[N]
print(ans if ans != inf else -1)