[LeetCode]Reachable Nodes In Subdivided Graph

我们直接把输入看成带权图即可，这道题本质上就是最短路径，但是区别是，如果我们发现M步之内无法从当前点去往下一个点，我们仍然会取当前边的一部分。比如从u到v需要10步，我们只剩下6不可以走，我们仍然会取这六个点。这里有一个情况需要注意一下，就是同一条边，如果我们只能取部分，可能会取到两次。比如u到v存在一条无向边，长度为10，我们到u的时候还剩8步，我们取了8个点。然后我们从其他某个点到达v，还剩5步，如果我们取了5个点这里就有重复了，长度为10的边我们却取了13个点，这是明显不行的。这里我们需要做一些特殊的处理，假设我们现在在顶点u，剩下的步数不够到达顶点v，连接u和v的边的长度为w，我们还剩下k步：

• 如果v是还没有visited过的点，我们取边上k个点即可。得到source到v的最短路径shortestPath[v]
• 如果v是已经被visited过的点，有可能出现上面提到的重复的情况。我们需要查看visit v的时候已经取了多少个节点，这个我们可以通过shortestPath[v]推出，等于总步数M - shortestPath[v]。根据这个值来决定取k还是w - (M - shortestPath[v])即可。

时间复杂度就是Dijkstra的复杂度O(E * log V)，空间复杂度O(V + E)，代码如下：

	class Solution {
	public:
	int reachableNodes(vector<vector<int>>& edges, int M, int N) {
	vector<vector<pair<int, int>>> g(N);
	for(const auto& edge : edges)
	{
	int u = edge[0], v = edge[1], w = edge[2];
	g[u].emplace_back(v, w);
	g[v].emplace_back(u, w);
	}
	unordered_map<int, int> visited;
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	unordered_map<string, int> pickedE;
	int cnt = 0;
	pq.emplace(0, 0);
	while(pq.size())
	{
	int curr = pq.top().second, currDist = pq.top().first;
	pq.pop();
	if(visited.find(curr) != visited.end())continue;
	visited[curr] = currDist;
	++cnt;
	for(const auto& adj : g[curr])
	{
	int v = adj.first, w = adj.second;
	if(visited.find(v) != visited.end())
	{
	int picked = min(w, M - visited[v]);
	cnt += min(w - picked, M - currDist);
	}
	else
	{
	cnt += min(w, M - currDist);
	if(currDist + w < M)
	{
	pq.emplace(currDist + w + 1, v);
	}
	}
	}
	}
	return cnt;
	}
	};

view raw Reachable Nodes In Subdivided Graph.cpp hosted with ❤ by GitHub