原始题目
给出 graph 为有 N 个节点（编号为 0, 1, 2, …, N-1）的无向连通图。
graph.length = N，且只有节点 i 和 j 连通时，j != i 在列表 graph[i] 中恰好出现一次。
返回能够访问所有节点的最短路径的长度。你可以在任一节点开始和停止，也可以多次重访节点，并且可以重用边。
题目大意
给一邻接表表示的图，求访问所有节点的最短路径（任意起点，可重边重点）。
解题思路
数位 dp，但这里不涉及转移，只判断状态是否出现过。（vis[1«N][n]） 第一维表示访问节点造访状态，第二维表示最后访问节点。
层序遍历 or 队列保存状态，BFS 下首次访问全状态节点即为答案。
解题代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ulll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<string, string> pss;
#define rep(i, a, n) for (int i = a; i < n; ++i)
#define per(i, a, n) for (int i = n - 1; i >= a; --i)
#define fi first
#define pb push_back
typedef struct Node {
int state;
int val;
int lst;
Node(int s, int v, int l)
: state(s)
, val(v)
, lst(l)
{
}
} Node;
class Solution {
public:
int shortestPathLength(vector<vector<int>>& graph)
{
int N = graph.size();
int start_state = 0;
int final_state = (1 << N) - 1;
// 不同状态下的dis表
vector<vi> vis(1 <<N , vi(N, 0));
queue<Node> q;
rep(i, 0, N)
{
q.push(Node(1 << i, 0, i));
vis[1 << i][i] = 1;
}
while (!q.empty()) {
Node now = q.front();
int nxt_p, nxt_state, nxt_value;
q.pop();
rep(i, 0, graph[now.lst].size())
{
// cout<<"lst="<<now.lst<<endl;
nxt_p = graph[now.lst][i];
// cout<<"nxt_p="<<nxt_p<<endl;
nxt_state = ((1 << graph[now.lst][i]) | now.state);
// cout<<"nxt_state="<<nxt_state<<endl;
if (nxt_state == final_state) {
return now.val + 1;
}
if (!vis[nxt_state][nxt_p]) {
vis[nxt_state][nxt_p] = 1;
q.push(Node(nxt_state, now.val + 1, nxt_p));
}
}
}
return 0;
}
};
收获与反思
- 开始仅用访问状态（一维），发现重访问边、节点无法体现，WA。
- 在包括该题在内的最短路问题中，BFS 蕴含了 DP 思想。所以该题不但能用 BFS 解，还能用 DP 解