# [847. Shortest Path Visiting All Nodes](https://leetcode.com/problems/shortest-path-visiting-all-nodes/)
##### tags: `leetcode`

[TOC]

## Description

## Ideas

* 由於此題只能窮舉全部的可能，所以創建一個memo儲存已搜尋過的值
* 而跑過的點我們不需要考慮，只需考慮剩下哪些點還沒有跑過
* 等價找點與點之間的最短距離，再窮舉全部的可能性
* 等價先求all-pairs shortest paths再DFS/BFS
* 所以先利用Floyd-Warshall algo. 求 all min. paths
* 再利用DFS遞迴找答案
* TC = O(2^n * n^2)
### Code
#### Python 3

class Solution:
    def shortestPathLength(self, graph: List[List[int]]) -> int:
        # dp + bitmask
        @lru_cache(maxsize = None)
        def dp(mask, idx):
            if mask == 0:
                return 0
            res = inf
            for nei in range(n):
                if mask & (1 << nei):
                     res = min(res, dp(mask - (1 << nei), nei) + g[idx][nei])
            return res
        
        # init. graph
        n = len(graph)
        g = [[inf] * n for i in range(n)]
        for i, arr in enumerate(graph):
            for j in arr:
                g[i][j] = g[j][i] = 1
        
        # all-pairs shortest paths
        for k in range(n):
            temp = g.copy()
            for i in range(n):
                for j in range(n):
                    temp[i][j] = min(temp[i][j], g[i][k] + g[k][j])
            g = temp
        # for i in range(n):
        #     g[i][i] = inf      # 也可以等於0
        
        # dp + bitmask
        mask = (1 << n) - 1
        res = inf
        for start in range(n):
            res = min(res, dp(mask - (1 << start), start))
        return res

#### C++
* 由於c++有overflow的問題，所以就真的一個點一個點的跑下去 (好像其實也比較快?)
* 另外創建一個 not_seen 表示尚未看過 (同memo，名稱不同而已)
* 用BFS/DFS從所有的起點出發，直到跑完全部的點

class Solution {
public:
    int shortestPathLength(vector<vector<int>>& graph) {
        int n = graph.size();
        int res = 0, mask = (1 << n) - 1;
        vector<vector<bool>> not_seen(1<<n, vector<bool>(n, true));
        
        // all start nodes
        vector<pair<int, int>> stack;
        for (int i = 0; i < n; ++i) {
            not_seen[1<<i][i] = false;
            stack.push_back({1<<i, i});
        }
        
        while (stack.size()) {
            vector<pair<int, int>> new_stack;
            ++res;
            
            // BFS
            for (auto p: stack) {
                int m = p.first, start = p.second;
                // find neighbor
                for (auto nei: graph[start]) {
                    int new_mask = m | (1 << nei);
                    if (new_mask == mask)
                        return res;
                    
                    if (not_seen[new_mask][nei]) {
                        not_seen[new_mask][nei] = false;
                        new_stack.push_back({new_mask, nei});
                    }
                }
            }
            
            swap(new_stack, stack);
        }
        return 0;
    }
};