Hello! In this post, we will discuss a C++ algorithm problem titled Finding Minimum Cost<\/strong>. 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.<\/p>\n 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.<\/p>\n Here is the mathematical definition of the problem:<\/p>\n Output the minimum cost to reach the target city. If it is not possible to reach, output This problem involves finding the shortest path in a weighted graph, which can be effectively solved using the representative algorithm Dijkstra’s algorithm<\/strong>. Dijkstra’s algorithm has a time complexity of The basic idea of Dijkstra’s algorithm is as follows:<\/p>\n 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.<\/p>\n Test the input through the code above. For example, you can test using the following input:<\/p>\n 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.<\/p>\n Dijkstra\u2019s 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.<\/p>\n 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.<\/p>\n Continue learning and practicing how to solve more algorithm problems. Thank you!<\/p>\n <\/body><\/p>\n","protected":false},"excerpt":{"rendered":"Problem Description<\/h2>\n
Problem Definition<\/h3>\n
\n
n<\/code> (between 1 and 10,000)<\/li>\nm<\/code> (between 1 and 100,000)<\/li>\nu<\/code>, v<\/code>, cost<\/code>. This means that the cost to travel from city u<\/code> to city v<\/code> is cost<\/code>.<\/li>\nstart<\/code> and the target city end<\/code> are provided.<\/li>\n<\/ul>\nInput<\/h3>\n
\n n m\n u1 v1 cost1\n u2 v2 cost2\n ...\n um vm costm\n start end\n <\/code><\/pre>\nOutput<\/h3>\n
-1<\/code>.<\/p>\nAlgorithm Selection<\/h2>\n
O((n + m) log n)<\/code>, making it efficient even under maximum input conditions.<\/p>\nDijkstra’s Algorithm Overview<\/h3>\n
\n
Problem Solving Process<\/h2>\n
Step 1: Problem Analysis<\/h3>\n
Step 2: Code Implementation<\/h3>\n
\n#include <iostream>\n#include <vector>\n#include <queue>\n#include <utility>\n#include <limits>\n\nusing namespace std;\n\nconst int INF = numeric_limits<int>::max();\n\nvector<pair<int, int>> graph[10001];\n\nvoid dijkstra(int start, int n) {\n vector<int> cost(n + 1, INF);\n priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;\n\n cost[start] = 0;\n pq.push(make_pair(0, start));\n\n while (!pq.empty()) {\n int currentCost = pq.top().first;\n int currentNode = pq.top().second;\n pq.pop();\n\n if (currentCost > cost[currentNode]) continue;\n\n for (auto &edge : graph[currentNode]) {\n int nextNode = edge.first;\n int nextCost = edge.second;\n\n if (cost[currentNode] + nextCost < cost[nextNode]) {\n cost[nextNode] = cost[currentNode] + nextCost;\n pq.push(make_pair(cost[nextNode], nextNode));\n }\n }\n }\n\n for (int i = 1; i <= n; ++i) {\n if (cost[i] == INF) {\n cout << -1 << endl; \/\/ unreachable case\n } else {\n cout << cost[i] << endl;\n }\n }\n}\n\nint main() {\n int n, m;\n cin >> n >> m;\n\n for (int i = 0; i < m; ++i) {\n int u, v, cost;\n cin >> u >> v >> cost;\n graph[u].push_back(make_pair(v, cost));\n graph[v].push_back(make_pair(u, cost)); \/\/ assuming bidirectional roads\n }\n\n int start, end;\n cin >> start >> end;\n\n dijkstra(start, n);\n \n return 0;\n}\n <\/code><\/pre>\nStep 3: Code Testing<\/h3>\n
\n5 6\n1 2 1\n1 3 4\n2 3 2\n2 4 5\n3 4 1\n4 5 3\n1 5\n <\/code><\/pre>\nStep 4: Optimization<\/h3>\n
Conclusion<\/h2>\n