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:
# RMQ のパフォーマンステスト
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 = map(int, input().split())
LRC = [list(map(int, input().split())) for _ in range(M)]
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)

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()))

N, M = inpl()
LRC = sorted([inpl() for _ in range(M)])
points = sorted(list({lrc[i] for i in range(2) for lrc in LRC} | {1,N}))
m = 0
dq = [(0,1)]
for i in points:
    while dq and dq[0][1] < i:
        heappop(dq)
    if not dq:
        print(-1)
        break
    d = dq[0][0]
    while m < M and LRC[m][0] == i:
        heappush(dq, (d+LRC[m][2], LRC[m][1]))
        m += 1
else:
    print(d)

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()))

N, M = inpl()
LRC = sorted([(lambda L,R,C:(L-1,R-1,C))(*inpl()) for _ in range(M)])
m = 0
dq = [(0,0)]
for i in range(N):
    while dq and dq[0][1] < i:
        heappop(dq)
    if not dq:
        print(-1)
        break
    d = dq[0][0]
    while m < M and LRC[m][0] == i:
        heappush(dq, (d+LRC[m][2], LRC[m][1]))
        m += 1
else:
    print(d)

Submission status: Accepted

Solution code:
# 抽象化をやめる
class Rmq(object):
    __slots__ = ["elem_size", "tree", "real_size"]

    def __init__(self, a):
        if hasattr(a, "__iter__"):
            self.real_size = len(a)
            self.elem_size = elem_size = 1 << (self.real_size-1).bit_length()
            self.tree = tree = [float("inf")] * (elem_size * 2)
            tree[elem_size:elem_size + self.real_size] = a
            for i in range(elem_size - 1, 0, -1):
                tree[i] = min(tree[i << 1], tree[(i << 1) + 1])
        elif isinstance(a, int):
            self.real_size = a
            self.elem_size = elem_size = 1 << (self.real_size-1).bit_length()
            self.tree = [float("inf")] * (elem_size * 2)

    def get_value(self, x: int, y: int) -> int:  # 半開区間
        l, r = x + self.elem_size, y + self.elem_size
        tree = self.tree
        result = float("inf")
        while l < r:
            if l & 1:
                result = min(tree[l], result)
                l += 1
            if r & 1:
                r -= 1
                result = min(tree[r], result)
            l, r = l >> 1, r >> 1
        return result

    def set_value(self, i: int, value: int) -> None:
        k = self.elem_size + i
        tree = self.tree
        tree[k] = value
        while k > 1:
            k >>= 1
            tree[k] = min(tree[k << 1], tree[(k << 1) + 1])

    def get_one_value(self, i):
        return self.tree[i+self.elem_size]

    def debug(self):
        print(self.tree[self.elem_size:self.elem_size+self.real_size])


from operator import itemgetter

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

idx_LRC = 0
q = []

seg = Rmq(N+1)

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

Submission status: Accepted

Solution code:
# セグ木のパフォーマンステスト

class SegmentTree(object):
    __slots__ = ["elem_size", "tree", "default", "op", "real_size"]

    def __init__(self, a, default, op):
        self.default = default
        self.op = op
        if hasattr(a, "__iter__"):
            self.real_size = len(a)
            self.elem_size = elem_size = 1 << (self.real_size-1).bit_length()
            self.tree = tree = [default] * (elem_size * 2)
            tree[elem_size:elem_size + self.real_size] = a
            for i in range(elem_size - 1, 0, -1):
                tree[i] = op(tree[i << 1], tree[(i << 1) + 1])
        elif isinstance(a, int):
            self.real_size = a
            self.elem_size = elem_size = 1 << (self.real_size-1).bit_length()
            self.tree = [default] * (elem_size * 2)

    def get_value(self, x: int, y: int) -> int:  # 半開区間
        l, r = x + self.elem_size, y + self.elem_size
        tree, result, op = self.tree, self.default, self.op
        while l < r:
            if l & 1:
                result = op(tree[l], result)
                l += 1
            if r & 1:
                r -= 1
                result = op(tree[r], result)
            l, r = l >> 1, r >> 1
        return result

    def set_value(self, i: int, value: int) -> None:
        k = self.elem_size + i
        op, tree = self.op, self.tree
        tree[k] = value
        while k > 1:
            k >>= 1
            tree[k] = op(tree[k << 1], tree[(k << 1) + 1])

    def get_one_value(self, i):
        return self.tree[i+self.elem_size]

    def debug(self):
        print(self.tree[self.elem_size:self.elem_size+self.real_size])


from operator import itemgetter

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

idx_LRC = 0
q = []

