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:
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))
ans = seg.query(N - 1, N)
if ans == float('inf'):
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

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

import heapq
hq = [(0,0)]
INF = float('inf')
cost = [INF] * N
cost[0] = 0
while hq:
    d,v = heapq.heappop(hq)
    for to,c in es[v]:
        if cost[to] <= d+c: continue
        cost[to] = d+c
        heapq.heappush(hq, (d+c,to))

print(-1 if cost[-1]==INF else cost[-1])

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/nikkei2019-2-qual/submissions/16478910
# D - Shortest Path on a Line
import sys
from heapq import heapify, heappop, heappush

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def dijkstra_heap(v, start, edge):
    """
    ダイクストラ法
    :param v: 走査するグラフの頂点数
    :param start: 始点
    :param edge: 重み付き隣接リスト。[cost, node]の形で渡す
    :return: 始点から各頂点への最短距離
    """
    res = [f_inf] * v
    res[start] = 0
    checked = [False] * v
    checked[start] = True
    edge_list = []
    for u in edge[start]:
        heappush(edge_list, u)
    while len(edge_list):
        min_edge = heappop(edge_list)
        cost, node = min_edge
        if not checked[node]:
            res[node] = cost
            checked[node] = True
            for next_cost, next_node in edge[node]:
                if not checked[next_node]:
                    heappush(edge_list, [next_cost + cost, next_node])
    return res


class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(N)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """

    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        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番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        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, left, right):
        """
        [left, right)のsegfuncしたものを得る
        left: index(0-index)
        right: index(0-index)
        """
        res = self.ide_ele
        left += self.num
        right += self.num
        while left < right:
            if left & 1:
                res = self.segfunc(res, self.tree[left])
                left += 1
            if right & 1:
                res = self.segfunc(res, self.tree[right - 1])
            left >>= 1
            right >>= 1
        return res


def resolve():
    n, m = map(int, input().split())
    LRC = sorted([list(map(int, input().split())) for _ in range(m)], key=lambda x: [x[0], x[1]])
    dist = [f_inf] * n
    dist[0] = 0
    seg = SegTree(dist, lambda x, y: min(x, y), f_inf)
    for l, r, c in LRC:
        l -= 1
        r -= 1
        mi = seg.query(l, r)
        if dist[r] > mi + c:
            seg.update(r, mi + c)
            dist[r] = mi + c
    res = dist[-1]
    print(res if res != f_inf else -1)


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

    dist = dijkstra_heap(n, 0, edge)
    print(-1 if dist[-1] == f_inf else dist[-1])


if __name__ == '__main__':
    resolve2()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(N)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """

    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        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番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        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, left, right):
        """
        [left, right)のsegfuncしたものを得る
        left: index(0-index)
        right: index(0-index)
        """
        res = self.ide_ele
        left += self.num
        right += self.num
        while left < right:
            if left & 1:
                res = self.segfunc(res, self.tree[left])
                left += 1
            if right & 1:
                res = self.segfunc(res, self.tree[right - 1])
            left >>= 1
            right >>= 1
        return res


def resolve():
    n, m = map(int, input().split())
    LRC = sorted([list(map(int, input().split())) for _ in range(m)], key=lambda x: [x[0], x[1]])
    dist = [f_inf] * n
    dist[0] = 0
    seg = SegTree(dist, lambda x, y: min(x, y), f_inf)
    for l, r, c in LRC:
        l -= 1
        r -= 1
        mi = seg.query(l, r)
        if dist[r] > mi + c:
            seg.update(r, mi + c)
            dist[r] = mi + c
    res = dist[-1]
    print(res if res != f_inf else -1)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

import heapq


class PriorityQueue:
    class Reverse:
        def __init__(self, val):
            self.val = val

        def __lt__(self, other):
            return self.val > other.val

        def __repr__(self):
            return repr(self.val)

    def __init__(self, x=None, desc=False):
        if not x:
            x = []
        if desc:
            for i in range(len(x)):
                x[i] = self.Reverse(x[i])
        self._desc = desc
        self._container = x
        heapq.heapify(self._container)

    @property
    def is_empty(self):
        return not self._container

    def pop(self):
        if self._desc:
            return heapq.heappop(self._container).val
        else:
            return heapq.heappop(self._container)

    def push(self, item):
        if self._desc:
            heapq.heappush(self._container, self.Reverse(item))
        else:
            heapq.heappush(self._container, item)

    def top(self):
        if self._desc:
            return self._container[0].val
        else:
            return self._container[0]

    def sum(self):
        return sum(self._container)

    def __len__(self):
        return len(self._container)


