Dijkstra? (Codeforces 20C)
Tags: Others, shortest paths

You are given a weighted undirected graph. The vertices are enumerated from 1 to n. Your task is to find the shortest path between the vertex 1 and the vertex n.

Input: The first line contains two integers n and m (2 ≤ n ≤ 105, 0 ≤ m ≤ 105), where n is the number of vertices and m is the number of edges. Following m lines contain one edge each in form ai, bi and wi (1 ≤ ai, bi ≤ n, 1 ≤ wi ≤ 106), where ai, bi are edge endpoints and wi is the length of the edge.It is possible that the graph has loops and multiple edges between pair of vertices.

Output: Write the only integer -1 in case of no path. Write the shortest path in opposite case. If there are many solutions, print any of them.


Sample Inputs:
5 6
1 2 2
2 5 5
2 3 4
1 4 1
4 3 3
3 5 1

5 6
1 2 2
2 5 5
2 3 4
1 4 1
4 3 3
3 5 1

Sample Outputs:
1 4 3 5

1 4 3 5

Solution (Python):
import heapq

def dijkstra():
    (x, z) = map(int, input().split())
    adjacentes = [[] for _ in range(x + 1)]
    for _ in range(z):
        (a, b, w) = map(int, input().split())
        adjacentes[b].append((w, a))
        adjacentes[a].append((w, b))
    dist = [float('inf')] * (x + 1)
    prev = [0] * (x + 1)
    dist[1] = 0
    queue = [(0, 1)]
    while queue:
        (d, v) = heapq.heappop(queue)
        if d != dist[v]:
            continue
        for (w, to) in adjacentes[v]:
            if dist[v] + w < dist[to]:
                dist[to] = dist[v] + w
                prev[to] = v
                heapq.heappush(queue, (dist[to], to))
    if dist[x] == float('inf'):
        print(-1)
    else:
        path = []
        v = x
        while v != 0:
            path.append(v)
            v = prev[v]
        path.reverse()
        print(' '.join(map(str, path)))
dijkstra()

Solution (Python):
import heapq

def dijkstra(n, adj):
    INF = float('inf')
    dist = [INF] * n
    prev = [-1] * n
    dist[0] = 0
    pq = [(0, 0)]
    while pq:
        (d, u) = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for (v, w) in adj[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                prev[v] = u
                heapq.heappush(pq, (dist[v], v))
    if dist[n - 1] == INF:
        return -1
    path = []
    curr = n - 1
    while curr != 0:
        path.append(curr + 1)
        curr = prev[curr]
    path.append(1)
    return path[::-1]

def main():
    (n, m) = map(int, input().split())
    adj = [[] for _ in range(n)]
    for _ in range(m):
        (a, b, w) = map(int, input().split())
        a -= 1
        b -= 1
        adj[a].append((b, w))
        adj[b].append((a, w))
    path = dijkstra(n, adj)
    if path == -1:
        print(-1)
    else:
        print(' '.join((str(vertex) for vertex in path)))
if __name__ == '__main__':
    main()

Solution (Python):
import heapq

def dijkstra():
    (n, m) = map(int, input().split())
    adj = [[] for _ in range(n + 1)]
    for _ in range(m):
        (a, b, w) = map(int, input().split())
        adj[a].append((w, b))
        adj[b].append((w, a))
    dist = [float('inf')] * (n + 1)
    prev = [0] * (n + 1)
    dist[1] = 0
    queue = [(0, 1)]
    while queue:
        (d, v) = heapq.heappop(queue)
        if d != dist[v]:
            continue
        for (w, to) in adj[v]:
            if dist[v] + w < dist[to]:
                dist[to] = dist[v] + w
                prev[to] = v
                heapq.heappush(queue, (dist[to], to))
    if dist[n] == float('inf'):
        print(-1)
    else:
        path = []
        v = n
        while v != 0:
            path.append(v)
            v = prev[v]
        path.reverse()
        print(' '.join(map(str, path)))
dijkstra()