【单源最短路 图论】3112. 访问消失节点的最少时间

class CNeiBo
{
public: 
  static vector<vector<int>> Two(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0) 
  {
    vector<vector<int>>  vNeiBo(n);
    for (const auto& v : edges)
    {
      vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase);
      if (!bDirect)
      {
        vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase);
      }
    }
    return vNeiBo;
  } 
  static vector<vector<std::pair<int, int>>> Three(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0)
  {
    vector<vector<std::pair<int, int>>> vNeiBo(n);
    for (const auto& v : edges)
    {
      vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase, v[2]);
      if (!bDirect)
      {
        vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase, v[2]);
      }
    }
    return vNeiBo;
  }
  static vector<vector<int>> Grid(int rCount, int cCount, std::function<bool(int, int)> funVilidCur, std::function<bool(int, int)> funVilidNext)
  {
    vector<vector<int>> vNeiBo(rCount * cCount);
    auto Move = [&](int preR, int preC, int r, int c)
    {
      if ((r < 0) || (r >= rCount))
      {
        return;
      }
      if ((c < 0) || (c >= cCount))
      {
        return;
      }
      if (funVilidCur(preR, preC) && funVilidNext(r, c))
      {
        vNeiBo[cCount * preR + preC].emplace_back(r * cCount + c);
      }
    };
    for (int r = 0; r < rCount; r++)
    {
      for (int c = 0; c < cCount; c++)
      {
        Move(r, c, r + 1, c);
        Move(r, c, r - 1, c);
        Move(r, c, r, c + 1);
        Move(r, c, r, c - 1);
      }
    }
    return vNeiBo;
  }
  static vector<vector<int>> Mat(vector<vector<int>>& neiBoMat)
  {
    vector<vector<int>> neiBo(neiBoMat.size());
    for (int i = 0; i < neiBoMat.size(); i++)
    {
      for (int j = i + 1; j < neiBoMat.size(); j++)
      {
        if (neiBoMat[i][j])
        {
          neiBo[i].emplace_back(j);
          neiBo[j].emplace_back(i);
        }
      }
    }
    return neiBo;
  }
};
//堆（优先队列)优化迪杰斯特拉算法 狄克斯特拉(Dijkstra)算法详解
typedef pair<long long, int> PAIRLLI;
class  CMyHeapDis
{
public:
  CMyHeapDis(vector<int>& disappear,int n, long long llEmpty = LLONG_MAX / 10) :m_llEmpty(llEmpty),m_disappear(disappear)
  {
    m_vDis.assign(n, m_llEmpty);
  }
  void Cal(int start, const vector<vector<pair<int, int>>>& vNeiB)
  {
    std::priority_queue<PAIRLLI, vector<PAIRLLI>, greater<PAIRLLI>> minHeap;
    minHeap.emplace(0, start);
    while (minHeap.size())
    {
      const long long llDist = minHeap.top().first;
      const int iCur = minHeap.top().second;
      minHeap.pop();
      if (m_llEmpty != m_vDis[iCur])
      {
        continue;
      }
      if (llDist >= m_disappear[iCur]) {
        continue;
      }
      m_vDis[iCur] = llDist;
      for (const auto& it : vNeiB[iCur])
      {
        minHeap.emplace(llDist + it.second, it.first);
      }
    }
  }
  vector<long long> m_vDis;
  const long long m_llEmpty;
  vector<int>& m_disappear;
};
class Solution {
public:
  vector<int> minimumTime(int n, vector<vector<int>>& edges, vector<int>& disappear) {
    auto neiBo = CNeiBo::Three(n, edges, false);
    CMyHeapDis dis(disappear,n,m_llNotMay);
    dis.Cal(0, neiBo);  
    vector<int> vRet;
    for (int i = 0; i < n; i++) {
      vRet.emplace_back((m_llNotMay==dis.m_vDis[i])?-1: dis.m_vDis[i]);
    }
    return vRet;
  }
  const long long m_llNotMay = 1'000'000'000'000LL;
};