Solution: Dijkstra?

We can implement Dijkstra's Shortest Path algorithm to find the shortest distances between node $1$ and node $n$ . To find the path that yields the shortest path between nodes $1$ and $n$ , we should backtrack from node $n$ and determine if a given node should be in the path using the shortest distance array. However, when the shortest distance from node 1 to node $n$ is $\infty$ , then we should print $-1$ .

Time Complexity: $\mathcal{O}(N\log M)$

C++

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using vi = vector<int>;
using pi = pair<ll, ll>;

#define f first
#define s second
#define all(x) begin(x), end(x)

Python

import sys
from typing import Dict, List
import heapq


# Returns a list where list[ind] is the node through which we visit node ind
def dijkstra(graph: Dict[int, List[int]], source: int) -> List[int]:
	vis = [False] * (len(graph) + 1)
	dist = [sys.maxsize] * (len(graph) + 1)
	par = [-1] * (len(graph) + 1)

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum