【LeetCode-847】解题报告(最短路)

原始题目

给出 graph 为有 N 个节点(编号为 0, 1, 2, …, N-1)的无向连通图。

graph.length = N,且只有节点 ij 连通时,j != i 在列表 graph[i] 中恰好出现一次。

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

题目大意

给一邻接表表示的图,求访问所有节点的最短路径(任意起点,可重边重点)。

解题思路

数位 dp,但这里不涉及转移,只判断状态是否出现过。(vis[1<<N][n]) 第一维表示访问节点造访状态,第二维表示最后访问节点。

层序遍历 or 队列保存状态,BFS 下首次访问全状态节点即为答案。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#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 解