def main():
    from collections import deque, defaultdict
    N, M = map(int, readline().split())

    edge = defaultdict(list)

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

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

    pq = PriorityQueue()
    pq.push((0, 1))
    dist = defaultdict(lambda: INF)

    while pq:
        cur, u = pq.pop()
        for v, c in edge[u]:
            nc = cur + c
            if nc < dist[v]:
                dist[v] = nc
                pq.push((nc, v))

    if dist[N] != INF:
        print(dist[N])
    else:
        print(-1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from heapq import *
input = sys.stdin.readline

def main():
    n, m = map(int, input().split())
    
    tree = [[] for _ in range(n)]
    for i in range(m):
        s, t, c = map(int, input().split())
        tree[t-1].append((s-1, c))
        tree[s-1].append((t-1, c))
    
    for i in range(n-1):
        tree[i+1].append((i, 0))
    
    ans = [-1]*n
    already = [False]*n
    not_yet = [(0, 0)]
    
    while not_yet:
        value, key = heappop(not_yet)
        if already[key]:
            continue
        already[key] = True
        ans[key] = value
        
        for k, v in tree[key]:
            if already[k]:
                continue
            heappush(not_yet, (v+value, k))
        
    print(ans[n-1])
    
    
    
    
if __name__ == "__main__":
    main()

Submission status: Accepted

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

class Segment_tree_Lazy:
    
    def __init__(self, n):
        
        self.init(n)
        
        #この次の処理は、求められる動作に応じて変化させる。ここでは区間最小問題のコードを書く。
        self.node = [self.inf]*self.size
        
        self.lazy = [self.inf]*self.size
        
        
    def init(self, n):
        
        self.inf = pow(2, 60)
        self.n = n
        
        self.N = 1
        while self.N < self.n:
            self.N *= 2
            
        self.size = self.N * 2 - 1
        self.N -= 1
        
        
    def evalate(self, k, l, r):
        
        if self.lazy[k] != self.inf:
            self.node[k] = min(self.lazy[k], self.node[k])
            
            if r-l > 1:
                if self.lazy[2*k+1] > self.lazy[k]:
                    self.lazy[2*k+1] = self.lazy[k]
                if self.lazy[2*k+2] > self.lazy[k]:
                    self.lazy[2*k+2] = self.lazy[k]
                
            self.lazy[k] = self.inf
         
            
    def update(self, a, b, x, k=0, l=0, r=-1):
        
        if r < 0:
            r = self.size - self.N
        
        if b <= l or r <= a:
            return 0
        
        if a <= l and r <= b:
            self.lazy[k] = x
            self.evalate(k, l, r)
            return 0
        
        self.update(a, b, x, 2*k+1, l, (l+r)//2)
        self.update(a, b, x, 2*k+2, (l+r)//2, r)
        self.node[k] = min(self.node[2*k+1], self.node[2*k+2])
        
        
    def find(self, a, b, k, l, r):
        
        if r <= a or b <= l:
            return self.inf
        
        self.evalate(k, l, r)
        
        if a <= l and r <= b:
            return self.node[k]
        
        find_l = self.find(a, b, 2*k+1, l, (l+r)//2)
        find_r = self.find(a, b, 2*k+2, (l+r)//2, r)
        return min(find_l, find_r)
    
    
    def count(self, l, r):
        
        return self.find(l, r, 0, 0, self.size-self.N)
    
    
    
    

def main():
    n, m = map(int, input().split())
    
    inf = pow(2, 60)
    dp = [inf]*(n)
    dp[0] = 0
    
    node = [[] for _ in range(n)]
    segment = Segment_tree_Lazy(n)
    
    segment.update(0, 1, 0)
    for i in range(m):
        s, t, c = map(int, input().split())
        node[t-1].append((s-1, c))
        segment.update(s, t, c)
    
    for i in range(n-1):
        dp[i+1] = dp[i] + min(segment.node[segment.N+i+1], segment.lazy[segment.N+i+1])
        for (v, c) in node[i+1]:
            dp[i+1] = min(dp[i+1], dp[v]+c)
        index = i
        while True:
            if dp[index] > dp[index+1]:
                dp[index] = dp[index+1]
                index -= 1
            else:
                break
    
    print(dp[n-1] if dp[n-1] < inf else -1)
    
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

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

def dijkstra(s,graph):
    d = [inf]*n
    d[s] = 0
    h = [(0,s)]
    while h:
        c,v = heappop(h)
        if d[v] < c:
            continue
        for t,cost in graph[v]:
            if d[v] + cost < d[t]:
                d[t] = d[v] + cost
                heappush(h,(d[t],t))
    return d

n, m = LI()
edges = [[] for _ in range(n)]
for i in range(1, n):
    edges[i].append((i-1, 0))

for _ in range(m):
    l, r, c = LI()
    edges[l-1].append((r-1, c))

d = dijkstra(0, edges)
if d[-1] == inf:
    print(-1)
else:
    print(d[-1])

Submission status: Accepted

Solution code:
import heapq
n, m = map(int, input().split())
INF = float('inf')


def dijkstra(s, n, edges):
    d = [INF] * n
    d[s] = 0
    pq = [(0, s)]
    while len(pq) != 0:
        c, v = heapq.heappop(pq)
        if d[v] < c:
            continue
        for v2nvc, nv in edges[v]:
            if c + v2nvc < d[nv]:
                d[nv] = c + v2nvc
                heapq.heappush(pq, (d[nv], nv))
    return d


edges = [[] for _ in range(n)]
for _ in range(m):
    l, r, c = map(int, input().split())
    l -= 1
    r -= 1
    edges[l].append((c, r))
for i in range(n - 1):
    edges[i + 1].append((0, i))
d = dijkstra(0, n, edges)
if d[-1] == INF:
    print(-1)
else:
    print(d[-1])

Submission status: Accepted

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

import heapq
def dijkstra_heap(s):
  #始点sから各頂点への最短距離と直前の点
  dist=[float("inf")]*size_v
  prev=[-1]*size_v
  used=[False]*size_v
  #used=set()
  dist[s]=0
  used[s]=True
  #used.add(s)

  hq_edge=[]
  for v,w in graph[s]:
    heapq.heappush(hq_edge,(w,v,s))

  while hq_edge:
    min_w,min_v,u=heapq.heappop(hq_edge)
    #まだ使われてない頂点の中から最小の距離のものを探す
    if used[min_v]:
    #if min_v in used:
      continue

    dist[min_v]=min_w
    prev[min_v]=u
    used[min_v]=True
    #used.add(min_v)
    for v,w in graph[min_v]:
      if not used[v]: 
      #if not v in used:
        heapq.heappush(hq_edge,(min_w+w,v,min_v))

  return dist,prev

size_v=N+1
s=1

graph=[[] for _ in range(size_v)]
for i in range(2,N):
  graph[i].append((i-1,0))
for _ in range(M):
  L,R,C=map(int,input().split())
  graph[L].append((R,C))
  
dist,prev=dijkstra_heap(s)
#print(dist)
if dist[N]==float("inf"):
  print(-1)
else:
  print(dist[N])

Submission status: Accepted

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

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)

ans = -1 if L[N-1] == INF else L[N-1]

print(ans)

Submission status: Accepted

Solution code:
import heapq

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

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

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=[[0,now]]
while todo:
  d,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,[seen[v]+c,r-1])
      seen[r-1]=seen[v]+c
if seen[-1]!=inf:
  print(seen[-1])
else:
  print(-1)
#print(seen)

Submission status: Accepted

Solution code:
import math
#import numpy as np
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,m = map(int,ipt().split())
    way = [[] for i in range(n+1)]
    for _ in range(m):
        l,r,c = map(int,ipt().split())
        way[l].append((r,c))
    for i in range(1,n):
        way[i+1].append((i,0))
    hq = [(0,1)]
    dst = [10**18]*(n+1)
    dst[1] = 0
    while hq:
        di,qi = hpq.heappop(hq)
        for j,cj in way[qi]:
            if dst[j] > di+cj:
                dst[j] = di+cj
                hpq.heappush(hq,(di+cj,j))
    print((dst[n]+1)%(10**18+1)-1)
    
    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n,m = map(int,readline().split())
chk = []
for i in range(m):
  l,r,c = map(int,readline().split())
  chk.append((l-1,r-1,c))
  
chk.sort()
class SegmentTree:
    def __init__(self, n, ele, segfun):
        self.ide_ele = ele
        self.segfun = segfun
        self.n = n
        self.N0 = 1 << n.bit_length()
        self.data = [self.ide_ele] * (self.N0 * 2)

    def update(self, l, r, val):
        l += self.N0
        r += self.N0
        while l < r:
            if l & 1:
                self.data[l] = self.segfun(self.data[l], val)
                l += 1
            if r & 1:
                self.data[r - 1] = self.segfun(self.data[r - 1], val)
                r -= 1
            l //= 2
            r //= 2

    def query(self, i):
        i += len(self.data) // 2
        ret = self.data[i]
        while i > 0:
            i //= 2
            ret = self.segfun(ret, self.data[i])
        return ret

S = SegmentTree(n,10**14,lambda a,b: min(a,b))
S.update(0,1,0)
for l,r,c in chk:
  a = S.query(l)
  S.update(l,r+1,a+c)
  
ans = S.query(n-1)
if ans == 10**14:
  print(-1)
else:
  print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from heapq import *

def dijkstra():
    dist = [10**18]*N
    dist[0] = 0
    pq = []
    heappush(pq, (0, 0))
    
    while pq:
        d, v = heappop(pq)
        
        if dist[v]<d:
            continue
        
        for nv, w in G[v]:
            if dist[nv]>dist[v]+w:
                dist[nv] = dist[v]+w
                heappush(pq, (dist[nv], nv))
    
    return dist

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

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

ans = dijkstra()[-1]

if ans==10**18:
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

def dijkstra(s,edge):
    #始点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())
edge=[[] for _ in range(n)]
for i in range(n-1):
  edge[i+1].append([0,i])
for _ in range(m):
  u,v,w=map(int,input().split())
  edge[u-1].append([w,v-1])
  edge[v-1].append([w,u-1])
d=dijkstra(0,edge)
if d[n-1]==float('inf'):
  print(-1)
else:
  print(d[n-1])

Submission status: Accepted

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 ** 20] * 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: Accepted

Solution code:
from heapq import heappop, heappush, heapify

class Graph():  #directed
    def __init__(self, n, edge, indexed=1):
        self.n = n
        self.graph = [[] for _ in range(n)]
        self.deg = [0 for _ in range(n)]
        for e in edge:
            self.graph[e[0] - indexed].append((e[1] - indexed, e[2]))
            self.deg[e[1] - indexed] += 1

    def dijkstra(self, s, INF=10**18, restore_to=None):
        dist = [INF for _ in range(self.n)]
        dist[s] = 0
        heap = [(0, s)]
        while heap:
            cost, node = heappop(heap)
            if dist[node] < cost:
                continue
            for adj, adjcost in self.graph[node]:
                if dist[node] + adjcost < dist[adj]:
                    dist[adj] = dist[node] + adjcost
                    heappush(heap, (dist[adj], adj))
        if restore_to is not None:
            g = restore_to
            if dist[g] == INF:
                return dist, False
            path = [g]
            node = g
            while node != s:
                node = prev[node]
                path.append(node)
            return dist, path[::-1]
        return dist

import sys
input = sys.stdin.readline

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

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

for i in range(N - 1):
    E.append((i + 1, i, 0))

g = Graph(N, E, 0)
res = g.dijkstra(0)[N - 1]

print(res if res != 10**18 else -1)

Submission status: Accepted

Solution code:
import heapq
def dijkstra_heap(s,edge,n):
    d = [float("inf")] * n
    used = [True] * n
    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())
graph = [[] for _ in range(n)]
for i in range(1,n):
    graph[i].append((0,i-1))
for i in range(m):
    l,r,c = map(int,input().split())
    graph[l-1].append((c,r-1))
ans = dijkstra_heap(0,graph,n)[-1]
if ans == float("inf"):
    print(-1)
else:
    print(ans)