Code Logo

Delivery Fee with Dijkstra

Published at22 Apr 2026
Created by
Dijkstra Easy 0 views
Like0

A courier company stores one-way delivery routes between hubs. Each route is written as [from, to, cost], which means you may travel from one hub to another by paying that cost.

You are given the number of hubs, the list of routes, a starting hub, and a destination hub. Return the smallest total delivery fee needed to reach the destination.

Because the routes are directed, a road from 0 to 2 does not automatically mean you can go back from 2 to 0. You must follow the direction exactly as listed.

If no valid directed path exists, return -1. This problem is another clean Dijkstra exercise, but the graph is one-way instead of two-way.

Example Input & Output

Example 1
Input
n = 3, routes = [], start = 1, destination = 1
Output
0
Explanation

If the start and destination are the same hub, the minimum cost is zero.

Example 2
Input
n = 5, routes = [[0,1,5], [0,2,2], [2,1,1], [1,3,4], [2,3,7], [3,4,3]], start = 0, destination = 4
Output
10
Explanation

The cheapest route is 0 -> 2 -> 1 -> 3 -> 4 with total cost 10.

Example 3
Input
n = 4, routes = [[0,1,4], [2,3,5]], start = 0, destination = 3
Output
-1
Explanation

The destination is unreachable because the graph has no directed chain from 0 to 3.

Algorithm Flow

Recommendation Algorithm Flow for Delivery Fee with Dijkstra
Recommendation Algorithm Flow for Delivery Fee with Dijkstra

Solution Approach

The algorithm is still Dijkstra's algorithm, but the graph should be built as a directed adjacency list. That means each route [u, v, cost] is added only from u to v.

Once the graph is built, keep a distance array filled with very large values and set the start hub to distance 0. Use a min-priority queue to always process the hub with the smallest known cost so far.

Whenever you pop one hub, try all outgoing routes. If reaching a neighbor through the current hub gives a cheaper total fee, update the distance and push the new state into the queue.

The important detail in this version is not to add the reverse edge by mistake. The routes are directional, so the algorithm must respect that rule all the way through.

The runtime is O((n + m) log n) for m routes, which is the standard complexity for Dijkstra with a priority queue.

Best Answers

java
import java.util.*;

class Solution {
    public int delivery_fee_with_dijkstra(int n, int[][] routes, int start, int destination) {
        List<int[]>[] graph = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int[] route : routes) {
            graph[route[0]].add(new int[]{route[1], route[2]});
        }

        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        pq.offer(new int[]{0, start});

        while (!pq.isEmpty()) {
            int[] state = pq.poll();
            int cost = state[0];
            int node = state[1];
            if (cost != dist[node]) {
                continue;
            }
            if (node == destination) {
                return cost;
            }
            for (int[] edge : graph[node]) {
                int next = edge[0];
                int newCost = cost + edge[1];
                if (newCost < dist[next]) {
                    dist[next] = newCost;
                    pq.offer(new int[]{newCost, next});
                }
            }
        }
        return -1;
    }
}