## TL;DR

Given a number of vertices `N` and a list of weighted directed edges in a directed acyclic graph (each edge is written as `[start, end, weight]` where `from < to`), compute the weight of the shortest path from vertex `0` to vertex `N - 1`.  If there is no such path, return `-1`.

## Background

A weighted DAG is a directed acyclic graph where each edge has a weight associated with it:













1
5
3
1
5




A
B
C
D


In this example, the shortest path from A to D is given by A -> B -> D, which has a total weight of 4.

Finding shortest distances in DAGs is made easier by the fact that the nodes can be _linearized:_ they can be given an order `A1, A2, ..., An` such that edges only point forward (that is, there are no edges from `Aj` to `Ai` when `j > i`).  In the example above, the two possible linear orderings are `A, B, C, D` and `A, C, B, D.`














1

1
5
5
3





A
B
C
D


## Your Task

Given a number `N` (indicating a graph with vertices `0, 1, ..., N-1`) and a list of weighted edges `[start, end, weight]` for a DAG, where `start < end` for each edge, find the weight (a.k.a. length) of the shortest path from node `0` to node `N-1`.

For example, if the input is

```
N = 4
edgeList = [
  [0, 1, 1], [0, 2, 5], [0, 3, 5], [1, 3, 3], [2, 3, 1]
]
```

then we have the graph depicted above (with `0 = A`, `1 = B`, etc.) and the answer is `4`.

If there is no path from node `0` to node `N-1`, return `-1`.

## Notes and Warnings

**Precondition:** `N` will always be greater than 1, and edge weights will always be positive integers.  There may be multiple edges going between two nodes.

**Warning:** You will probably need to use a dynamic programming solution if you want your solution to run fast enough not to time out--that's the whole point of this kata!


However, a well-written general shortest-path algorithm such as Dijkstra's Algorithm may also be fast enough to past the soak tests.  (The reason is that the dividing line between linear and linearithmic time is hard to define and depends on a variety of external factors, so the kata's tests err on the safe side.)

Difficulty: introductory

Starter code:

def shortest(N, edgeList):
	

Solutions:
import heapq
from collections import defaultdict

def shortest(N, edge):
    ver, inf = defaultdict(list), 10**10
    for e in edge: ver[e[0]].append(e[1:])

    dist = {i:inf for i in range(N)}
    dist[0], pq = 0, []
    heapq.heappush(pq, [dist[0], 0])
    while pq: 
        u_dis, u_node = heapq.heappop(pq)
        if u_dis == dist[u_node]:
            for v in ver[u_node]:
                v_node = v[0]
                v_wei = v[1]
                if dist[u_node] + v_wei < dist[v_node]:
                    dist[v_node] = dist[u_node] + v_wei
                    heapq.heappush(pq, [dist[v_node], v_node])
    return -1 if dist[N-1] == inf else dist[N-1]

def shortest(n, edges):
    m = [0] + [float('inf')] * (n-1)
    for start, end, weight in sorted(edges):
        if m[start] == float('inf'): continue
        m[end] = min(m[start] + weight, m[end])
    return -1 if m[-1] == float('inf') else m[-1]

def shortest(N, edgeList):
    
    edgeList.sort(key= lambda x: x[0])
    path_values = [None for _ in range(N)]
    path_values[0] = 0
        
    for edge in edgeList:

        if path_values[edge[0]] != None: # If the node value is 0, then we can not use it as a base to go further.
            new_val = edge[2] + path_values[edge[0]]
        
            if path_values[edge[1]] == None:
                path_values[edge[1]] = new_val
            else:
                path_values[edge[1]] = min(path_values[edge[1]], new_val)
    
    if path_values[-1] == None: # no path goes to the end
        return -1
    else:
        return path_values[-1]

def shortest(N, edges):
    
    path = [0]+[float('inf')]*(N-1)
    for start,end,weight in sorted(edges):
        if path[start]==-1: continue
        path[end] = min(path[start]+weight, path[end] )
        
        
        
    return -1 if path[-1]==float('inf') else path[-1]

from collections import defaultdict


INFINITY = 2 ** 80


