Problem:


Score : 600 points

Problem Statement

We have N points numbered 1 to N arranged in a line in this order.

Takahashi decides to make an undirected graph, using these points as the vertices.
In the beginning, the graph has no edge. Takahashi will do M operations to add edges in this graph.
The i-th operation is as follows:

The operation uses integers L_i and R_i between 1 and N (inclusive), and a positive integer C_i. For every pair of integers (s, t) such that L_i \leq s < t \leq R_i, add an edge of length C_i between Vertex s and Vertex t.

The integers L_1, ..., L_M, R_1, ..., R_M, C_1, ..., C_M are all given as input.

Takahashi wants to solve the shortest path problem in the final graph obtained. Find the length of the shortest path from Vertex 1 to Vertex N in the final graph.

Constraints

2 \leq N \leq 10^5

1 \leq M \leq 10^5

1 \leq L_i < R_i \leq N

1 \leq C_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N M
L_1 R_1 C_1
:
L_M R_M C_M

Output

Print the length of the shortest path from Vertex 1 to Vertex N in the final graph.
If there is no shortest path, print -1 instead.

Sample Input 1

4 3
1 3 2
2 4 3
1 4 6

Sample Output 1

5

We have an edge of length 2 between Vertex 1 and Vertex 2, and an edge of length 3 between Vertex 2 and Vertex 4, so there is a path of length 5 between Vertex 1 and Vertex 4.

Sample Input 2

4 2
1 2 1
3 4 2

Sample Output 2

-1

Sample Input 3

10 7
1 5 18
3 4 8
1 3 5
4 7 10
5 9 8
6 10 5
8 10 3

Sample Output 3

28



Sample input:
4 3
1 3 2
2 4 3
1 4 6


Sample output:
5

Submission status: Wrong Answer

Solution code:
import 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
    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()
print(dijkstra_result[-1])

Submission status: Wrong Answer

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

tree_list = [[] for _ in range(N) ]
for _ in range(M):
    L,R,C = map(int,input().split(' '))
    tree_list[R-1].append([C,L-1])
dp = [1000000000000] * N
dp[N-1] = 0
current_num = -1
flag = False
if len(tree_list[N-1]) > 0: 
    for i in reversed(range(N)):
        if dp[i] == 1000000000000:
            flag = True
            break
        current_start_paths = tree_list[i]
        if len(current_start_paths) > 0:
            current_start_paths.sort()
            for path in current_start_paths:
                if dp[path[1]] > dp[i] + path[0]:
                    for j in range(path[1],i):
                        if (dp[i] + path[0]) < dp[j]:
                            dp[j] = dp[i] + path[0]
                        else:
                            break
    if dp[0] == 1000000000000 or flag:
        print(-1)
    else:
        print(dp[0])
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
INF = 2**31 - 1

class RangeMinimunQuery:
    def __init__(self, n):
        self._n = 1 << n.bit_length()
        self._d = [INF] * (2 * self._n)

    def update(self, k, v):
        k += self._n
        self._d[k] = v
        k >>= 1
        while k:
            self._d[k] = min(self._d[2 * k], self._d[2 * k + 1])
            k >>= 1

    def query(self, l, r):
        l += self._n
        r += self._n + 1
        res = INF
        while l < r:
            if l & 1:
                res = min(res, self._d[l])
                l += 1
            if r & 1:
                r -= 1
                res = min(res, self._d[r])
            l >>= 1
            r >>= 1
        return res

    def a(self, k):
        return self._d[k + self._n]

    def d(self):
        return self._d[self._n:]

n, m = map(int, raw_input().split())
edges = []
for _ in range(m):
    edges.append(map(int, raw_input().split()))
edges.sort(key=lambda x: x[1])

segtree = RangeMinimunQuery(n + 1)
segtree.update(1, 0)
for l, r, c in edges:
    cost = min(segtree.query(l, r - 1) + c, segtree.a(r))
    segtree.update(r, cost)

