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

## 题目描述

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

### 提示

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

## 题解

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

$dp[\text{to}][\text{to\_status}] = min(dp[\text{to}][\text{status\_status}], dp[\text{from}][\text{from\_status}] + dis[\text{from}][\text{to}])$

## 代码

#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;
}