N개의 서로 다른 노드와 M개의 간선이 있는 가중치가 부여된 무방향 그래프가 있다고 가정하고 일부 노드는 좋은 노드입니다. 우리는 두 개의 서로 다른 좋은 노드 쌍 사이의 최단 거리를 찾아야 합니다. 주어진 다이어그램에서 다음 그래프의 노란색은 좋은 노드로 간주됩니다.
따라서 입력이 다음과 같으면
좋은 노드의 쌍과 그들 사이의 거리가 다음과 같기 때문에 출력은 11이 됩니다. (1에서 3) 거리가 11, (3에서 5) 거리가 13, (1에서 5) 거리가 24이고, 그 중 11개가 최소값입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
N :=100005
-
MAX_VAL :=99999999
-
하나의 우선 순위 대기열 생성 q
-
결과 :=MAX_VAL
-
initialize 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에서 요소 삭제
-
-
q에 { 0, i } 삽입
-
좋은 :=0
-
동안(q가 비어 있지 않음) -
를 수행합니다.-
v :=q의 최상위 요소
-
q에서 요소 삭제
-
vis[v]가 참이면 -
-
다음 부분은 무시하고 다음 반복으로 건너뜁니다.
-
-
vis[v] :=1
-
good :=good + (good_verts[v]가 참이면 1, 그렇지 않으면 0)
-
dist[v]> 결과이면 -
-
루프에서 나오세요
-
-
good이 2 및 good_verts[v]와 같으면 -
-
result :=결과의 최소값과 dist[v]
-
루프에서 나오세요
-
-
j 초기화의 경우:=0, j <그래프[v]의 크기일 때 업데이트(j를 1만큼 증가), 수행 -
-
to :=그래프[v, j].첫 번째
-
가중치 :=그래프[v, j].초
-
dist[v] + weight
-
dist[to] :=dist[v] + 가중치
-
q에 { dist[to], to } 삽입
-
-
-
-
-
반환 결과
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
#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