if segtree.a(n) == INF:
    print -1
else:
    print segtree.a(n)

Submission status: Wrong Answer

Solution code:
INF = 2**31 - 1

class RangeMinimunQuery:
    def __init__(self, n):
        self._n = 1 << n.bit_length()
        self._d = [INF] * (2 * self._n)

    def update(self, k, v):
        k += self._n
        self._d[k] = v
        k >>= 1
        while k:
            self._d[k] = min(self._d[2 * k], self._d[2 * k + 1])
            k >>= 1

    def query(self, l, r):
        l += self._n
        r += self._n + 1
        res = INF
        while l < r:
            if l & 1:
                res = min(res, self._d[l])
                l += 1
            if r & 1:
                r -= 1
                res = min(res, self._d[r])
            l >>= 1
            r >>= 1
        return res

    def a(self, k):
        return self._d[k + self._n]

    def d(self):
        return self._d[self._n:]

n, m = map(int, raw_input().split())
edges = []
for _ in range(m):
    edges.append(map(int, raw_input().split()))
edges.sort()

segtree = RangeMinimunQuery(n + 1)
segtree.update(1, 0)
for l, r, c in edges:
    cost = min(segtree.query(l, r - 1) + c, segtree.a(r))
    segtree.update(r, cost)

if segtree.a(n) == INF:
    print -1
else:
    print segtree.a(n)

Submission status: Wrong Answer

Solution code:
INF = 2**31 - 1

class RangeMinimunQuery:
    def __init__(self, n):
        self._n = 1 << n.bit_length()
        self._d = [INF] * (2 * self._n)

    def update(self, k, v):
        k += self._n
        self._d[k] = v
        k >>= 1
        while k:
            self._d[k] = min(self._d[2 * k], self._d[2 * k + 1])
            k >>= 1

    def query(self, l, r):
        l += self._n
        r += self._n + 1
        res = INF
        while l < r:
            if l & 1:
                res = min(res, self._d[l])
                l += 1
            if r & 1:
                r -= 1
                res = min(res, self._d[r])
            l >>= 1
            r >>= 1
        return res

    def a(self, k):
        return self._d[k + self._n]

    def d(self):
        return self._d[self._n:]

n, m = map(int, raw_input().split())
edges = []
for _ in range(m):
    edges.append(map(int, raw_input().split()))
edges.sort()

segtree = RangeMinimunQuery(n)
segtree.update(1, 0)
for l, r, c in edges:
    cost = min(segtree.query(l, r - 1) + c, segtree.a(r))
    segtree.update(r, cost)

if segtree.a(n) == INF:
    print -1
else:
    print segtree.a(n)

Submission status: Wrong Answer

Solution code:
INF = 2**31 - 1

class RangeMinimunQuery:
    def __init__(self, n):
        self._n = 1 << n.bit_length()
        self._d = [INF] * (2 * self._n)

    def update(self, k, v):
        k += self._n
        self._d[k] = v
        k >>= 1
        while k:
            self._d[k] = min(self._d[2 * k], self._d[2 * k + 1])
            k >>= 1

    def query(self, l, r):
        l += self._n
        r += self._n
        res = INF
        while l < r:
            if l & 1:
                res = min(res, self._d[l])
                l += 1
            if r & 1:
                r -= 1
                res = min(res, self._d[r])
            l >>= 1
            r >>= 1
        return res

    def a(self, k):
        return self._d[k + self._n]

    def d(self):
        return self._d[self._n:]

n, m = map(int, raw_input().split())
edges = []
for _ in range(m):
    edges.append(map(int, raw_input().split()))
edges.sort()

segtree = RangeMinimunQuery(n)
segtree.update(1, 0)
for l, r, c in edges:
    cost = min(segtree.query(l, r) + c, segtree.a(r))
    segtree.update(r, cost)

