【动态规划】【广度优先搜索】【状态压缩】847 访问所有节点的最短路径

class Solution {
public:
  int shortestPathLength(vector<vector<int>>& graph) {
    m_c = graph.size();
    m_iMaskCount = 1 << m_c;
    for (int i = 0; i < m_c; i++)
    {
      BFS(graph, i);
    }
    return m_iRet;
  }
  void BFS(vector<vector<int>>& neiBo,int start)
  {
    vector<vector<int>> vDis(m_c, vector<int>(m_iMaskCount, m_iNotMay));
    queue<pair<int, int>> que;
    auto Add = [&](int node, int iPreMask,int iNew)
    {
      const int iMask = iPreMask | (1 << node);
      if (vDis[node][iMask] <= iNew )
      {
        return ;
      }
      vDis[node][iMask] = iNew;
      que.emplace(node, iMask);
    };
    Add( start,0, 0);
    while (que.size())
    {
      auto [preNode, preMask] = que.front();
      const int iNew = vDis[preNode][preMask]+1;
      que.pop();
      for (const auto& next : neiBo[preNode])
      {
        Add(next, preMask, iNew);
      }
    }
    for (const auto& v : vDis)
    {
      m_iRet = min(m_iRet, v.back());
    }
  }
  const int m_iNotMay = 100'000;
  int m_c, m_iMaskCount;
  int m_iRet = m_iNotMay;
};

template<class T>
void Assert(const T& t1, const T& t2)
{
  assert(t1 == t2);
}
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
  if (v1.size() != v2.size())
  {
    assert(false);
    return;
  }
  for (int i = 0; i < v1.size(); i++)
  {
    Assert(v1[i], v2[i]);
  }
}
int main()
{ 
  vector<vector<int>> graph;
  {
    Solution sln;
    graph = { {1,2,3},{0},{0},{0} };
    auto res = sln.shortestPathLength(graph);
    Assert(res, 4);
  }
  {
    Solution sln;
    graph = { {1},{0,2,4},{1,3,4},{2},{1,2} };
    auto res = sln.shortestPathLength(graph);
    Assert(res, 4);
  }
}

//多源码路径
template<class T, T INF = 1000 * 1000 * 1000>
class CFloyd
{
public:
  CFloyd(const  vector<vector<T>>& mat)
  {
    m_vMat = mat;
    const int n = mat.size();
    for (int i = 0; i < n; i++)
    {//通过i中转
      for (int i1 = 0; i1 < n; i1++)
      {
        for (int i2 = 0; i2 < n; i2++)
        {
          //此时：m_vMat[i1][i2] 表示通过[0,i)中转的最短距离
          m_vMat[i1][i2] = min(m_vMat[i1][i2], m_vMat[i1][i] + m_vMat[i][i2]);
          //m_vMat[i1][i2] 表示通过[0,i]中转的最短距离
        }
      }
    }
  };
  vector<vector<T>> m_vMat;
};
class Solution {
public:
  int shortestPathLength(vector<vector<int>>& graph) {
    m_c = graph.size();
    m_iMaskCount = 1 << m_c;
    vector<vector<int>> mat(m_c, vector<int>(m_c, 1000 * 1000 * 1000));
    for (int i = 0; i < m_c; i++)
    {
      for (const auto& j : graph[i])
      {
        mat[i][j] = 1;
      }
    }
    CFloyd floyd(mat);
    vector<vector<int>> vDis(m_c, vector<int>(m_iMaskCount, m_iNotMay));
    for (int i = 0; i < m_c; i++)
    { 
      vDis[i][1 << i] = 1;
    }
    for (int mask = 1; mask < m_iMaskCount; mask++)
    {
      for (int i = 0; i < m_c; i++)
      {
        if (vDis[i][mask] >= m_iNotMay)
        {
          continue;
        }
        for (int next = 0 ;next < m_c ;next++ )
        {
          if ((1 << next) & mask)
          {
            continue;//已经访问
          }
          const int iNewMask = (1 << next) | mask;
          vDis[next][iNewMask] = min(vDis[next][iNewMask], vDis[i][mask] + floyd.m_vMat[i][next]);
        }
      }
    }
    int iRet = m_iNotMay;
    for (const auto& v : vDis)
    {
      iRet = min(iRet, v.back());
    }
    return iRet-1;
  }
  const int m_iNotMay = 100'000;
  int m_c, m_iMaskCount;
};