Shortest Paths with Non-Negative Edge Weights

C++

Copy
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

constexpr long long BIG = 1e18;  // We can't use LLONG_MAX because of overflow

int main() {

Java

Copy
import java.io.*;
import java.util.*;

public class ShortestRoutesII {
	// We can't use Long.MAX_VALUE because of overflow
	private static final long BIG = (long)1e18;

	public static void main(String[] args) {
		Kattio io = new Kattio();

Python

Copy
# 1e18 is used instead of float('inf') for performance reasons
BIG = int(1e18)

n, m, q = map(int, input().split())

min_dist = [[BIG] * n for _ in range(n)]

for _ in range(m):
	a, b, c = map(int, input().split())
	a, b = a - 1, b - 1

C++

Recall from the second prerequisite module that we can use greater<> to make the top element of a priority queue the least instead of the greatest. Alternatively, you can negate distances before placing them into the priority queue.

Copy
#include <bits/stdc++.h>
using namespace std;

int main() {
	int n, m;
	cin >> n >> m;

	// Adjacency list of (neighbour, edge weight)
	vector<vector<pair<int, int>>> neighbors(n);
	for (int i = 0; i < m; i++) {

Java

Copy
import java.io.*;
import java.util.*;

public class ShortestRoutesI {
 	Code Snippet: Pair Class (Click to expand)

	public static void main(String[] args) {
		Kattio io = new Kattio();

		int n = io.nextInt();

Python

Copy
import heapq

n, m = map(int, input().split())

# Adjacency list of (neighbour, edge weight)
graph = [[] for _ in range(n)]
for i in range(m):
	a, b, c = map(int, input().split())
	graph[a - 1].append((b - 1, c))