leetcode::minimum_weighted_subgraph_with_the_required_paths::Solution类 参考

#include <leetcode.h>

静态 Public 成员函数
static void	calc_dist (int s, vector< pair< int, int > > *graph, vector< long long int > &dist)
static long long	minimumWeight (int n, vector< vector< int > > &edges, int src1, int src2, int dest)

详细描述

在文件 leetcode.h 第 1714 行定义.

成员函数说明

calc_dist()

void leetcode::minimum_weighted_subgraph_with_the_required_paths::Solution::calc_dist ( int  s, vector< pair< int, int > > *  graph, vector< long long int > &  dist  )

static

在文件 leetcode.cpp 第 4444 行定义.

                                                                                                  {
            priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;
            dist[s] = 0;
            pq.emplace(0, s);
            while(!pq.empty()) {
                auto [weight, node] = pq.top();
                pq.pop();
                if(weight > dist[node]) {
                    continue;
                }
                for(auto [next_node, next_weight]: graph[node]) {
                    if(weight + next_weight < dist[next_node]) {
                        dist[next_node] = weight + next_weight;
                        pq.emplace(weight + next_weight, next_node);
                    }
                }
            }
        }

被这些函数引用 minimumWeight().

minimumWeight()

long long leetcode::minimum_weighted_subgraph_with_the_required_paths::Solution::minimumWeight ( int  n, vector< vector< int > > &  edges, int  src1, int  src2, int  dest  )

static

在文件 leetcode.cpp 第 4405 行定义.

                                                                                                         {
            auto *graph     = new vector<pair<int, int>>[n];
            auto *graph_rev = new vector<pair<int, int>>[n];
            for(int i = 0; i < n; i++) {
                graph[i]     = vector<pair<int, int>>();
                graph_rev[i] = vector<pair<int, int>>();
            }
            for(auto &edge: edges) {
                auto from   = edge[0];
                auto to     = edge[1];
                auto weight = edge[2];
                graph[from].emplace_back(to, weight);
                graph_rev[to].emplace_back(from, weight);
            }
 
            long long a = LLONG_MAX;
            vector dist_src1(n, LLONG_MAX);
            vector dist_src2(n, LLONG_MAX);
            vector dist_dest(n, LLONG_MAX);
 
            calc_dist(src1, graph, dist_src1);
            calc_dist(src2, graph, dist_src2);
            calc_dist(dest, graph_rev, dist_dest);
 
            long long ans = LLONG_MAX;
 
            for(int i = 0; i < n; ++i) {
                if(dist_src1[i] != LLONG_MAX && dist_src2[i] != LLONG_MAX && dist_dest[i] != LLONG_MAX) {
                    ans = min(ans, dist_src1[i] + dist_src2[i] + dist_dest[i]);
                }
            }
            if(ans == LLONG_MAX) {
                ans = -1;
            }
            delete[] graph;
            delete[] graph_rev;
            return ans;
        }

引用了 calc_dist().

被这些函数引用 leetcode::minimum_weighted_subgraph_with_the_required_paths::TEST().

---

该类的文档由以下文件生成:

• leetcode.h
• leetcode.cpp