def shortest(N, edgeList):
    edges = defaultdict(list)
    for (fro, to, weight) in edgeList:
        edges[fro].append((to, weight))
    
    dist_dp = [INFINITY] * N
    dist_dp[0] = 0
    
    for i in range(N):
        for (to, w) in edges[i]:
            dist_dp[to] = min(dist_dp[to], dist_dp[i] + w)
    
    return -1 if dist_dp[N - 1] >= INFINITY else dist_dp[N - 1]

from collections import defaultdict
from heapq import heappop, heappush
from typing import List, Tuple


def shortest(N: int, edgeList: List[Tuple[int, int, int]]) -> int:
    graph = defaultdict(list)
    for v, u, e in edgeList:
        graph[v].append((u, e))

    pathes = defaultdict(lambda: float('inf'), {0: 0})

    queue = [(0, 0)]
    while queue:
        cost, v = heappop(queue)

        if v == N - 1:
            return cost

        for u, e in graph[v]:
            new_cost = cost + e
            if new_cost < pathes[u]:
                pathes[u] = new_cost
                heappush(queue, (new_cost, u))

    return -1

def shortest(n, edges):
    m = [0] + [-1] * (n-1)
    for start, end, weight in sorted(edges):
        if m[start] == -1: continue
        m[end] = min(m[start] + weight,
                     m[end] == -1 and float('inf') or m[end])
    return m[-1]

def shortest(N, es):
    ee = [[] for _ in range(N)]
    for f, t, w in es:
        ee[f].append((t, w))
    dd = [0x7f7f7f7f for _ in range(N)]
    f = [False for _ in range(N)]
    dd[0] = 0
    q = [0]
    f[0] = True
    while len(q) > 0:
        k = q.pop()
        f[k] = False
        for t, w in ee[k]:
            if dd[t] > dd[k] + w:
                dd[t] = dd[k] + w
                if not f[t]:
                    q.append(t)
                    f[t] = True
    return -1 if dd[N - 1] == 0x7f7f7f7f else dd[N - 1]

def shortest(N, edgeList):
    import math
    edgeList.sort(key=lambda x: x[0])
    path_length = [math.inf for _ in range(N)]
    path_length[0] = 0
        
    for start, end, weight in edgeList:
#         each edge is written as [start, end, weight] where from < to więc to działa, 
#         ale gdyby taki warunek nie był prawdziwy to np.
#         shortest(5, [(0,2,0), (0,3,1), (2,1,0), (3,4,1), (1,4,0)]) zwracałoby 2, zamiast 0
        if path_length[start] == math.inf:
            continue
        path_length[end] = min(path_length[start] + weight, path_length[end])
    
    result = path_length[N-1]
    return result if result is not math.inf else -1





# def shortest(N, edgeList):
#     import math, heapq, collections
#     edges = collections.defaultdict(lambda:collections.defaultdict(lambda:math.inf))
#     path_length = [math.inf for _ in range(N)]
#     path_length[0] = 0
#     for start, end, weight in edgeList:
#         edges[start][end] = min(weight, edges[start][end])
#     h = [(0,0)]
#     visited = set()
#     heapq.heapify(h)
#     while h:
#         sum, start = heapq.heappop(h)
#         if start == N-1: return sum
#         if start in visited: continue
#         for end, weight in edges[start].items():
#             if end in visited: continue
#             if sum + weight < path_length[end]:
#                 path_length[end] = sum + weight
#                 heapq.heappush(h, (sum+weight, end))
#         visited.add(start)
#     return -1


from collections import defaultdict
from heapq import *

def shortest(N, edges):
    '''Same as def dijkstra(edges, f, t)'''
    f=0;t=N-1
    g = defaultdict(list)
    for l,r,c in edges:
        g[l].append((c,r))

    q, seen, mins = [(0,f,())], set(), {f: 0}
    while q:
        (cost,v1,path) = heappop(q)
        if v1 not in seen:
            seen.add(v1)
            path = (v1, path)
            if v1 == t: return cost#,path

            for c, v2 in g.get(v1, ()):
                if v2 in seen: continue
                prev = mins.get(v2, None)
                next = cost + c
                if prev is None or next < prev:
                    mins[v2] = next
                    heappush(q, (next, v2, path))

    return -1 #float("inf")