847. 访问所有节点的最短路径

题目描述

给出 graph 为有 N 个节点（编号为 0, 1, 2, ..., N-1）的无向连通图。 

graph.length = N，且只有节点 $i$ 和 $j$ 连通时，$j \ne i$ 在列表 graph[i] 中恰好出现一次。

返回能够访问所有节点的最短路径的长度。你可以在任一节点开始和停止，也可以多次重访节点，并且可以重用边。

示例

示例 1
输入：[[1,2,3],[0],[0],[0]]
输出：4
解释：一个可能的路径为 [1,0,2,0,3]

示例 2
输入：[[1],[0,2,4],[1,3,4],[2],[1,2]]
输出：4
解释：一个可能的路径为 [0,1,4,2,3]
 

提示

1 <= graph.length <= 12
0 <= graph[i].length < graph.length

题解

尽管第一开始看可能会想暴力跑，不过看到数据大小才 $12$，应该去果断考虑状压 DP。（就算是暴力跑，用到 DFS 的时候存储状态还是需要状态压缩）

（貌似和官方题解不太一样）

这道题最大的问题应该是题目描述有点绕，不过不看题目只看数据应该也可以猜出来意思

首先可以很容易确定两个变量：当前节点、当前状态。也即 dp[node][status]。由于节点最多只有 $12$ 个，因此可以直接用一个int的不同位来存储每个节点是否被访问过

如，dp[2][5] ($\underset{3}{\overset{8}{0}}\underset{2}{\overset{4}{1}}\underset{1}{\overset{2}{0}}\underset{0}{\overset{1}{1}}$) 表示节点 $0$ 和 节点 $2$ 已访问，且当前处于节点 $2$

那么我们很容易可以推知，状态转移方程为
$dp[\text{to}][\text{to\_status}] = min(dp[\text{to}][\text{status\_status}], dp[\text{from}][\text{from\_status}] + dis[\text{from}][\text{to}])$

公式的含义显而易见，对于位于 to 节点的状态，其必然是从一个没有访问过 to 节点的状态转移过来的（尽管整个路径中存在重复节点，但是每个重复路线的最终目的必定是为了访问某个未访问过的点。因此在这里不需要考虑重复节点，只需要确保走这两个节点间的最短路即可）

需要特别注意的是两个状态。首先，根据状态的含义可知，如果当前在 $i$ 节点，那么在状态中，$i$ 必定是被访问过的。也即，对于 to_status，from 和 to 对应的位必定为 1。而对于 from_status，from 对应的位必定为 1，to 对应的位必定为 0（其余位保持不变）。

接下来是初始和结束状态。开始时，可以位于任意节点，状态且只有对应节点访问过。也即 $dp[0][1]=dp[1][2]=dp[2][4]=dp[3][8]=\cdots=dp[i][2^i]=0$。
而结束时，也可以位于任意一个节点，只需要确保所有节点都已被访问（全 $1$）即可，其中的最小值即为最终答案。

这里实际上应该需要考虑状态顺序，原则上最完美的顺序应该是 “只有一个位为 $1$”、“两个位为 $1$”、$\cdots$、“所有位都是 $1$”。尽管从 $0$ 递加 status 并不严格满足这个公式，但是所有值在计算时，其依赖的值都已被计算。因此直接递加是可以达到目的的。
导致这个巧合地原因是，所有的 to_status 必定比 from_status 多一个 $1$，即 $\text{to\_status} > \text{from\_status}$。在其他的状压 DP，这点可能并不一定满足

解决状压 DP 部分后，只需要再计算一下任意两点最短路即可。任意两点最短路使用 floyd 算法，用 $O(n^3)$ 即可（注意中转节点在最外层）

代码

#include <stdio.h>
#include <stdlib.h> 

#define MAX (0x3f3f3f3f)
#define MAXN (15)

int dis[MAXN][MAXN];
int dp[MAXN][1<<MAXN];


int min(int a, int b) {
    return a<b ? a : b;
}

int shortestPathLength(int** graph, int graphSize, int* graphColSize){
    // 先求任意两点之间最短路
    memset(dis, MAX, sizeof(int)*MAXN*MAXN);
    for (int i=0; i<graphSize; ++i) {
        dis[i][i] = 0;
        for (int j=0; j<graphColSize[i]; ++j) 
            dis[i][graph[i][j]] = 1;
    }
    
    for (int k=0; k<graphSize; ++k) 
        for (int i=0; i<graphSize; ++i) 
            for (int j=0; j<graphSize; ++j) 
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);

    // 状态压缩 DP
    int maxStatus = (1<<(graphSize))-1;
    memset(dp, MAX, sizeof(int)*MAXN*(1<<MAXN));
    for(int i=0; i<graphSize; ++i) dp[i][1<<i] = 0;
    
    for (int status=0; status<=maxStatus; ++status) {
        for (int from=0; from<graphSize; ++from) {
            for (int to=0; to<graphSize; ++to) {
                if ((status>>from) & 1 == 1 && (status>>to) & 1 == 1) {
                    dp[to][status] = min(
                        dp[to][status], 
                        dp[from][status&(~(1<<to))] + dis[from][to]
                    );
                }
            }
        }
    }

    // 获取最小值
    int res = MAX;
    for (int i=0; i<graphSize; ++i) res = min(res, dp[i][maxStatus]);
    return res;
}