seg = SegmentTree(N+1, float("inf"), min)

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

Submission status: Accepted

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

N, M = inpl()
q = []
LRC = sorted([inpl() for _ in range(M)])
points = sorted(list({lrc[i] for i in range(2) for lrc in LRC}))
if points[0] != 1 or points[-1] != N:
    print(-1)
    exit()
positions = dict()
P = 0
prev = -1
for p in points:
    if p > prev:
        prev = p
        positions[p] = P
        P += 1
m = 0
dq = [(0,0)]
for i in range(P):
    while dq and dq[0][1] < i:
        heappop(dq)
    if not dq:
        print(-1)
        break
    d = dq[0][0]
    while m < M and positions[LRC[m][0]] == i:
        heappush(dq, (d+LRC[m][2], positions[LRC[m][1]]))
        m += 1
else:
    print(d)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
inf = float('inf')

# 計算量O((E+V)logV)
# 引数(始点,隣接リスト)
def dijkstra(start,ad):
    global dist
    #global cnt
    N = len(ad)
    dist = [inf] * N
    dist[start] = 0
    #cnt = [0] * N
    #cnt[start] = 1
    pq = [(dist[start], start)]
    while pq:
        dist_v, v = heappop(pq)
        for nv, nw in ad[v]:
            if dist[nv] > dist_v + nw:
                dist[nv] = dist_v + nw
                heappush(pq,(dist[nv], nv))
            #if dist[nv] == dist_v + nw:
                #cnt[nv] += cnt[v]
                #cnt[nv] %= mod

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

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

dijkstra(0, to)

ans = dist[N-1]
if ans == inf:
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
# セグ木のパフォーマンステスト

class SegmentTree(object):
    __slots__ = ["elem_size", "tree", "default", "op"]

    def __init__(self, a, default, op):
        self.default = default
        self.op = op
        if hasattr(a, "__iter__"):
            real_size = len(a)
            self.elem_size = elem_size = 1 << (real_size-1).bit_length()
            self.tree = tree = [default] * (elem_size * 2)
            tree[elem_size:elem_size + real_size] = a
            for i in range(elem_size - 1, 0, -1):
                tree[i] = op(tree[i << 1], tree[(i << 1) + 1])
        elif isinstance(a, int):
            real_size = a
            self.elem_size = elem_size = 1 << (real_size-1).bit_length()
            self.tree = [default] * (elem_size * 2)

    def get_value(self, x: int, y: int) -> int:  # 半開区間
        l, r = x + self.elem_size, y + self.elem_size
        tree, result, op = self.tree, self.default, self.op
        while l < r:
            if l & 1:
                result = op(tree[l], result)
                l += 1
            if r & 1:
                r -= 1
                result = op(tree[r], result)
            l, r = l >> 1, r >> 1
        return result

    def set_value(self, i: int, value: int) -> None:
        k = self.elem_size + i
        self.tree[k] = value
        self.update(k)

    def update(self, i: int) -> None:
        op, tree = self.op, self.tree
        while i > 1:
            i >>= 1
            tree[i] = op(tree[i << 1], tree[(i << 1) + 1])


from operator import itemgetter

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

idx_LRC = 0
q = []

seg = SegmentTree(N+1, float("inf"), min)

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

Submission status: Accepted

Solution code:
import heapq
N, M = map(int, input().split())
edge_list = [[] for i in range(N+1)]
for i in range(2, N + 1):
    edge_list[i].append((0, i-1))
for i in range(M):
    L, R, C = map(int, input().split())
    edge_list[L].append((C, R))
def solve(s, t):
    fixed = {}
    q = []
    heapq.heappush(q, (0, s))
    while q:
        w, x = heapq.heappop(q)
        if x == t:
            return w
        if x in fixed:
            continue
        fixed[x] = w
        for c, y in edge_list[x]:
            if y not in fixed:
                heapq.heappush(q, (w + c, y))
    return None

answer = solve(1, N)
if answer is None:
    print(-1)
else:
    print(answer)

Submission status: Accepted

Solution code:
import sys
from heapq import heappop, heappush


def dijkstra(s, t, links):
    q = [(0, s)]
    visited = set()
    while q:
        cost, v = heappop(q)
        if v in visited:
            continue
        if v == t:
            return cost
        visited.add(v)
        for u, c in links[v]:
            if u in visited:
                continue
            heappush(q, (cost + c, u))
    return -1


n, m = list(map(int, input().split()))
links = [set() for _ in range(n)]
for v in range(n - 1):
    links[v + 1].add((v, 0))
for line in sys.stdin:
    l, r, c = map(int, line.split())
    links[l - 1].add((r - 1, c))
