C++ Coding Test Course, Minimum Cost Calculation

Hello! In this post, we will discuss a C++ algorithm problem titled Finding Minimum Cost. This problem presents a good opportunity to explore algorithmic concepts that are useful for finding optimal solutions in various situations. Through this article, we will delve into problem analysis, algorithm selection, code implementation, testing, and optimization methods in detail.

Problem Description

We have several cities and roads between them. Each road has a specific cost. Our goal when traveling between the given cities is to find the minimum travel cost from the starting city to the target city. This can be solved using Dijkstra’s algorithm.

Problem Definition

Here is the mathematical definition of the problem:

The number of given cities n (between 1 and 10,000)
The number of paths m (between 1 and 100,000)
Each path is given in the form of u, v, cost. This means that the cost to travel from city u to city v is cost.
The starting city start and the target city end are provided.

Input


    n m
    u1 v1 cost1
    u2 v2 cost2
    ...
    um vm costm
    start end

Output

Output the minimum cost to reach the target city. If it is not possible to reach, output -1.

Algorithm Selection

This problem involves finding the shortest path in a weighted graph, which can be effectively solved using the representative algorithm Dijkstra’s algorithm. Dijkstra’s algorithm has a time complexity of O((n + m) log n), making it efficient even under maximum input conditions.

Dijkstra’s Algorithm Overview

The basic idea of Dijkstra’s algorithm is as follows:

Select the starting node and initialize the distance to this node as 0.
Initialize the distance to all other nodes as infinity.
Calculate the distance to the nodes adjacent to the current node, updating the distance if a shorter distance is found.
Repeat this process until all nodes have been visited.

Problem Solving Process

Step 1: Problem Analysis

We need to construct a graph from the given input and a data structure to store the cost information for each city. We will use an adjacency list.

Step 2: Code Implementation


#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <limits>

using namespace std;

const int INF = numeric_limits<int>::max();

vector<pair<int, int>> graph[10001];

void dijkstra(int start, int n) {
    vector<int> cost(n + 1, INF);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    cost[start] = 0;
    pq.push(make_pair(0, start));

    while (!pq.empty()) {
        int currentCost = pq.top().first;
        int currentNode = pq.top().second;
        pq.pop();

        if (currentCost > cost[currentNode]) continue;

        for (auto &edge : graph[currentNode]) {
            int nextNode = edge.first;
            int nextCost = edge.second;

            if (cost[currentNode] + nextCost < cost[nextNode]) {
                cost[nextNode] = cost[currentNode] + nextCost;
                pq.push(make_pair(cost[nextNode], nextNode));
            }
        }
    }

    for (int i = 1; i <= n; ++i) {
        if (cost[i] == INF) {
            cout << -1 << endl;  // unreachable case
        } else {
            cout << cost[i] << endl;
        }
    }
}

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

    for (int i = 0; i < m; ++i) {
        int u, v, cost;
        cin >> u >> v >> cost;
        graph[u].push_back(make_pair(v, cost));
        graph[v].push_back(make_pair(u, cost));  // assuming bidirectional roads
    }

    int start, end;
    cin >> start >> end;

    dijkstra(start, n);
    
    return 0;
}

Step 3: Code Testing

Test the input through the code above. For example, you can test using the following input:

The above input represents a case with 5 cities and 6 roads, where the starting city is 1 and the target city is 5. In this case, the algorithm should output the method to reach from city 1 to city 5 with the minimum cost.

Step 4: Optimization

Dijkstra’s algorithm is typically implemented using a Priority Queue; however, in limited cases, a Fibonacci Heap might be used. In this article, we demonstrated a simple and efficient implementation using a standard Priority Queue.

Conclusion

In this session, we examined how to solve the minimum cost problem using C++. We understood the principles of Dijkstra’s algorithm and how to apply it to real problems. This will be helpful in preparing for coding tests.

Continue learning and practicing how to solve more algorithm problems. Thank you!