Dijkstra and Bellman–Ford both compute shortest paths from a source vertex, but they rely on different assumptions about edge weights. Dijkstra requires nonnegative weights. Bellman–Ford permits negative edges and can detect a negative cycle reachable from the source.

We will use a reusable Dijkstra template, apply it to an emergency-rescue problem, and then work through Bellman–Ford with a directed graph containing negative edges.

1. Dijkstra’s algorithm

Dijkstra maintains a tentative distance for each vertex. At each step, it selects the unvisited vertex with the smallest distance, finalizes that distance, and uses its outgoing edges to improve neighboring distances.

The finalization step depends on nonnegative edge weights. Once a vertex has the smallest tentative distance, a path through a later vertex cannot make it cheaper. A negative edge invalidates that argument.

1.1 An adjacency-matrix template

The matrix below stores cost[u][v], with INF meaning that no edge exists. Set the diagonal to zero. For an undirected graph, store each edge in both directions. Vertices are numbered from 0 to n - 1.

#pragma once
#include <limits>
#include <stdexcept>
#include <vector>

namespace matrix_paths {
using Distance = long long;
constexpr Distance INF = std::numeric_limits<Distance>::max() / 4;
using Matrix = std::vector<std::vector<Distance>>;

// INF means no edge. Finite weights and path costs must be below INF.
inline std::vector<Distance> dijkstra(const Matrix& cost, int source) {
    const int n = static_cast<int>(cost.size());
    if (source < 0 || source >= n)
        throw std::invalid_argument("invalid source");
    for (const auto& row : cost) {
        if (static_cast<int>(row.size()) != n)
            throw std::invalid_argument("matrix must be square");
        for (auto weight : row)
            if (weight < 0 || weight > INF)
                throw std::invalid_argument("invalid nonnegative edge weight");
    }
    std::vector<Distance> distance(n, INF);
    std::vector<bool> visited(n, false);
    distance[source] = 0;
    for (int step = 0; step < n; ++step) {
        int u = -1;
        for (int v = 0; v < n; ++v)
            if (!visited[v] && (u == -1 || distance[v] < distance[u])) u = v;
        if (u == -1 || distance[u] == INF) break;
        visited[u] = true;
        for (int v = 0; v < n; ++v) {
            if (visited[v] || cost[u][v] == INF) continue;
            if (distance[u] >= INF - cost[u][v])
                throw std::overflow_error("candidate distance reaches INF");
            const auto candidate = distance[u] + cost[u][v];
            if (candidate < distance[v]) distance[v] = candidate;
        }
    }
    return distance;
}
}  // namespace matrix_paths

Save the complete template as dijkstra_matrix.hpp and call matrix_paths::dijkstra(cost, source) after building the matrix. A returned INF means that the vertex is unreachable. The loop stops when no unvisited reachable vertex remains, so an uninitialized vertex index is never used.

The template takes O(n²) time and space. That is convenient for small dense graphs and for the rescue problem below, where n ≤ 500. For a large sparse graph, an adjacency list with a priority queue avoids scanning all possible edges. Finite edge weights and candidate path sums must remain below the template’s INF sentinel; the code rejects invalid weights and out-of-range candidate sums.

1.2 Example: Emergency rescue

Problem: PAT 1003 — Emergency.

A map contains cities connected by roads. Each city has a number of rescue teams, and each road has a length. Starting at city C1, we must reach city C2 along a shortest route. Among those shortest routes, we want the largest total number of rescue teams that can be gathered along the way.

The output has two values: the number of distinct shortest routes from C1 to C2, and the largest rescue-team total along one of them.

Input

The first line contains four integers:

N M C1 C2

N ≤ 500 is the number of cities, numbered 0 through N - 1; M is the number of roads. The next line contains N rescue-team counts. Each of the following M lines contains a b L, describing an undirected road of length L between cities a and b. At least one route exists between C1 and C2.

The counting recurrence below assumes strictly positive road lengths. Every predecessor on a shortest route then has a smaller distance than its successor, so its route count is known before it contributes to the successor.

Output

Print the number of shortest routes and the maximum rescue-team total, separated by one space.

Sample input

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

Sample output

2 4

There are two shortest routes from city 0 to city 2: the direct road and the route through city 1. Both have total length 2. The route through city 1 collects 1 + 2 + 1 = 4 rescue teams.

Approach

Along with distance[v], maintain ways[v], the number of shortest routes currently known, and best_teams[v], the largest rescue-team total among those routes.

For an edge from the selected city u to v:

• If the candidate distance is smaller, replace distance[v], copy ways[u] into ways[v], and set the team total to best_teams[u] + teams[v].
• If the distance is equal, add ways[u] to ways[v] and keep the larger team total.

Initialize the source with distance 0, one route, and its own rescue-team count. These updates preserve Dijkstra’s distance computation while tracking the two quantities the problem asks for.

Complete solution