print(dijkstra(0, n - 1, links))

Submission status: Accepted

Solution code:
import heapq

INF = 2**62-1

def dijkstra(route_map, start_point):
    num_of_city = len(route_map)
    dist = [INF for _ in range(num_of_city)]

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

        if dist[src] < prev_cost:
            continue

        for dest, cost in route_map[src].items():
            if dist[dest] > dist[src] + cost:
                dist[dest] = dist[src] + cost
                heapq.heappush(heap_q, (dist[dest], dest))
    return dist

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

for i in range(m):
    u, v, a = list(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)

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

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

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

for i in range(1, n):
    graph[i].append((i-1, 0))

for _ in range(m):
    f, t, c = map(int, input().split())
    f -= 1; t -= 1
    graph[f].append((t, c))

INF = float("inf")
s = 0
d = [0] + [INF] * (n-1)
q = []
heappush(q, (0, s))

while q:
    dist, v = heappop(q)
    if d[v] < dist: continue
    for nv, cost in graph[v]:
        if d[nv] > d[v] + cost:
            d[nv] = d[v] + cost
            heappush(q, (d[nv], nv))

print(-1 if d[n-1] == INF else d[n-1])

Submission status: Accepted

Solution code:
import sys


class SegTreeMin:
    """
    以下のクエリを処理する
    1.update:  i番目の値をxに更新する
    2.get_min: 区間[l, r)の最小値を得る
    """

    def __init__(self, n, INF):
        """
        :param n: 要素数
        :param INF: 初期値（入りうる要素より十分に大きな数）
        """
        self.n = n
        # nより大きい2の冪数
        n2 = 1
        while n2 < n:
            n2 <<= 1
        self.n2 = n2
        self.tree = [INF] * (n2 << 1)
        self.INF = INF

    def update(self, i, x):
        """
        i番目の値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.n2
        self.tree[i] = x
        while i > 1:
            self.tree[i >> 1] = x = min(x, self.tree[i ^ 1])
            i >>= 1

    def get_min(self, a, b):
        """
        [a, b)の最小値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        result = self.INF

        l = a + self.n2
        r = b + self.n2
        while l < r:
            if r & 1:
                result = min(result, self.tree[r - 1])
            if l & 1:
                result = min(result, self.tree[l])
                l += 1
            l >>= 1
            r >>= 1

        return result

    def debug_print(self):
        a = 1
        while a <= self.n2:
            b = a << 1
            print(self.tree[a:b])
            a = b
        print()


INF = 10 ** 18
n, m = map(int, input().split())
segments = [tuple(map(int, line.split())) for line in sys.stdin]
segments.sort()
sgt = SegTreeMin(n, INF)
sgt.update(0, 0)

for l, r, c in segments:
    use_current = sgt.get_min(l - 1, r - 1) + c
    not_current = sgt.get_min(r - 1, r)

    if use_current < not_current:
        sgt.update(r - 1, use_current)

ans = sgt.get_min(n - 1, n)
if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import sys
from heapq import heapify, heappop, heappush
MAX_INT = int(10e15)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N, M = IL()
LRC = [IL() for _ in range(M)]

root = [[(0, i-1)] for i in range(N+1)] #(cost, vertex)
for i in range(M):
  L, R, C = LRC[i]
  root[L].append((C, R))
#print(root)
data = []
heappush(data, (0, 1)) #(total_cost, vertex)
ans = [MAX_INT]*(N+1)
ans[1] = 0
finished = [False]*(N+1)
finished[0] = True

while data:
  nowcost, v = heappop(data)
  #print(nowcost, v)
  if finished[v] == False:
    finished[v] = True
    for edge, nextv in root[v]:
      if ans[nextv] < nowcost + edge:
        continue
      else:
        ans[nextv] = nowcost + edge
        heappush(data, (nowcost + edge, nextv))
      #print(ans)
if finished[N] == True:
  print(ans[N])
else:
  print(-1)

Submission status: Accepted

Solution code:
import heapq

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

dists = [None for _ in range(n)]
h = [(0, 0)]
for i in range(n):
  while len(h) > 0 and h[0][1] < i:
    heapq.heappop(h)
  if len(h) == 0:
    break
  dists[i] = h[0][0]
  for e in edges[i]:
    heapq.heappush(h, (e[1] + dists[i], e[0]))
print(-1 if dists[i] is None else dists[-1])

Submission status: Accepted

Solution code:
from heapq import *
from collections import *

N, M = map(int, input().split())
L, R, C = [0] * M, [0] * M, [0] * M

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

