力扣 847. 访问所有节点的最短路径 bfs+状压

https://leetcode-cn.com/problems/shortest-path-visiting-all-nodes/

思路：考虑用二进制表示走过的点集(状态压缩)，那么可以用$dis[i][j]$表示在状态为$i$的情况下到$j$点的最短路径，那么我们期望的答案就是最小的$dis[2^n-1][...]$。依然可以使用$bfs$来求解最短路，只不过状态是两个维度的。也可以认为这是刷表法的$dp$。

class Solution {
public:int shortestPathLength(vector<vector<int>>& graph) {int n=graph.size();int times=1<<n;vector<vector<int>> dis(times,vector<int>(n,0x3f3f3f3f));using pr=pair<int,int>;queue<pr> q;for(int i=0;i<n;i++){q.emplace(1<<i,i);dis[1<<i][i]=0;}while(!q.empty()){pr f=q.front();q.pop();for(int to:graph[f.second]){int idx=f.first|(1<<to);if(dis[idx][to]>dis[f.first][f.second]+1){dis[idx][to]=dis[f.first][f.second]+1;if(idx==times-1)return dis[idx][to];q.emplace(idx,to);}}}return 0;}
};