#include <algorithm>
#include <iostream>
#include <limits>
#include <stdexcept>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, source, target;
    if (!(cin >> n >> m >> source >> target)) return 0;
    const long long INF = numeric_limits<long long>::max() / 4;
    vector<long long> teams(n), best_teams(n, 0), distance(n, INF);
    for (auto& count : teams) cin >> count;
    vector<vector<long long>> cost(n, vector<long long>(n, INF));
    for (int i = 0; i < n; ++i) cost[i][i] = 0;
    for (int i = 0; i < m; ++i) {
        int a, b;
        long long length;
        cin >> a >> b >> length;
        if (length <= 0 || length >= INF)
            throw invalid_argument("road lengths must be positive and below INF");
        cost[a][b] = cost[b][a] = min(cost[a][b], length);
    }
    vector<unsigned long long> ways(n, 0);
    vector<bool> visited(n, false);
    distance[source] = 0;
    best_teams[source] = teams[source];
    ways[source] = 1;
    for (int step = 0; step < n; ++step) {
        int u = -1;
        for (int v = 0; v < n; ++v)
            if (!visited[v] && (u == -1 || distance[v] < distance[u])) u = v;
        if (u == -1 || distance[u] == INF) break;
        visited[u] = true;
        for (int v = 0; v < n; ++v) {
            if (visited[v] || cost[u][v] == INF) continue;
            if (distance[u] >= INF - cost[u][v])
                throw overflow_error("candidate distance reaches INF");
            const auto candidate = distance[u] + cost[u][v];
            if (candidate < distance[v]) {
                distance[v] = candidate;
                ways[v] = ways[u];
                best_teams[v] = best_teams[u] + teams[v];
            } else if (candidate == distance[v]) {
                if (ways[v] > numeric_limits<unsigned long long>::max() - ways[u])
                    throw overflow_error("shortest-path count exceeds 64 bits");
                ways[v] += ways[u];
                best_teams[v] = max(best_teams[v], best_teams[u] + teams[v]);
            }
        }
    }
    cout << ways[target] << ' ' << best_teams[target] << '\n';
}

The standalone C++ solution can be compiled with:

c++ -std=c++17 -O2 emergency.cpp -o emergency
./emergency < input.txt

The matrix keeps the shortest road between a pair of cities, treating a route as a sequence of cities. The route counter uses an unsigned 64-bit integer and reports overflow instead of silently wrapping. Rescue-team totals must fit a signed 64-bit integer. Zero-weight roads require separate reasoning for route counting even though they are valid for computing ordinary Dijkstra distances.

2. Bellman–Ford

2.1 Edge relaxation

Bellman–Ford works with negative edge weights by repeatedly relaxing the edges. For an edge u → v of weight w, relaxation means checking whether a known route to u followed by that edge improves the current distance to v:

if distance[u] is finite:
    distance[v] = min(distance[v], distance[u] + w)

The route to u costs 5 and the edge u → v costs −2. Their combined cost, 3, improves v’s tentative distance from 9 to 3.

A shortest path can be chosen with at most n - 1 edges if no reachable negative cycle exists. Scanning every edge n - 1 times is therefore sufficient. In-place updates may propagate through several edges in one pass; the bound does not require exactly one edge of progress per pass.

A complete pass with no changes allows an early stop. If an edge can still improve a distance after the usual passes, a negative cycle is reachable from the source. Repeating that cycle can decrease the cost without bound for vertices reachable from it. A disconnected negative cycle does not affect this source’s distances.

2.2 Example: Shortest paths with negative edges

Problem: Lanqiao shortest-path exercise.

Given a directed graph with n vertices and m edges, some of which have negative weights, compute the shortest distances from vertex 1 to every other vertex. Vertices are numbered 1 through n. The graph has no negative cycle, and every vertex is reachable from every other vertex.

Input

The first line contains n m. Each of the next m lines contains u v w, describing an edge from u to v with weight w.

For the full input, −10,000 ≤ w ≤ 10,000.

Output

Print n - 1 lines. Line i contains the shortest distance from vertex 1 to vertex i + 1.

Sample input

3 3
1 2 -1
2 3 -1
3 1 2

Sample output

-1
-2

The distance to vertex 2 is −1; following 1 → 2 → 3 gives distance −2 to vertex 3. The cycle through all three vertices has total weight 0, so it does not violate the no-negative-cycle assumption.

Approach

Store the directed edges in a list. Set the source distance to zero and all other distances to INF. During each pass, relax an edge only when its source is reachable. Stop after a pass with no changes, or after n - 1 passes.

Use long long for distances. Under the stated vertex, edge, and weight bounds, the finite values produced by these passes remain well within that type’s range. Checking reachability before addition avoids treating INF plus a negative edge weight as a real path.

Complete solution

#include <iostream>
#include <limits>
#include <vector>
using namespace std;

struct Edge { int from, to; long long weight; };

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<Edge> edges(m);
    for (auto& edge : edges) cin >> edge.from >> edge.to >> edge.weight;
    const long long INF = numeric_limits<long long>::max() / 4;
    vector<long long> distance(n + 1, INF);
    distance[1] = 0;
    for (int pass = 1; pass < n; ++pass) {
        bool changed = false;
        for (const auto& edge : edges) {
            if (distance[edge.from] == INF) continue;
            const auto candidate = distance[edge.from] + edge.weight;
            if (candidate < distance[edge.to]) {
                distance[edge.to] = candidate;
                changed = true;
            }
        }
        if (!changed) break;
    }
    for (const auto& edge : edges) {
        if (distance[edge.from] != INF &&
            distance[edge.from] + edge.weight < distance[edge.to]) {
            cout << "NEGATIVE CYCLE\n";
            return 0;
        }
    }
    for (int vertex = 2; vertex <= n; ++vertex) {
        if (distance[vertex] == INF) cout << "UNREACHABLE\n";
        else cout << distance[vertex] << '\n';
    }
}

The standalone Bellman–Ford solution follows the problem’s input and output format. It also reports NEGATIVE CYCLE or UNREACHABLE if input violates the corresponding graph assumptions; neither branch is taken for a valid problem instance.

c++ -std=c++17 -O2 bellman_ford.cpp -o bellman_ford
./bellman_ford < input.txt

Bellman–Ford takes O(nm) time in the worst case and O(n + m) space. With n = 20,000 and m = 200,000, a full run approaches four billion edge examinations. Negative-edge support explains why the algorithm applies, but does not guarantee that this bound fits a particular time limit. Early stopping improves some cases without changing the worst case.