start = defaultdict(lambda: [])
end = defaultdict(lambda: [])
for i in range(M):
    start[L[i]].append(i)
    end[R[i]].append(i)

state = []
for i in start[0]:
    heappush(state, (C[i], i))

for i in range(1, N):
    while len(state) > 0 and R[state[0][1]] < i:
        heappop(state)

    if len(state) == 0:
        print(-1)
        exit()

    for j in start[i]:
        heappush(state, (state[0][0] + C[j], j))

print(state[0][0])

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

def dijkstra_heap(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heappush(edgelist,e)
    while len(edgelist):
        minedge = 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]]:
                heappush(edgelist,[e[0]+d[v],e[1]])
    return d

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

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

Submission status: Accepted

Solution code:
n, m, *t = map(int, open(0).read().split())
inf = float('inf')
dp = [inf] * -~n
dp[1] = 0

import heapq

mn = []
path = eval('[],' * -~n)
for l, r, c in zip(*[iter(t)] * 3):
    path[l].append((r, c))


def ins(v, r):
    heapq.heappush(mn, (v, r))


for i in range(1, n + 1):
    while len(mn) and mn[0][1] < i:
        heapq.heappop(mn)
    if len(mn):
        dp[i] = min(dp[i], mn[0][0])
    for r, c in path[i]:
        ins(dp[i] + c, r)

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

Submission status: Accepted

Solution code:
#          .g          `
#       .J.,M|  ..+NMMJMMMMNg..     `        `      `   `
#       ?TMa,5.MMMMMMM?MMMMMMMMt    _Z771,   (w.  j771. j_  z  `  `  `  `  `
#      dNHk;.NMMMB3???<ZZZZZW#^  `  _I  (Z  -C?l  j_  O j_  z`                `
#         .dMMM3_1????{ZZZZX=       _Ozr>`  J>.z_ jIz7! j7?7O`
#    `    dMMM!..__1=?>wZZC`        _I _O. (>  ?I j_    j_  z`
#        .MMM%.._Tm,?1>z0^          _C  _1.J`   (:j`    j`  z`   `  `  `  `  `
#        .Hmm..-?=!..``-gNNg-...`                -.
#     `  JMMMz>>????<<..WMMMMMMMMNe              !_                            `
#        ,MMMp?>?<<(;:(yI1rrwVMMMMM| z771.  `(v-  (C71+ (}  (:  `
#         WMMN<<(::;:!dyyIjtrrrdMMM\`O   w~  J<I  (}  (:(}  ({     `  `  `  `
#    `  `  TgMNx;;:;;(yyyyn1trqMMM# .OvO2!  (l.({ (Izv^ (C771{         .. .. .,
#           TMMMNgJ+!dyyyyynjMMMM#! `O _1. .v~`~z.(}    (}  ({    O?z(_.J..o.l,
#            .TMMMMM(MMMMMMMNWMM"    O  `1-(:   (l(}    (}  ({
#     `          ?""WMMMMMMW9^
#       `                                                      `


import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30

def dijkstra(n, start, nbl):
    """n: 頂点数, start: 始点, nbl: 隣接リスト"""
    import heapq
    WHITE = 1<<5
    GRAY = 1<<10
    BLACK = 1<<15
    color = [WHITE] * n
    distance = [INF] * n
    # parent = [-1] * n
    q = []

    distance[start] = 0
    heapq.heappush(q, (0, start))
    while len(q) != 0:
        du, u = heapq.heappop(q)
        # print("u: {}, du: {}".format(u, du))
        color[u] = BLACK
        if distance[u] < du:
            continue
        for next, cost in nbl[u]:
            if color[next] != BLACK and distance[u] + cost < distance[next]:
                distance[next] = distance[u] + cost
                color[next] = GRAY
                heapq.heappush(q, (distance[next], next))
    return distance

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def Dijkstra(g, s):
    prev = {}
    q = []
    d = defaultdict(lambda: INF)
    d[s] = 0
    heapq.heappush(q, (d[s], s))

    while q:
        c, u = heapq.heappop(q)
        if d[u] < c:
            continue
        for v, w in g[u].items():
            alt = w + c
            if d[v] > alt:
                d[v] = alt
                prev[v] = u
                heapq.heappush(q, (alt, v))
    return d

@mt
def slv(N, LRC):
    g = defaultdict(dict)

    LRC.sort(key=lambda x: x[2], reverse=True )
    for l, r, c in LRC:
        g[l][r] = c
    
    for i in range(2, N+1):
        g[i][i-1] = 0

    
    d = Dijkstra(g, 1)

    return -1 if d[N] == INF else d[N]