if segtree.a(n) == INF:
    print -1
else:
    print segtree.a(n)

Submission status: Wrong Answer

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

tree_list = [[] for _ in range(N) ]
for _ in range(M):
    L,R,C = map(int,input().split(' '))
    tree_list[R-1].append([C,L-1])
    #tree_list.append([R-1,L-1,C])
    '''
    if (R-1) in tree_list[L-1].keys():
        tree_list[L-1][R-1] = min(tree_list[L-1][R-1],C)
    else:
        tree_list[L-1][R-1] = C
    '''
#tree_list.sort(reverse=True)
dp = [1000000000] * N
dp[N-1] = 0
current_num = -1
flag = False
if len(tree_list[N-1]) > 0: 
    for i in reversed(range(N)):
        if dp[i] == 1000000000:
            flag = True
            break
        current_start_paths = tree_list[i]
        if len(current_start_paths) > 0:
            current_start_paths.sort()
            for path in current_start_paths:
                if dp[path[1]] > dp[i] + path[0]:
                    for j in range(path[1],i):
                        if (dp[i] + path[0]) < dp[j]:
                            dp[j] = dp[i] + path[0]
                        else:
                            break 

    '''
    for path in tree_list:
        if dp[path[0]] == 1000000000:
            flag = True
            break
        if dp[path[1]] > dp[path[0]] + path[2]:
            for i in range(path[1],path[0]):
                if (dp[path[0]] + path[2]) < dp[i]:
                    dp[i] = dp[path[0]] + path[2]
                else:
                    break 
    '''
    if dp[0] == 1000000000 or flag:
        print(-1)
    else:
        print(dp[0])
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
INF = 2**31 - 1

class RangeMinimunQuery:
    def __init__(self, n):
        self._n = 1
        while self._n < n:
             self._n *= 2
        self._d = [INF] * (2 * self._n)

    def update(self, k, v):
        k += self._n - 1
        self._d[k] = v
        while k >= 0:
            k = (k - 1) / 2
            self._d[k] = min(self._d[2 * k + 1], self._d[2 * k + 2])

    def query(self, l, r):
        l += self._n - 1
        r += self._n - 1
        res = INF
        while l < r:
            if l & 1 == 0:
                res = min(res, self._d[l])
                l += 1
            if r & 1:
                r -= 1
                res = min(res, self._d[r])
            l >>= 1
            r >>= 1
        return res

    def a(self, k):
        return self._d[k + self._n - 1]

    def d(self):
        return self._d[self._n - 1:]

n, m = map(int, raw_input().split())
edges = []
for _ in range(m):
    edges.append(map(int, raw_input().split()))
edges.sort()

segtree = RangeMinimunQuery(n)
segtree.update(0, 0)
for l, r, c in edges:
    s = l - 1
    e = r - 1
    cost = segtree.query(s, e) + c
    if cost < segtree.a(e):
        segtree.update(e, cost)

if segtree.a(n - 1) == INF:
    print -1
else:
    print segtree.a(n - 1)

Submission status: Wrong Answer

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

tree_list = [[] for _ in range(N) ]
for _ in range(M):
    L,R,C = map(int,input().split(' '))
    tree_list[R-1].append([C,L-1])
    #tree_list.append([R-1,L-1,C])
    '''
    if (R-1) in tree_list[L-1].keys():
        tree_list[L-1][R-1] = min(tree_list[L-1][R-1],C)
    else:
        tree_list[L-1][R-1] = C
    '''
#tree_list.sort(reverse=True)
dp = [1000000000] * N
dp[N-1] = 0
current_num = -1
flag = False

for i in reversed(range(N)):
    if dp[i] == 1000000000:
        flag = True
        break
    current_start_paths = tree_list[i]
    if len(current_start_paths) > 0:
        current_start_paths.sort()
        for path in current_start_paths:
            if dp[path[1]] > dp[i] + path[0]:
                for j in range(path[1],i):
                    if (dp[i] + path[0]) < dp[j]:
                        dp[j] = dp[i] + path[0]
                    else:
                        break 

