資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++程式：查詢給定圖中q個查詢的最短成本路徑
假設我們得到一個包含n個頂點的最小連通圖。邊的資訊以{源節點，目標節點，權重}的格式儲存在一個數組中。現在，我們得到q個查詢，每個查詢的格式為{源節點，目標節點}。我們必須找到從源節點到目標節點經過頂點k的最短成本路徑。我們列印每個查詢的路徑成本。
因此，如果輸入為n = 6，q = 3，k = 1，edges = {{1, 2, 2}, {1, 3, 4}, {3, 4, 2}, {3, 5, 3}, {5, 6, 2}}，queries = {{1, 4}, {2, 6}, {2, 5}}，則輸出將為6 11 9。
步驟
為了解決這個問題，我們將遵循以下步驟：
Define one 2D array graph of pairs of size n * n Define an array pathTotal of size n Define a function dfs(), this will take a, b, for each value i at graph[a]: if first value of i is same as b, then: Ignore following part, skip to the next iteration pathTotal[first value of i] := pathTotal[a] + second value of i dfs(first value of i, a) for initialize i := 0, when i < n - 1, update (increase i by 1), do: a := first value of (edges[i]) b := second value of (edges[i]) c := third value of (edges[i]) decrease a and b by 1 insert pair (b, c) at the end of graph[a] insert pair (a, c) at the end of graph[b] (decrease k by 1) dfs(k, k) for initialize i := 0, when i < q, update (increase i by 1), do: x := first value of queries[i] y := second value of queries[i] decrease x and y by 1 print(pathTotal[x] + pathTotal[y])
示例
讓我們看看下面的實現以更好地理解：
#include <bits/stdc++.h>
using namespace std;
vector<vector<pair<int,int>>> graph;
vector<int> pathTotal;
int k;
void dfs(int a, int b){
for(auto i : graph.at(a)){
if(i.first == b) continue;
pathTotal.at(i.first) = pathTotal.at(a) + i.second;
dfs(i.first,a);
}
}
void solve(int n, int q, vector<tuple<int, int, int>> edges,
vector<pair<int, int>> queries){
int a, b, c, x, y;
graph.resize(n);
pathTotal.resize(n);
for(int i = 0; i < n - 1; i++){
a = get<0> (edges[i]);
b = get<1> (edges[i]);
c = get<2> (edges[i]);
a--, b--;
graph.at(a).push_back(make_pair(b, c));
graph.at(b).push_back(make_pair(a, c));
}
k--;
dfs(k, k);
for(int i = 0; i < q; i++){
x = queries[i].first;
y = queries[i].second;
x--, y--;
cout << pathTotal.at(x) + pathTotal.at(y) << endl;
}
}
int main() {
int n = 6, q = 3;
k = 1;
vector<tuple<int, int, int>> edges = {{1, 2, 2}, {1, 3, 4}, {3, 4, 2}, {3, 5, 3}, {5, 6, 2}};
vector<pair<int, int>> queries = {{1, 4}, {2, 6}, {2, 5}};
solve(n, q, edges, queries);
return 0;
}輸入
6, 3, 1, {{1, 2, 2}, {1, 3, 4}, {3, 4, 2}, {3, 5, 3}, {5, 6, 2}}, {{1, 4}, {2, 6}, {2, 5}}
輸出
6 11 9
更新於：2022年3月2日
475 次瀏覽
廣告