資料結構
網路
關係型資料庫管理系統
作業系統
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 次瀏覽
廣告