'''
for path in tree_list:
    if dp[path[0]] == 1000000000:
        flag = True
        break
    if dp[path[1]] > dp[path[0]] + path[2]:
        for i in range(path[1],path[0]):
            if (dp[path[0]] + path[2]) < dp[i]:
                dp[i] = dp[path[0]] + path[2]
            else:
                break 
'''
if dp[0] == 1000000000 or flag:
    print(-1)
else:
    print(dp[0])

Submission status: Wrong Answer

Solution code:
INF = 2**31 - 1

class RangeMinimunQuery:
    def __init__(self, n):
        self._n = 1
        while self._n < n:
             self._n *= 2
        self._d = [INF] * (2 * self._n)

    def update(self, k, v):
        k += self._n - 1
        self._d[k] = v
        while k >= 0:
            k = (k - 1) / 2
            self._d[k] = min(self._d[2 * k + 1], self._d[2 * k + 2])

    def query(self, l, r):
        if r <= l:
            return INF
        l += self._n - 1
        r += self._n - 2
        res = INF
        while r - l > 1:
            if l & 1 == 0:
                res = min(res, self._d[l])
            if r & 1 == 1:
                res = min(res, self._d[r])
                r -= 1
            l = l / 2
            r = (r -1) / 2
        if l == r:
            res = min(res, self._d[l])
        else:
            res = min(min(res, self._d[l]), self._d[r])
        return res

    def a(self, k):
        return self._d[k + self._n - 1]

n, m = map(int, raw_input().split())
edges = []
for _ in range(m):
    edges.append(map(int, raw_input().split()))
edges.sort()

segtree = RangeMinimunQuery(n)
segtree.update(0, 0)
for l, r, c in edges:
    s = l - 1
    e = r - 1
    cost = segtree.query(s, e + 1) + c
    if cost < segtree.a(e):
        segtree.update(e, cost)

if segtree.a(n - 1) == INF:
    print -1
else:
    print segtree.a(n - 1)

Submission status: Wrong Answer

Solution code:
import sys
def input():
	return sys.stdin.readline()[:-1]

INF = 10**30

class Rmin():
	def __init__(self, size):
		#the number of nodes is 2n-1
		self.n = 1
		while self.n < size:
			self.n *= 2
		self.node = [INF] * (2*self.n-1)

	def Access(self, x):
		return self.node[x+self.n-1]

	def Update(self, x, val):
		x += self.n-1
		self.node[x] = min(val, self.node[x])
		while x > 0:
			x = (x-1)//2
			self.node[x] = min(self.node[2*x+1], self.node[2*x+2])
		return

	#[l, r)
	def Get(self, l, r):
		L, R = l+self.n, r+self.n
		s = INF
		while L<R:
			if R & 1:
				R -= 1
				s = min(s, self.node[R-1])
			if L & 1:
				s = min(s, self.node[L-1])
				L += 1
			L >>= 1
			R >>= 1
		return s

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

seg.sort(reverse=True)
ans = [INF for _ in range(n)]
ans[0] = 0
tree = Rmin(n)

for i in range(1, n):
	while seg and seg[-1][0] == i-1:
		l, r, c = seg.pop()
		tree.Update(r, c + ans[l])
	ans[i] = tree.Get(i, n)

if ans[n-1] > 10**10:
	print(-1)
else:
	print(ans[n-1])

Submission status: Wrong Answer

Solution code:
n,m,*t=map(int,open(0).read().split())
d=[0,0]+[1e18]*n
for l,r,c in sorted(zip(*[iter(t)]*3)):
  for i in range(r,l,-1):
    if d[l]+c<d[i]:d[i]=d[l]+c
    else:break
print(d[-2]%1e18or-1)

Submission status: Wrong Answer

