假设我们有两个大小相同的costs_from和costs_to列表，其中每个索引i代表一个城市。它正在从城市i到j的单向道路，其成本为costs_from [i] + costs_to [j]。我们还有一个边列表，其中每个边包含[x，y]，表示从城市x到y已有单向道路。如果要从城市0到任何城市，我们必须找到建造必要道路的最低成本。
因此，如果输入像costs_from = [6，2，2，12] cost_to = [2，2，3，2] edge = [[0，3]]，那么我们将输出为13从0到2的成本为9。之后，我们可以从2到1的成本为4。并且我们已经有从0到3的道路。所以总数为9 + 4 = 13。
为了解决这个问题，我们将遵循以下步骤-
n：=成本的大小
ret：= 0
定义两个映射边缘并变红
对于g中的所有项目：
在边缘[it [0]]的末尾插入[1]
在[red [1]]的末尾插入[0]
from_cost：= inf
定义一个访问过的集合，另一个可以访问的集合
定义一个函数dfs，这将需要一个数字i
将我插入访问
对于边[i]中的所有j，做
在po的末尾插入i
dfs(j)
如果我没有去过我并且无法到达，那么：
定义一个函数dfs2，这将需要一个数字i
如果拜访我，那么
返回真
如果我可以到达
返回假
将我标记为已访问并将我标记为可访问
ret：= true
对于所有红色的[i]，做
ret：+ ret和dfs2(j)
返回ret
定义一个队列q
在可达中插入0，在q中插入0
当（q不为空）时，请执行以下操作：
如果我无法到达，则：
from_cost：= from_cost和costs_from [node]的最小值
将我插入可及范围，将我插入q
节点：= q的第一个元素
从q删除元素
对于边缘中的每个i [node]
global_min：= costs_from的最小元素
ret：= ret + from_cost-global_min
定义数组po
对于0到n范围内的i，执行
dfs(i)
反转数组po
对于每个我在po中，
最好：= inf
对于访问的每个j：
ret：= ret + global_min +最佳
最佳：=最佳和costs_to的最小值[j]
进行下一次迭代
如果我可以到达，则：
清除访问的数组
首字母：= dfs2(i)
如果initial为true，则：
返回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