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: Runtime Error

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 998244353
inf = float('INF')

#A
def A():
    n = II()
    n -= 1
    print(n // 2)
    return

#B
def combination_mod(n, k, mod=mod):
    """ power_funcを用いて(nCk) mod p を求める """ 
    """ nCk = n!/((n-k)!k!)を使用 """

    from math import factorial
    if n < 0 or k < 0 or n < k: return 0
    if n == 0 or k == 0: return 1
    a = factorial(n) % mod
    b = factorial(k) % mod
    c = factorial(n - k) % mod
    return (a * pow(b, mod - 2, mod) * pow(c, mod - 2, mod)) % mod
    

def B():
    n = II()
    d = LI()
    dic = defaultdict(int)
    if d[0] != 0:
        print(0)
        return
    for di in d[1:]:
        dic[di] += 1
    ans = 1
    di = list(dic.items())
    di.sort()
    if di[0][0] != 1:
        print(0)
        return
    for i in range(len(di) - 1):
        if di[i][0] != di[i + 1][0] - 1:
            print(0)
            return
    be = 1
    for _, b in di:
        ans *= pow(be, b, mod)
        be = b
        ans %= mod
    print(ans)
    return
class BinaryIndexedTree:
    # http://hos.ac/slides/20140319_bit.pdf
    def __init__(self, size):
        """
        :param int size:
        """
        self.bit = [0 for _ in range(size)]
        self.size = size

    def add(self, i, w):
        """
        i番目にwを加える
        :param int i:
        :param int w:
        :return:
        """
        x = i + 1
        while x <= self.size:
            self.bit[x - 1] += w
            x += x & -x
        return

    def sum(self, i):
        """
        [0,i]の合計
        :param int i:
        :return:
        """
        res = 0
        x = i + 1
        while x > 0:
            res += self.bit[x - 1]
            x -= x & -x
        return res

    def search(self, x):
        """
        二分探索。和がx以上となる最小のインデックス(>= 1)を返す
        :param int x:
        :return :
        """
        i = 1
        s = 0
        step = 1 << (self.size.bit_length() - 1)
        while step:
            if i + step <= self.size and s + self.bit[i + step - 1] < x:
                i += step
                s += self.bit[i - 1]
            step >>= 1
        return i

    def __len__(self):
        return self.size
#C
def C():
    n = II()
    a = LI()
    b = LI()
    tmp = [inf, inf]
    res = None
    for i in range(n):
        if tmp[0] >= b[i] - a[i] >= 0 and b[i] < tmp[1]:
            res = i
            tmp = [b[i] - a[i], b[i]]
    if res == None:
        print("No")
        return
    del a[res]
    del b[res]
    a.sort()
    b.sort()
    ans = 0
    bit = BinaryIndexedTree(b[-1] + 1)
    n -= 1
    for i in range(n):
        tmp = bisect_right(a, b[i]) - bit.sum(b[i])
        bit.add(b[i],1)
        if tmp <= 0:
            print("No")
            return
    print("Yes")

    return

from heapq import heappush, heappop

def Dijkstra(num, start, vedge):

    dist = [float("inf") for i in range(num)]
    dist[0] = 0
    for i in range(n):
        du = dist[i]
        l = i
        for k, j in vedge[i]:
            if dist[j] <= du + k:
                continue
            for j in range(l + 1, j + 1):
                if dist[j] > du + k:
                    dist[j] = du + k
                    l = j
    return dist


#D
def D():
    n, m = LI()
    dist = [[] for i in range(n)]
    for _ in range(m):
        l, r, c = LI_()
        c += 1
        dist[l].append([c, r])
    for i in range(n):
        dist[i].sort()
    dist = Dijkstra(n, 0, dist)
    print(dist[n - 1] if dist[n - 1] != inf else -1)
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path
N, M = map(int, input().split())
g = np.full((N, N), float('INF'))
for i in range(M):
    l, r, c = map(int, input().split())
    g[l-1: r, l-1:r] = np.where(g[l-1: r, l-1:r] > c, c, g[l-1: r, l-1:r])
    # print(g)
g = np.where(g == float('INF'), 0, g)
# print(g, shortest_path(g))
ans = shortest_path(g)[0][-1]
if ans == float('INF'):
    print(-1)
else:
    print(int(ans))

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
lrc=[list(map(int,input().split())) for _ in range(m)]
lrc.sort(key=lambda x:x[0])
rr=1
ll=10**5+1
for l,r,c in lrc:
    if rr<l:
        print(-1)
        exit()
    ll=min(l,ll)
    rr=max(rr,r)

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

lrc.sort(key=lambda x:x[1])
l=[1]
r=[1]
c=[0]
for i in range(m):
    ll,rr,cc=lrc[i]
    l.append(ll)
    r.append(rr)
    c.append(cc)

import bisect

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

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

lrc.sort(key=lambda x:x[0])
l=[1]
r=[1]
c=[0]
for i in range(m):
    ll,rr,cc=lrc[i]
    l.append(ll)
    r.append(rr)
    c.append(cc)

import bisect

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

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

ans=min(ans1,ans2)
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
import collections
import sys
N, M  = map(int, input().split(' '))
graph = np.ones((N, N)) + 1e9
for i in range(M):
    L, R, C = map(int, input().split(' '))
    for s in range(L-1, R-1):
        for t in range(s+1, R):
            if graph[s, t] > C:
                graph[s, t] = C
Ds = np.zeros(N)
for i in range(N-2, -1, -1):
    Ds[i] = (Ds[i+1:] + graph[i, i+1:]).min()
print(int(Ds[0]) if Ds[0] <= 1e9 else -1)

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path
N, M = map(int, input().split())
g = np.full((N, N), float('INF'))
for i in range(M):
    l, r, c = map(int, input().split())
    g[l-1: r, l-1:r] = np.where(g[l-1: r, l-1:r] > c, c, g[l-1: r, l-1:r])
    # print(g)
ans = shortest_path(g)[0][-1]
if ans == float('INF'):
    print(-1)
else:
    print(int(ans))

Submission status: Runtime Error

Solution code:
import math
N, M = map(int, input().split())
AtCodermap = [[math.inf for i in range(N)] for j in range(N)]
for i in range(M):
    L, R, C = map(int, input().split())
    AtCodermap[L-1][R-1] = C

Rootnum = N #ますめのかず
Distance = [math.inf] * Rootnum #それぞれのマスまでの初期値からの距離 最初は全部無限
NotYet = [math.inf]* Rootnum    #未探索の升目リスト　未探索は無限　探索済みは１になる
HowToGo = [[] for ssf in range(len(AtCodermap))]   #スタート地点からその場所への移動方法
print(Distance)
stert = 0 #スタート地点　整数で表す
Distance[stert] = 0 #初期値の場所は０

for Di in range(Rootnum):#すべてのマス探索するため
    SortedDistance = sorted(Distance)
    for Dj in range(len(AtCodermap[0])): #距離の小さいところから探索
        print(Distance)
        MASU = Distance.index(SortedDistance[Dj])
        MASUnum = MASU%len(AtCodermap[0])

        if NotYet[MASU] != 1: #きょりが小さくても探索済みなら意味がない　ここで調べるところをけってい　Djが今いるところ
            for Dk in range(len(AtCodermap[0])):#ここから探索
                print(Distance[Dk])
                if Distance[MASU] + AtCodermap[MASUnum][Dk] < Distance[Dk]: #もし今までの距離より今いるところから行ったほうが近かったら更新
                    Distance[Dk] = AtCodermap[MASUnum][Dk] + Distance[MASU] #距離を更新

    NotYet[MASU] = 1 #調べ終わったため探索済みに変更

if Distance[N-1] == math.inf:
    print(-1)
else:
    print(Distance[N-1])

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path
N, M = map(int, input().split())
g = np.full((N, N), float('INF'))
for i in range(M):
    l, r, c = map(int, input().split())
    g[l-1: r, l-1:r] = np.where(g[l-1: r, l-1:r] > c, c, g[l-1: r, l-1:r])
    # print(g)
ans = shortest_path(g, indices=[0])[0][-1]
if ans == float('INF'):
    print(-1)
else:
    print(int(ans))

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import sys

import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


def search(i, d, w, reached, costs, N, moves):
    if reached[i]:
        return
    if i == N-1:
        costs.append(moves)

    for j in w[i]:
        reached[i] = True
        moves += d[i, j]
        search(j, d, w, reached, costs, N, moves)
        moves -= d[i, j]
        reached[i] = False


def main():
    N, M = map(int, readline().split())
    d = np.full([N, N], 10**10)
    # w = np.full([N, N], -1)  # 1 => i, j がつながっている
    w = [[] for _ in range(N)]

    for i in range(M):
        L, R, C = map(int, readline().split())
        L, R = L-1, R-1
        for j in range(L+1, R+1):
            d[L, j] = min(d[L, j], C)
            w[L].append(j)

    for i in range(len(w)):
        w[i] = list(set(w[i]))
    reached = [False]*N
    costs = []
    moves = 0
    search(0, d, w, reached, costs, N, moves)

    if costs == []:
        print(-1)
    else:
        print(min(costs))


main()

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
lrc=[list(map(int,input().split())) for _ in range(m)]
lrc.sort(key=lambda x:x[0])
lrc.sort(key=lambda x:x[1])

l=[1]
r=[1]
c=[0]
for i in range(m):
    ll,rr,cc=lrc[i]
    l.append(ll)
    r.append(rr)
    c.append(cc)

if l[0]!=1:
    print(-1)
    exit()



import bisect

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


x=bisect.bisect_left(r,n)
ans=min(c[x:])


lrc.sort(key=lambda x:x[0])
ll=lrc[0][0]
rr=lrc[0][1]
for i in range(1,m):
    l,r,c=lrc[i]
    if rr<l:
        print(-1)
        exit()
    rr=r

print(ans)

Submission status: Runtime Error

Solution code:
import sys
import math
from heapq import heappop, heappush

N, M = [int(x) for x in sys.stdin.readline().split()]
LRC = []
for _ in range(M):
    LRC.append([int(x) for x in sys.stdin.readline().split()])

dist = [math.inf] * N
dist[0] = 0

routes = [None] * N
for i in range(N):
    routes[i] = [math.inf] * N

for l, r, c in LRC:
    for i in range(l - 1, r - 1):
        for j in range(i + 1, r):
            routes[i][j] = min(routes[i][j], c)
            routes[j][i] = min(routes[j][i], c)

q = []
heappush(q, (dist[0], 0))

while q:
    d, u = heappop(q)
    if dist[u] < d:
        continue
    for i, w in enumerate(routes[u]):
        t = d + w
        if t < dist[i]:
            dist[i] = t
            heappush(q, (t, i))

if dist[-1] == math.inf:
    print(-1)
else:
    print(dist[-1])

Submission status: Runtime Error

Solution code:
input()
A=list(map(int,input().split()))
B=list(map(int,input().split()))
c=0
for i in range(len(A)):
    if A[i]<=B[i]:
        c+=1
    if sorted(A)[i]>sorted(B)[i]:
        print("No")
        exit()

print("Yes" if c>2 else "No")

Submission status: Runtime Error

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]

flag = False

for i in range(N):
    if(B[i] - A[i] >= 0):
        flag = True
        break


A.sort()
B.sort()
for i in range(N):
    if(B[i] - A[i] < 0):
        flag = False
        break

if(flag):
    print("Yes")
else:
    print("No")