Solution code:
n,m,*t=map(int,open(0).read().split())
d=[0,0]+[9e9]*n
for l,r,c in sorted(zip(*[iter(t)]*3)):
 for i in range(r,l,-1):
  if d[l]+c<d[i]:d[i]=d[l]+c
  else:break
print(-(d[-2]>9e9)or d[-2])

Submission status: Wrong Answer

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

import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

N,M = map(int,readline().split())
LRC = np.array(read().split(),np.int64)

fr = []
to = []
wt = []

# i+1 -> i に長さ 0 の辺を貼る
fr.append(np.arange(2,N+1))
to.append(np.arange(1,N))
wt.append(np.zeros(N-1,np.int64))
# L,R に長さ C の辺を貼る
fr.append(LRC[::3])
to.append(LRC[1::3])
wt.append(LRC[2::3])

fr = np.concatenate(fr)
to = np.concatenate(to)
wt = np.concatenate(wt)

graph = csr_matrix((wt,(fr,to)),(N+1,N+1))

x = dijkstra(graph,indices=1)[-1]

if x == np.inf:
    answer = -1
else:
    answer = int(x+.5)

print(answer)

Submission status: Wrong Answer

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

import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

N,M = map(int,readline().split())
LRC = np.array(read().split(),np.int64)

fr = []
to = []
wt = []

# i+1 -> i に長さ 0 の辺を貼る
fr.append(np.arange(2,N+1))
to.append(np.arange(1,N))
wt.append(np.zeros(N-1))
# L,R に長さ C の辺を貼る
fr.append(LRC[::3])
to.append(LRC[1::3])
wt.append(LRC[2::3])

fr = np.concatenate(fr)
to = np.concatenate(to)
wt = np.concatenate(wt)

graph = csr_matrix((wt,(fr,to)),(N+1,N+1))

x = dijkstra(graph,indices=1)[-1]

if x == np.inf:
    answer = -1
else:
    answer = int(x+.5)

print(answer)

Submission status: Wrong Answer

Solution code:
from scipy.sparse import*
n,*t=map(int,open(0).read().split())
x=[i-1for i in t]
*u,=range(n)
a=csgraph.dijkstra(csr_matrix(([0]*~-n+t[3::3],(u[1:]+x[1::3],u[:-1]+x[2::3])),(n,n)),1,0)[-1]
print(int(a)if a<1e18else-1)

Submission status: Wrong Answer

Solution code:
from scipy.sparse import*
n,*t=map(int,open(0).read().split())
*u,=range(n+1)
a=csgraph.dijkstra(csr_matrix(([0]*n+t[3::3],(u[1:]+t[1::3],u[:-1]+t[2::3])),[n+1]*2),1,1)[n]
print(int(a)if a<1e18else-1)

Submission status: Wrong Answer

Solution code:
from scipy.sparse import*
n,*t=map(int,open(0).read().split())
*u,=range(n+1)
a=csgraph.dijkstra(csr_matrix((t[3::3]+[0]*n,(t[1::3]+u[1:],t[2::3]+u[:-1])),[n+1]*2),1,(1))[n]
print(int(a)if a<1e18else-1)

Submission status: Wrong Answer

Solution code:
from scipy.sparse import*
n,*t=map(int,open(0).read().split())
*u,=range(1,n+1)
a=csgraph.dijkstra(csr_matrix((t[3::3]+[0]*~-n,(t[1::3]+u[1:],t[2::3]+u[:-1])),[n+1]*2),1,(1))[n]
print(int(a)if a<1e30else-1)

Submission status: Wrong Answer

Solution code:
from scipy.sparse import*
n,*t=map(int,open(0).read().split())
*u,=range(1,n+1)
a=csgraph.dijkstra(csr_matrix((t[3::3]+[0]*~-n,(t[1::3]+u[1:],t[2::3]+u[:-1])),[n+1]*2),1,(1))[n]
print(int(a)if a<1e18else-1)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
lrc = []
for _ in range(m):
  lrc.append(list(map(int,input().split())))
