2019 Dec Silver Problem 3 Milk Visits: Difference between revisions
No edit summary |
No edit summary |
||
(2 intermediate revisions by the same user not shown) | |||
Line 1: | Line 1: | ||
== Official Problem Statement == | |||
[http://www.usaco.org/index.php?page=viewproblem2&cpid=968 Milk Visits] | |||
== Problem Statement == | == Problem Statement == | ||
Line 13: | Line 17: | ||
In C++, the algorithm can be implemented as follows: | In C++, the algorithm can be implemented as follows: | ||
< | <pre> | ||
#include <vector> | #include <vector> | ||
#include <algorithm> | #include <algorithm> | ||
Line 82: | Line 86: | ||
return 0; | return 0; | ||
} | } | ||
</ | </pre> | ||
[[Category:Yearly_2019_2020]] | [[Category:Yearly_2019_2020]] | ||
[[Category:Silver]] | [[Category:Silver]] | ||
[[Category:DFS]] | |||
[[Category:Graph]] | |||
[[Category:Tree]] |
Latest revision as of 23:01, 11 June 2023
Official Problem Statement[edit]
Problem Statement[edit]
The farmer John has a farm with N cows (1 ≤ N ≤ 10^5). He wants to visit each cow exactly once and return to his house. He has a map of the farm, which contains N points: the house, the cows, and possibly some other points.
John can move between any two points on the map in a straight line. He can also move from one point to another and back again in a single move. The time it takes to move between two points is the Euclidean distance between them.
John wants to find the shortest route that visits each cow exactly once and returns to his house.
Solution[edit]
The solution to this problem can be found using the Travelling Salesman Problem (TSP) algorithm. This algorithm can be used to find the shortest route that visits each cow exactly once and returns to the house.
In C++, the algorithm can be implemented as follows:
#include <vector> #include <algorithm> using namespace std; // Function to find the shortest route // that visits each cow exactly once // and returns to the house int tsp(vector<vector<int>>& graph, vector<bool>& visited, int currPos, int n, int count, int cost) { // If all cows are visited if (count == n) { // Return cost of the route return cost + graph[currPos][0]; } // Initialize result int res = INT_MAX; // Try all unvisited cows for (int i = 0; i < n; i++) { if (!visited[i]) { // Mark cow as visited visited[i] = true; // Calculate cost of the route int newCost = cost + graph[currPos][i]; // Recur for remaining cows res = min(res, tsp(graph, visited, i, n, count + 1, newCost)); // Mark cow as unvisited visited[i] = false; } } return res; } int main() { // Number of cows int n = 5; // Adjacency matrix vector<vector<int>> graph = { { 0, 10, 15, 20 }, { 10, 0, 35, 25 }, { 15, 35, 0, 30 }, { 20, 25, 30, 0 } }; // Visited array to keep track // of visited cows vector<bool> visited(n); // Initialize result int res = INT_MAX; // Find the shortest route res = tsp(graph, visited, 0, n, 0, 0); // Print result cout << res << endl; return 0; }