[백준 알고리즘] 1504번: 특정한 최단 경로
March 23, 2021
https://www.acmicpc.net/problem/1504
문제
문제
방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.
세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.
입력
첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존재하며, 그 거리가 c라는 뜻이다. (1 ≤ c ≤ 1,000) 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 v1과 v2가 주어진다. (v1 ≠ v2, v1 ≠ N, v2 ≠ 1)
출력
첫째 줄에 두 개의 정점을 지나는 최단 경로의 길이를 출력한다. 그러한 경로가 없을 때에는 -1을 출력한다.
풀이
기존 다익스트라 알고리즘을 이용해서 풀 수 있었다. 사실 플로이드 와샬 알고리즘으로 한번에 모든 노드의 최소비용을 구하는 것도 방법이겠지만, 지금은 다익스트라를 공부하고 있기 때문에 다익스트라 알고리즘을 연속적으로 사용하는 방법으로 문제를 풀었다.
중간에 거쳐가야하는 지점 v1 과 v2 를 모두 들린채로 최소비용으로 이동하는 방법은 아래와 같이 두 가지 경우로 나누어진다.
- start -> v1 -> v2 -> end
- start -> v2 -> v1 -> end
정점이 많아져도 start 부터 v1까지의 최소비용, v1부터 v2까지의 최소비용, v2에서 end 까지의 최소비용은 다익스트라를 통해 한번에 구할 수 있다. 한가지 유념해야 할 것은 start -> v1 의 비용이 start -> v2 의 비용보다 저렴해도 총 비용이 적을 것이라는 보장이 없다는 것이다. 따라서 각 경우의 비용을 구해보고 더 작은 쪽은 최소비용으로 선택해야한다. 나는 다익스트라 알고리즘을 start(1번 정점) 을 출발점으로 한 번, v1을 출발점으로 한 번, v2를 출발점으로 한 번 수행해서 총 세 번의 다익스트라 함수를 호출했다. 그리고 반환받은 dist 배열에 들어있는 출발 정점으로부터 각 정점들 까지의 최소비용을 더해 최종 답을 구했다.
나는 INF 를 INT_MAX 매크로를 사용해서 선언했기 떄문에, 최종비용을 더하는 과정에서 overflow가 생길 가능성이 있다고 생각해서 비용에 대해서는 long long 자료형을 사용했다.
코드
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
vector<long long> dist(801);
vector<vector<pair<int, int>>> edges(801);
struct Compare {
bool operator()(pair<int, int>& a, pair<int, int>& b) {
return a.second > b.second;
}
};
vector<long long> dijkstra(int start) {
priority_queue<pair<int, int>, vector<pair<int, int>>, Compare> pq;
pq.push({ start, 0 });
dist[start] = 0;
while (!pq.empty()) {
int here = pq.top().first;
int hereCost = pq.top().second;
pq.pop();
for (auto next : edges[here]) {
int there = next.first;
int thereCost = next.second + hereCost;
if (dist[there] > thereCost) {
dist[there] = thereCost;
pq.push({ there, thereCost });
}
}
}
return dist;
}
void clearDist(int N) {
for (int i = 1; i <= N; i++) {
dist[i] = INT_MAX;
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(NULL);
int N, E;
cin >> N >> E;
for (int i = 0; i < E; i++) {
int a, b, c;
cin >> a >> b >> c;
edges[a].push_back({ b, c });
edges[b].push_back({ a, c });
}
int pointOne, pointTwo;
cin >> pointOne >> pointTwo;
clearDist(N);
auto fromStartDist = dijkstra(1);
clearDist(N);
auto fromPointOneDist = dijkstra(pointOne);
clearDist(N);
auto fromPointTwoDist = dijkstra(pointTwo);
long long pointOneFirst = fromStartDist[pointOne] + fromPointOneDist[pointTwo] + fromPointTwoDist[N];
long long pointTwoFirst = fromStartDist[pointTwo] + fromPointTwoDist[pointOne] + fromPointOneDist[N];
long long answer = min(pointOneFirst, pointTwoFirst);
if (answer < INT_MAX) {
cout << answer;
}
else {
cout << -1;
}
}