import heapq
heapq.heapify(lrc)
arrive = [[1,0]]
heapq.heapify(arrive)
#print(arrive)
while True:
  if arrive == []:
    print(-1)
    break
  point,dis = heapq.heappop(arrive)
  if point == n:
    print(dis)
    break
  while True:
    if lrc == []:
      break
    if lrc[0][0] <= point:
      l,r,c = heapq.heappop(lrc)
      if r > point:
        if arrive != []:
          if dis+c > arrive[0][1]:
            continue
        heapq.heappush(arrive,[r,dis+c])
    else:
      break

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush
N, M = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(M)]

edges = [[] for _ in range(N)]
for u, v, c in X:
    edges[u - 1].append((v - 1, c))
    
for i in range(N - 1):
    edges[i + 1].append((i, 0))

INF = 10 ** 9 + 7
d = [INF] * N
d[0] = 0

pq = []
heappush(pq, (0, 0))

while len(pq) > 0:
    cost, u = heappop(pq)
    for v, c in edges[u]:            
        if d[v] > d[u] + c:
            d[v] = d[u] + c
            heappush(pq, (d[v], v))
            
print(d[-1] if d[-1] != INF else -1)

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush
N, M = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(M)]

edges = [[] for _ in range(N)]
for u, v, c in X:
    edges[u - 1].append((v - 1, c))
    
for i in range(N - 1):
    edges[i + 1].append((i, 0))

INF = 10 ** 9 + 7
d = [INF] * N
d[0] = 0

visited = [False] * N
visited[0] = True

# Priority queue (cost, node)
pq = []
heappush(pq, (0, 0))

while len(pq) > 0:
    cost, u = heappop(pq)
    visited[u] = True
    
    # Search nodes connected with target node 'u'
    for v, c in edges[u]:
        if visited[v]:
            continue
        if d[v] > d[u] + c:
            d[v] = d[u] + c
            heappush(pq, (d[v], v))
            
print(d[-1] if d[-1] != INF else -1)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
LRC = sorted([list(map(int, input().split())) for i in range(M)], key=lambda x: (x[0], x[1]))

inf = 10**6
dp = [inf] * N
dp[0] = 0

for l, r, c in LRC:
    for i in range(r, l, -1):
        if dp[i-1] > dp[l-1] + c:
            dp[i-1] = dp[l-1] + c
        else:
            break

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

Submission status: Wrong Answer

Solution code:
import sys


class AlgSegmentTreeMin:
    def __init__(self, n, default_value):
        self.Nelem = n
        self.default_value = default_value
        self.size = 1 << (n.bit_length())
        self.data = [self.default_value] * (2 * self.size)

    def update(self, i, x):
        i += self.size
        self.data[i] = x
        i >>= 1
        while i:
            x = self.data[i + i]
            y = self.data[i + i + 1]
            self.data[i] = min(x, y)
            i >>= 1

    def get_value(self, left, right):
        left += self.size
        right += self.size + 1
        x = self.default_value
        while left < right:
            if left & 1:
                y = self.data[left]
                x = min(x, y)
                left += 1
            if right & 1:
                right -= 1
                y = self.data[right]
                x = min(x, y)
            left >>= 1
            right >>= 1
        return x


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, readline().split()))
    stree = AlgSegmentTreeMin(n, 10 ** 15)
    lrc = [list(map(int, readline().split())) for _ in range(m)]
    lrc.sort()
    stree.update(0, 0)
    for l, r, c in lrc:
        l -= 1
        r -= 1
        now = stree.get_value(r, r)
        if now > c:
            tm = stree.get_value(l, r)
            if tm + c < now:
                stree.update(r, tm + c)
    mt = stree.get_value(n-1, n)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import bisect
