백준 문제 링크 : 1504번: 특정한 최단 경로 (acmicpc.net)
백준 1504번 문제 사진
문제 요약
입력 값 : n(정점 갯수), e(간선 갯수), a,b,c(간선 정보), v1,v2(반드시 지나야 하는 두 점)
- 시작점과 끝점은 반드시 1, n이다.
- 간선과 정점은 여러 번 사용할 수 있다.
- 반드시 지나야 하는 두 점이 있다.
문제 풀이 과정
이 문제를 한 줄로 요약하자면 입력된 두 정점을 반드시 지나는 1과 n 사이의 최단 경로의 길이를 출력하라는 말이 될 것 같습니다. 다만 간선이나 정점들을 중복하여 사용하는 것이 가능하기 때문에 최단 경로를 찾는데 제약이 많이 줄어들죠.
이 문제에서 반드시 지나야 하는 정점을 지나면서 시작점과 끝점을 이어주는 경우는 두 가지가 있습니다.
- v1이 n보다 1에 가까울 경우 [1 -> v1 -> v2 -> n]
- v1이 1보다 n에 가까울 경우 [1 -> v2 -> v1 -> n]
위 경로들의 길이 중 최솟값이 정답이 되죠. 이를 위해서 구해야 하는 값은 반드시 지나는 점들과 시작점, 끝점의 최단 경로의 길이 입니다.
이를 위해서 두 개의 정점을 입력 받고 해당 정점들 사이의 거리를 구해주는 함수를 만들어줘야 해요. 저는 distance_a2b라는 함수를 만든 후 최단 경로들을 구해 더해주는 방법을 사용했습니다.
#include <iostream>
#include <queue>
#include <vector>
#define MAX 1e8
using namespace std;
//입력 변수
int v,e;
int must_a,must_b;
//정점 벡터
vector<vector<pair<int,int>>> vertexes;
//거리 벡터
vector<int> vertex_distances;
//특정 정점 거리 연산 함수
int distance_a2b(int a,int b){
vertex_distances = vector<int>(v+1,MAX);
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> queue;
vertex_distances[a] = 0;
queue.push(pair<int,int>(0,a));
while (!queue.empty()) {
int cur_vertex = queue.top().second;
int cur_cost = queue.top().first;
queue.pop();
if (vertex_distances[cur_vertex] < cur_cost) {
continue;
}
for (int i = 0; i < vertexes[cur_vertex].size();i++) {
int v_vertex = vertexes[cur_vertex][i].second;
int v_distance = vertexes[cur_vertex][i].first + cur_cost;
if (vertex_distances[v_vertex] > v_distance) {
vertex_distances[v_vertex] = v_distance;
queue.push({v_distance,v_vertex});
}
}
}
return vertex_distances[b];
}
int main()
{
cin >> v >> e;
vertexes = vector<vector<pair<int,int>>>(v + 1);
for (int i = 0;i < e;i++) {
int a,b,cost;
cin >> a >> b >> cost ;
vertexes[a].push_back({cost,b});
vertexes[b].push_back({cost,a});
}
cin >> must_a >> must_b;
//반드시 지나야 하는 정점 거리 연산
int must_a2b = distance_a2b(must_a,must_b);
//반드시 지나야하는 정점과 시작 끝 정점 계산
int o2a = distance_a2b(1,must_a);
int o2b = distance_a2b(1,must_b);
int b2n = distance_a2b(must_b,v);
int a2n = distance_a2b(must_a,v);
//각각의 결과 합
int result_case_1 = o2a + must_a2b + b2n;
int result_case_2 = o2b + must_a2b + a2n;
//합 중 최솟값 선별
int result = min(result_case_1,result_case_2);
//출력
if (result >= MAX) {
cout << -1 << endl;
}
else {
cout << result << endl;
}
return 0;
}다익스트라 알고리즘을 사용한 다른 문제의 경우 아래 카테고리에서 찾아보실 수 있습니다.