数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++程序：查找到达任意城市（从第一个城市出发）所需的最小道路数量
假设我们有两个大小相同的列表 costs_from 和 costs_to，其中每个索引 i 代表一个城市。它正在从城市 i 到城市 j 建立一条单向道路，它们的成本为 costs_from[i] + costs_to[j]。我们还有一个边的列表，其中每条边包含 [x, y]，表示城市 x 到城市 y 已经存在一条单向道路。如果我们想从城市 0 到达任何城市，我们需要找到建造必要道路的最小成本。
因此，如果输入类似于 costs_from = [6, 2, 2, 12] costs_to = [2, 2, 3, 2] edges = [[0, 3]]，则输出将为 13，因为我们可以以 9 的成本从 0 到达 2。之后，我们可以以 4 的成本从 2 到达 1。并且我们已经有了从 0 到达 3 的道路。所以总成本为 9 + 4 = 13。
为了解决这个问题，我们将遵循以下步骤：
- n := costs_from 的大小
- ret := 0
- 定义两个映射 edges 和 redges
- 对于所有项目 it in g
- 将 it[1] 插入到 edges[it[0]] 的末尾
- 将 it[0] 插入到 redges[it[1]] 的末尾
- from_cost := 无穷大
- 定义一个集合 visited 和另一个集合 reachable
- 定义一个函数 dfs，它将接收一个数字 i
- 如果 i 未被访问并且 i 不可到达，则
- 将 i 插入到 visited 中
- 对于 edges[i] 中的所有 j，执行
- dfs(j)
- 将 i 插入到 po 的末尾
- 如果 i 未被访问并且 i 不可到达，则
- 定义一个函数 dfs2，它将接收一个数字 i
- 如果 i 被访问过，则
- 返回 true
- 如果 i 可到达
- 返回 false
- 将 i 标记为已访问并将其标记为可到达
- ret := true
- 对于 redges[i] 中的所有 j，执行
- ret :+ ret AND dfs2(j)
- 返回 ret
- 定义一个队列 q
- 将 0 插入到 reachable 和 q 中
- 当 (q 不为空) 时，执行
- node := q 的第一个元素
- 从 q 中删除元素
- 对于 edges[node] 中的每个 i
- 如果 i 不在 reachable 中，则
- 将 i 插入到 reachable 和 q 中
- from_cost := from_cost 和 costs_from[node] 的最小值
- 如果 i 不在 reachable 中，则
- global_min := costs_from 的最小元素
- ret := ret + from_cost - global_min
- 定义一个数组 po
- 对于 i 从 0 到 n，执行
- dfs(i)
- 反转数组 po
- 对于 po 中的每个 i，执行
- 如果 i 可到达，则
- 进行下一次迭代
- 清空 visited 数组
- initial := dfs2(i)
- 如果 initial 为 true，则
- best := 无穷大
- 对于 visited 中的每个 j
- best := best 和 costs_to[j] 的最小值
- ret := ret + global_min + best
- 如果 i 可到达，则
- 返回 ret
让我们看看以下实现以获得更好的理解：
示例
#include
using namespace std;
class Solution {
public:
int solve(vector& costs_from, vector& costs_to, vector>& g) {
int n = costs_from.size();
int ret = 0;
map> edges;
map> redges;
for (auto& it : g) {
edges[it[0]].push_back(it[1]);
redges[it[1]].push_back(it[0]);
}
int from_cost = INT_MAX;
set visited;
set reachable;
queue q;
reachable.insert(0);
q.push(0);
while (!q.empty()) {
int node = q.front();
q.pop();
for (int i : edges[node]) {
if (!reachable.count(i)) {
reachable.insert(i);
q.push(i);
}
}
from_cost = min(from_cost, costs_from[node]);
}
int global_min = *min_element(costs_from.begin(), costs_from.end());
ret += from_cost - global_min;
vector po;
function dfs;
dfs = [&](int i) {
if (!visited.count(i) && !reachable.count(i)) {
visited.insert(i);
for (int j : edges[i]) {
dfs(j);
}
po.push_back(i);
}
};
for (int i = 0; i < n; i++) dfs(i);
reverse(po.begin(), po.end());
function dfs2;
dfs2 = [&](int i) {
if (visited.count(i)) return true;
if (reachable.count(i)) return false;
visited.insert(i);
reachable.insert(i);
bool ret = true;
for (int j : redges[i]) {
ret &= dfs2(j);
}
return ret;
};
for (int i : po) {
if (reachable.count(i)) continue;
visited.clear();
bool initial = dfs2(i);
if (initial) {
int best = INT_MAX;
for (int j : visited) {
best = min(best, costs_to[j]);
}
ret += global_min + best;
}
}
return ret;
}
};
int solve(vector& costs_from, vector& costs_to, vector>& edges) {
return (new Solution())->solve(costs_from, costs_to, edges);
}
int main(){
vector costs_from = {6, 2, 2, 12};
vector costs_to = {2, 2, 3, 2};
vector> edges = {{0, 3}};
cout << solve(costs_from, costs_to, edges);
}输入
{6, 2, 2, 12}, {2, 2, 3, 2}, {{0, 3}}输出
13
更新于: 2020年12月3日
650 次浏览
广告