N,M=[int(s) for s in input().split()]
ls=[[int(s) for s in input().split()] for i in range(M)]
ls.sort()
#print(ls)
path=[[1,0]]
t=1
flag=0
for e in ls:
  if e[0]>t:
    print(-1)
    flag=1
    break
  else:
    k = bisect.bisect_left(path,[e[0],0])
    l = [e[1],path[k][1]+e[2]]
    k = bisect.bisect_left(path,l)
    path.insert(k, l)
    t=max([t,e[1]])
#    print(path)
if flag==0:
#  print(path)
  k=bisect.bisect_left(path,[N,0])
  print(path[k][1])

Submission status: Wrong Answer

Solution code:
import heapq
import sys

input = sys.stdin.readline

def dijkstra_heap(s,edge):
    #始点sから各頂点への最短距離
    d = [float("inf")] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d
#########################
n,w = map(int,input().split())
edge = [[] for i in range(n)]
#隣接リスト edge[i]:[コスト,行先]
for i in range(n-1):
    edge[i+1].append([0, i])

for i in range(w):
    x,y,z = map(int,input().split())
    edge[x-1].append([z,y-1])
    edge[y-1].append([z,x-1])
print(dijkstra_heap(0, edge)[-1])

Submission status: Wrong Answer

Solution code:
class Rmq:
    # 平方分割
    # 値を変更すると元のリストの値も書き換わる
    def __init__(self, a, sqrt_n=500):
        from itertools import zip_longest
        self.n = len(a)
        self.sqrt_n = sqrt_n
        self.layer1 = a
        self.layer0 = [min(values) for values in zip_longest(*[iter(a)]*sqrt_n, fillvalue=float("inf"))]

    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
        idx //= self.sqrt_n
        self.layer0[idx] = min(self.layer0[idx], val)

    def chmin(self, idx, val):
        if self.layer1[idx] > val:
            self.set_value(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
import sys

def main():
    N, M = map(int, input().split())
    LRC = list(zip(*[iter(map(int, sys.stdin.read().split()))]*3))
    LRC.sort(key=itemgetter(0))
    idx_LRC = 0
    inf = 1 << 60

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

main()

Submission status: Wrong Answer

Solution code:
import sys


class AlgSegmentTreeMin:
    def __init__(self, n, default_value):
        self.Nelem = n
        self.default_value = default_value
        self.size = 1 << (n.bit_length())
        self.data = [default_value] * (2 * self.size)

    def update(self, i, x):
        i += self.size
        self.data[i] = x
        i >>= 1
        while i:
            x = self.data[i + i]
            y = self.data[i + i + 1]
            self.data[i] = min(x, y)
            i >>= 1

    def get_value(self, left, right):
        left += self.size
        right += self.size + 1
        x = self.default_value
        while left < right:
            if left & 1:
                y = self.data[left]
                x = min(x, y)
                left += 1
            if right & 1:
                right -= 1
                y = self.data[right]
                x = min(x, y)
            left >>= 1
            right >>= 1
        return x


def solve():
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read
    mod = 10 ** 9 + 7
    n, m = list(map(int, input().split()))
    stree = AlgSegmentTreeMin(n, 10 ** 15)
    mm = map(int, read().split())
    lrc = zip(mm, mm, mm)
    stree.update(0, 0)
    for l, r, c in lrc:
        l -= 1
        r -= 1
        tm = stree.get_value(l, r)
        now = stree.get_value(r, r)
        tm = tm + c if tm + c < now else now
        stree.update(r, tm)
    mt = stree.get_value(n-1, n)
    print(mt if mt != stree.default_value else -1)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
tail = []
head = []
cost = []
for _ in range(m):
  l, r, c = map(int, input().split())
  tail.append(l - 1)
  head.append(r - 1)
  cost.append(c)
tail += list(range(1, n))
head += list(range(n - 1))
cost += [0] * (n - 1)

inf = sum(cost) + 1
dp = [0] + [inf] * (n - 1)
act = 0
unexplr = [False] + [True] * (n - 1)
while unexplr[-1]:
  for edge in range(m + n - 1):
    to = head[edge]
    if act == tail[edge] and unexplr[to] and dp[to] > dp[act] + cost[to]:
      dp[to] = dp[act] + cost[to]
  short = inf
  for vertex in range(n):
    if unexplr[vertex] and dp[vertex] < short:
      act = vertex
      short = dp[vertex]
  unexplr[act] = False
if dp[-1] < inf:
  print(dp[-1])
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
INF = 1000000
Glaph = [[INF for j in range(N)] for i in range(N)]
for i in range(1,N):
  Glaph[i][i-1] = 0
for i in range(M):
  l,r,c = map(int,input().split())
  l -= 1
  r -= 1
  
  if Glaph[l][r] == 0 or Glaph[l][r] > c:
    Glaph[l][r] = c

def djikstra(s,g,Glaph):
  INF = 1000000
  done = [ 0  for i in range(N)]
  cost = [INF for i in range(N)]
    
  done[s] = 1
  cost[s] = 0
  done_node = s
  
  for i in range(N):
    min = INF
   
    k = done_node 
    for j in range(N):
      if done[j] == 0:
        
        if cost[j] > cost[k] + Glaph[k][j]:
          cost[j] = cost[k] + Glaph[k][j]
        
        if min > cost[j]:
          min = cost[j]
          done_node = j
     
    done[done_node] = 1
    if done_node == g:
      break
  
  if cost[g] == INF:
    return(-1)
  else:
    return cost[g]
 
      
print(djikstra(0,N-1,Glaph))

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
Glaph = [[0 for j in range(N)] for i in range(N)]
for i in range(M):
  l,r,c = map(int,input().split())
  l -= 1
  r -= 1
  for s in range(l,r):
    if Glaph[s][s+1] == 0 or Glaph[s][s+1] > c:
      Glaph[s][s+1] = c

def djikstra(s,g,Glaph):
  INF = 1000000
  done = [ 0  for i in range(N)]
  cost = [INF for i in range(N)]
    
  done[s] = 1
  cost[s] = 0
  done_node = s
  
  for i in range(N):
    min = INF
   
    k = done_node 
    for j in range(N):
      if done[j] == 0:
        
        if Glaph[k][j] != 0 and cost[j] > cost[k] + Glaph[k][j]:
          cost[j] = cost[k] + Glaph[k][j]
        
        if min > cost[j]:
          min = cost[j]
          done_node = j
     
    done[done_node] = 1
    if done_node == g:
      break
  
  if cost[g] == INF:
    return(-1)
  else:
    return cost[g]
 
      
print(djikstra(0,N-1,Glaph))

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
Glaph = [[0 for j in range(N)] for i in range(N)]
for i in range(M):
  l,r,c = map(int,input().split())
  l -= 1
  r -= 1
  
  if Glaph[l][r] == 0 or Glaph[l][r] > c:
    Glaph[l][r] = c
    Glaph[r][l] = c


def djikstra(s,g,Glaph):
  INF = 1000000
  done = [ 0  for i in range(N)]
  cost = [INF for i in range(N)]
    
  done[s] = 1
  cost[s] = 0
  done_node = s
  
  for i in range(N):
    min = INF
   
    k = done_node 
    for j in range(N):
      if done[j] == 0:
        
        if Glaph[k][j] != 0 and cost[j] > cost[k] + Glaph[k][j]:
          cost[j] = cost[k] + Glaph[k][j]
        
        if min > cost[j]:
          min = cost[j]
          done_node = j
     
    done[done_node] = 1
    if done_node == g:
      break
  
  if cost[g] == INF:
    return(-1)
  else:
    return cost[g]
 
      
print(djikstra(0,N-1,Glaph))