LeetCode882 细分图中的可到达结点

发表于 | 分类于 |
字数统计: 467 | 阅读时长 ≈ 2

链接: https://leetcode-cn.com/problems/reachable-nodes-in-subdivided-graph/

题意

给定一张图，图上每两条边上有链上节点，求从节点0出发最多能到的节点个数

解法

我是废物.jpg
简单的说来就是最短路径算法，把两个节点链上的节点当作是两个节点的距离
只是在计算节点的过程中，需要记录寻找最短路径的过程来计算链上节点可以到达的个数
复习了一遍dijkstra算法和用优先队列优化的dijkstra
用两个used来记录每两个节点的链上的节点使用率
细节见代码
写了大半天 我是废物.jpg

代码

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
#define P pair<int, int>
class Solution {
public:
    int reachableNodes(vector<vector<int>>& edges, int maxMoves, int n) {
        vector<vector<P>> graph(n);
        map<P, int> used;
        vector<int> d(n);
        int ans = 0;
        for (auto edge: edges) {
            graph[edge[0]].push_back({edge[1], edge[2] + 1});
            graph[edge[1]].push_back({edge[0], edge[2] + 1});
        }
        priority_queue<P, vector<P>, greater<P> > que;
        fill(d.begin(), d.end(), 0x7f7f7f);
        d[0] = 0;
        que.push(P(0, 0));
        while(que.size()) {
            P p = que.top();
            que.pop();
            int v = p.second;
            if (d[v] < p.first) continue; // 如果已经不是最短距离了 continue
            ans++;
            for (int i = 0; i < graph[v].size(); i++) {
                P e = graph[v][i];
                int value = maxMoves - d[v];
                // cout << v << ' ' << e.first << ' ' << value << ' ' << e.second << endl;
                used[{v, e.first}] = max(used[{v, e.first}], min(e.second - 1, value));
                if (d[e.first] > d[v] + e.second) {
                    d[e.first] = d[v] + e.second;
                    if (d[e.first] <= maxMoves) // 小于最大步数才加入队列
                        que.push({d[e.first], e.first});
                }
            }
        }
        for (auto edge: edges) {
            int u = edge[0], v = edge[1], w = edge[2];
            int a = used[{u, v}], b = used[{v, u}];
            ans += min(a + b, w);
        }
        return ans;

    }
};