LeetCode 3112. 访问消失节点的最少时间
原题链接
中等
作者:
autumn_0
,
2024-07-18 00:21:12
,
所有人可见
,
阅读 6
class Solution {
public:
vector<int> minimumTime(int n, vector<vector<int>>& edges, vector<int>& disappear) {
vector<vector<pair<int, int>>> g(n);
for(auto& c : edges)
{
int x = c[0], y = c[1], wt = c[2];
g[x].emplace_back(y, wt);
g[y].emplace_back(x, wt);
}
vector<int> dis(n, -1);
dis[0] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
pq.emplace(0, 0);
while(!pq.empty())
{
auto [dx, x] = pq.top();
pq.pop();
if(dx > dis[x]) continue;
for(auto& [y, d]: g[x])
{
int new_dis = dx + d;
if(new_dis < disappear[y] && (dis[y] < 0 || new_dis < dis[y]))
{
dis[y] = new_dis;
pq.emplace(new_dis, y);
}
}
}
return dis;
}
};