数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究在 C++ 中查找任意一对不同良节点之间的最短距离
假设我们有一个给定的带权无向图，它有 N 个不同的节点和 M 条边，其中一些节点是良节点。我们必须找到任意一对不同良节点之间的最短距离。在下图中，黄色节点被认为是良节点。
因此，如果输入类似于
那么输出将是 11，因为良节点对及其之间的距离为：(1 到 3) 距离为 11，(3 到 5) 距离为 13，(1 到 5) 距离为 24，其中 11 是最小值。
为了解决这个问题，我们将遵循以下步骤：
N := 100005
MAX_VAL := 99999999
创建一个优先队列 q
result := MAX_VAL
初始化 i := 1，当 i <= n 时，更新 (i 加 1)，执行以下操作：
如果 good_verts[i] 为假，则：
忽略以下部分，跳到下一个迭代
初始化 j := 1，当 j <= n 时，更新 (j 加 1)，执行以下操作：
dist[j] := MAX_VAL
vis[j] := 0
dist[i] := 0
当 (q 不为空) 时，执行以下操作：
从 q 中删除元素
将 { 0, i } 插入 q
good := 0
当 (q 不为空) 时，执行以下操作：
v := q 的顶部元素
从 q 中删除元素
如果 vis[v] 为真，则：
忽略以下部分，跳到下一个迭代
vis[v] := 1
good := good + (当 good_verts[v] 为真时为 1，否则为 0)
如果 dist[v] > result，则：
退出循环
如果 good 等于 2 且 good_verts[v] 为真，则：
result := result 和 dist[v] 的最小值
退出循环
初始化 j := 0，当 j < graph[v] 的大小时，更新 (j 加 1)，执行以下操作：
to := graph[v, j].first
weight := graph[v, j].second
如果 dist[v] + weight < dist[to]，则：
dist[to] := dist[v] + weight
将 { dist[to], to } 插入 q
返回 result
示例
让我们看看以下实现以更好地理解：
#include <bits/stdc++.h>
using namespace std;
#define N 100005
#define MAX_VAL 99999999
void insert_edge(vector<pair<int, int> > graph[], int x, int y, int weight) {
graph[x].push_back({ y, weight });
graph[y].push_back({ x, weight });
}
int get_min_dist(vector<pair<int, int> > graph[], int n, int dist[], int vis[], int good_verts[], int k) {
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int>>> q;
int result = MAX_VAL;
for (int i = 1; i <= n; i++) {
if (!good_verts[i])
continue;
for (int j = 1; j <= n; j++) {
dist[j] = MAX_VAL;
vis[j] = 0;
}
dist[i] = 0;
while (!q.empty())
q.pop();
q.push({ 0, i });
int good = 0;
while (!q.empty()) {
int v = q.top().second;
q.pop();
if (vis[v])
continue;
vis[v] = 1;
good += good_verts[v];
if (dist[v] > result)
break;
if (good == 2 and good_verts[v]) {
result = min(result, dist[v]);
break;
}
for (int j = 0; j < graph[v].size(); j++) {
int to = graph[v][j].first;
int weight = graph[v][j].second;
if (dist[v] + weight < dist[to]) {
dist[to] = dist[v] + weight;
q.push({ dist[to], to });
}
}
}
}
return result;
}
int main() {
int n = 5, m = 5;
vector<pair<int, int> > graph[N];
insert_edge(graph, 1, 2, 3);
insert_edge(graph, 1, 2, 3);
insert_edge(graph, 2, 3, 4);
insert_edge(graph, 3, 4, 1);
insert_edge(graph, 4, 5, 8);
int k = 3;
int good_verts[N], vis[N], dist[N];
good_verts[1] = good_verts[3] = good_verts[5] = 1;
cout << get_min_dist(graph, n, dist, vis, good_verts, k);
}输入
n = 5, m = 5 insert_edge(graph, 1, 2, 3); insert_edge(graph, 1, 2, 3); insert_edge(graph, 2, 3, 4); insert_edge(graph, 3, 4, 1); insert_edge(graph, 4, 5, 8); k = 3 good_verts[1] = good_verts[3] = good_verts[5] = 1;
输出
7
402 次浏览
