Patrolling Time: Compute Minimum Time for a Guard to Patrol All Zones in a Graph

Problem A security guard must patrol n zones connected by corridors (a weighted undirected graph). Each zone must be visited at least once. The guard starts at zone 0. Find the minimum total travel time to visit all zones and optionally return to the start. Example: Approach For small n (n <= 20): bitmask DP on visited set. dp[mask][v] = min time to have visited exactly the zones in mask, ending at zone v. Precompute all-pairs shortest paths with Floyd-Warshall. Follow-ups What is the time compl…