def main():
    N, M = read_int_n()
    LRC = [read_int_n() for _ in range(M)]
    print(slv(N, LRC))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
from heapq import heappop, heappush


class Graph():

    def __init__(self):
        self.graph = defaultdict(list)

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

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra():

    def __init__(self, graph, start):
        self.g = graph.graph

        self.dist = defaultdict(lambda: float("inf"))
        self.dist[start] = 0

        self.prev = defaultdict(lambda: None)

        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            dist_u, u = heappop(self.Q)

            if self.dist[u] < dist_u:
                continue

            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):

        return self.dist[goal]

    def shortest_path(self, goal):
        path = []
        node = goal

        while node is not None:
            path.append(node)
            node = self.prev[node]

        return path[::-1]


import sys
input=sys.stdin.readline
n,m=map(int,input().split())
g=Graph()

for _ in range(m):
    l,r,c=map(int,input().split())
    g.add_edge(l,r,c)
for i in range(2,n+1):
    g.add_edge(i,i-1,0)


d = Dijkstra(g,1)
ans=d.shortest_distance(n)
print(ans if ans!=float("inf") else -1)

Submission status: Accepted

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

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


def dijkstra(graph, start, inf=float('inf')):
    import heapq
    n = len(graph)
    distances = [inf] * n
    distances[start] = 0
    visited = [False] * n

    # 距離・頂点
    hq = [(0, start)]
    while hq:
        dist, fr = heapq.heappop(hq)
        visited[fr] = True

        for to, cost in graph[fr]:
            new_dist = distances[fr] + cost
            if (visited[to]) or (distances[to] <= new_dist):
                continue

            distances[to] = new_dist
            heapq.heappush(hq, (new_dist, to))

    return distances


ans = dijkstra(G, 0)[N - 1]
print(ans if ans != float('inf') else -1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n, m = map(int,input().split())
C = [list(map(int,input().split())) for i in range(m)]
S = [0] * n

for i in range(m):
    for j in range(2):
        C[i][j] -= 1

for i in range(m):
    S[C[i][0]] += 1
    S[C[i][1]] -= 1

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

for i in range(n-1):
    if S[i] > 0:
        C.append([i+1, i, 0])

M = [[] for i in range(n)]
for i in range(len(C)):
    M[C[i][0]].append([C[i][1], C[i][2]])
    if C[i][2] > 0:
        M[C[i][1]].append([C[i][0], C[i][2]])

import heapq

D = [float("inf")] * n
P = [-1] * n
D[0] = 0
V = [0] * n
Q = []
for v in range(n):
    heapq.heappush(Q, [D[v], v])

le = len(Q)
while le > 0:
    q = heapq.heappop(Q)
    u = q[1]
    du = q[0]
    if V[u] == 0:
        V[u] = 1
        le -= 1
        for i in range(len(M[u])):
            v = M[u][i][0]
            luv = M[u][i][1]
            if V[v] == 0:
                alt = du + luv
                if D[v] > alt:
                    D[v] = alt
                    P[v] = u
                    heapq.heappush(Q, [alt, v])

ans = D[-1]
if ans == float("inf"):
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
INF = 10**15
n,m=map(int,input().split())
graph=[[] for i in range(n)]
for i in range(m):
  l,r,c=map(int,input().split())
  l-=1;r-=1
  graph[l].append((r,c))
for i in range(n-1):
  graph[i+1].append((i,0))
def dijkstra(N, G, s):
    global dist
    dist = [INF] * N
    que = [(0, s)]
    dist[s] = 0
    while que:
        c, v = heappop(que)
        if dist[v] < c:
            continue
        for t, cost in G[v]:
            if dist[v] + cost < dist[t]:
                dist[t] = dist[v] + cost
                heappush(que, (dist[t], t))
dijkstra(n,graph,0)
if dist[n-1]==INF:
  print(-1)
else:print(dist[n-1])

Submission status: Accepted

Solution code:
import sys
import heapq
input = sys.stdin.readline
heapify, push, pop = heapq.heapify, heapq.heappush, heapq.heappop

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

_lrc.sort()


def chker(n, m, lrc):
    dst = [float('inf')] * n
    dst[0] = 0
    q = [(0, 0)]

    cnt = 0
    for i in range(n):
        while q:
            d, r = q[0]
            if i <= r:
                break
            pop(q)
        else:
            print(-1)
            return

        dst[i] = d
        while cnt < m and lrc[cnt][0] == i:
            l, r, c = lrc[cnt]
            push(q, (d + c, r))
            cnt += 1

    print(dst[-1])


chker(_n, _m, _lrc)