CSES - Investigation

 Problem Link

Time Complexity: O(N + M log M)
Algorithm used: Dijkstra, DP (partly)

The problem statement is quite straightforward: a series of M one-way flight routes are described, each connecting one city to another city and having a cost. You want to travel from city 1 to city N. Find:

1. minimum price of such a route
2. the number of minimum-price routes
3. maximum number of flights in a minimum-price route
4. minimum number of flights in a maximum-price route

It is guaranteed that at least 1 path exists from city 1 to city N

This can be modelled as a graph problem, where the cities are the nodes and the flights are the edges. Each flight has a cost and only travels in one direction, so the graph is weighted and directed. A minimum price route to node N means the shortest path to node N.

Since the route must start from city 1 and the edges are weighted, some form of Dijkstra's algorithm must be applied. The key point is to collect the data for the 4 answers while running the Dijkstra's. 

Maintain 4 arrays: one for the shortest path to reach node i (dis), one for the number of ]shortest paths to node i (sp), one for the minimum number of flights on a shortest path to node i (min_flight) and one for the maximum number of flights on a shortest path to node i (max_flight).

While running Dijkstra's, if we come across a shorter path to node i than any other path that we have come across till now, we need to update the 4 arrays.

1.  The length of the shortest path to i can be updated as done in standard Dijkstra's.
2. the number of shortest paths is updated to 1, since this is the first time a route of this length has been found.
3. the minimum number of nodes traversed by the shortest path to this node is the minimum number of nodes traversed by the shortest path to the parent city + 1 (add 1 to account for the current city).
4. the maximum number of nodes traversed by the shortest path to this node is the minimum number of nodes traversed by the shortest path to the parent city + 1 (add 1 to account for the current city).

What if a new path to node i matches its shortest path? This means than another shortest path has been found, so we need to update 3 arrays:

1. The length of the shortest path remains the same, so no need to update this array.
2. The number of shortest paths increases by 1 (while adding a path, modulo the sum by 10⁹ + 7).
3. the minimum number of nodes traversed by the shortest path to reach node i could be the previous minimum calculated or the number of nodes traversed by the current shortest path. So, the answer is the minimum of the two.
4. the maximum number of nodes traversed by the shortest path to reach node i could be the previous maximum calculated or the number of nodes traversed by the current shortest path. So, the answer is the maximum of the two.

Finally, print the values stored at the N location in each of the four arrays as your final answer.

Code

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e5 + 1;

vector <vector <pair <int, int>>> adj(MAX_N);

vector <long long> min_flight(MAX_N), max_flight(MAX_N), sp(MAX_N),

    dis(MAX_N);

const int mod = 1000000007;

int main()

{

    int n, m;

    cin >> n >> m;

    // read input

    for (int i = 0; i < m; i++){

        int a, b, w;

        cin >> a >> b >> w;

        adj[a].push_back({b, w});

    }

    // diijkstra's

    priority_queue <pair <long long, int>> pq;

    pq.push({0, 1});

    vector <bool> processed(n+1);

    dis[1] = 0;

    sp[1] = 1;

    min_flight[1] = max_flight[1] = 0;

    while (!pq.empty()){

        int a = pq.top().second;

        pq.pop();

        if (processed[a])

            continue;

        processed[a] = true;

        for (auto i : adj[a]){

            int b, w;

            tie(b, w) = i;

            if (dis[a] + w < dis[b]){

                // a new shortest path has been found

                dis[b] = dis[a] + w;

                sp[b] = sp[a];

                min_flight[b] = min_flight[a] + 1;

                max_flight[b] = max_flight[a] + 1;

                pq.push({-dis[b], b});

            } else if (dis[a] + w == dis[b]){

                // another shortest path has been found

                sp[b] = (sp[a] + sp[b]) % mod;

                min_flight[b] = min(min_flight[b], min_flight[a] + 1);

                max_flight[b] = max(max_flight[b], max_flight[a] + 1);

            }

        }

    }

    cout << dis[n] << ' ' << sp[n] << ' ' << min_flight[n] << ' ' <<

        max_flight[n] << '\n';

}