traveler

traveler.cpp

class Solution {
public:
    /**
     * @param n: an integer,denote the number of cities
     * @param roads: a list of three-tuples,denote the road between cities
     * @return: return the minimum cost to travel all cities
     */
    int minCost(int n, vector<vector<int>> &roads) {
        // unordered_map<int, vector<pair<int, int>>> graph;
        // constructGraph(roads, graph);
        
        vector<vector<int>> graph(n);
        constructGraph2(n, roads, graph);

        int cost = INT_MAX;
        int currCost = 0;
        unordered_set<int> visited;
        visited.insert(0);
        
        dfs(n, graph, cost, currCost, 0, visited);
        return cost;
    }

    void constructGraph(vector<vector<int>> &roads, unordered_map<int, vector<pair<int, int>>> &graph) {
        for (int i = 0; i < roads.size(); i++) {
            graph[roads[i][0] - 1].push_back(pair<int, int>{roads[i][1] - 1, roads[i][2]});
            graph[roads[i][1] - 1].push_back(pair<int, int>{roads[i][0] - 1, roads[i][2]});
        }
    }

    void constructGraph2(int n, vector<vector<int>> &roads, vector<vector<int>> &graph) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                graph[i].push_back(INT_MAX);
            }
        }
        
        for (int i = 0; i < roads.size(); i++) {
            int x = roads[i][1] - 1;
            int y = roads[i][0] - 1;
            graph[x][y] = min(graph[x][y], roads[i][2]);
            graph[y][x] = min(graph[y][x], roads[i][2]);
        }
    }

    // void dfs(int n, unordered_map<int, vector<pair<int, int>>> &graph, int &cost, int currCost, int lastCity, unordered_set<int> &visited) {
    void dfs(int n, vector<vector<int>> &graph, int &cost, int currCost, int lastCity, unordered_set<int> &visited) {
        if (visited.size() == n) {
            cost = min(cost, currCost);
            return;
        }

        // for (int i = 0; i < graph[lastCity].size(); i++) {
        for (int i = 0; i < n; i++) {
            // int nextCity = graph[lastCity][i].first;
            int nextCity = i;
            
            // if (visited.count(nextCity)) {
            //     continue;
            // }
            if (visited.count(nextCity) || graph[lastCity][i] == INT_MAX) {
                continue;
            }

            // int nextCost = graph[lastCity][i].second;
            int nextCost = graph[lastCity][i];
            currCost += nextCost;
            visited.insert(nextCity);
            dfs(n, graph, cost, currCost, nextCity, visited);
            visited.erase(nextCity);
            currCost -= nextCost;
        }
    }
};