【LeetCode-847】解题报告（最短路）

原始题目

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

graph.length = N，且只有节点 i  和 j  连通时，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 解