문제링크
https://www.acmicpc.net/problem/1504
풀이방법
해당 문제는 다익스트라 알고리즘을 이용하여 해결할 수 있다. 풀이 방법은 다음과 같다.
- 우선 solve라는 함수를 만들고 int st, int en을 추가해서 st 부터 en까지 최단 거리 값을 알려주는 함수를 만든다.
- 1~N까지의 경로 중에 v1과 v2를 반드시 지나는 경우는 딱 두 가지 케이스가 존재한다.
(~~~ 중간에 다른 경로를 의미한다. 중간에 다른 경로가 없을 수도 있다.)
(1) 1~~~V1을 지나고 V1부터 ~~~ V2를 거쳐서 V2~~~n에 도달하는 방법
(2) 1~~~V2를 지나고 V2부터 ~~~ V1을 거쳐서 V1~~~n에 도달하는 방법
위 두 케이스만 존재한다. - 두 케이스에서 작은 값을 최종 결과 값에 넣는다.
- 만약에 결과 값이 INF보다 크다면 해당 경로는 존재하지 않으므로 -1을 출력하고 아닌경우 최종 결과 값이 최소 값이므로 해당 값을 출력한다.
코드
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int n, e, v1, v2;
vector<pair<int, int>> adj[1005]; // {거리, 정점 번호}
const int INF = 0x3f3f3f3f;
long long solve(int st, int en)
{
int d[1005];
fill(d, d + n + 1, INF);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>> > pq;
d[st] = 0;
// 우선순위 큐에 (0, 시작점) 추가
pq.push({ d[st],st });
while (!pq.empty()) {
auto cur = pq.top(); pq.pop(); // {거리, 정점 번호}
// 거리가 d에 있는 값과 다를 경우 넘어감
if (d[cur.Y] != cur.X) continue;
for (auto nxt : adj[cur.Y]) {
if (d[nxt.Y] <= d[cur.Y] + nxt.X) continue;
// cur를 거쳐가는 것이 더 작은 값을 가질 경우
// d[nxt.Y]을 갱신하고 우선순위 큐에 (거리, nxt.Y)를 추가
d[nxt.Y] = d[cur.Y] + nxt.X;
pq.push({ d[nxt.Y],nxt.Y });
}
}
return d[en];
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> e;
while (e--) {
int a, b, c;
cin >> a >> b >> c;
adj[a].push_back({ c,b });
adj[b].push_back({ c,a });
}
cin >> v1 >> v2;
long long ans1 = solve(1, v1) + solve(v1, v2) + solve(v2, n);
long long ans2 = solve(1, v2) + solve(v2, v1) + solve(v1, n);
long long ans = min(ans1, ans2);
if (ans >= INF) ans = -1;
cout << ans;
}
'CS(Computer Science)지식 > [C++][코딩 테스트] 자료구조 및 알고리즘' 카테고리의 다른 글
[C++] 백준 1786번: 찾기 (0) | 2024.02.03 |
---|---|
백준 14938번: 서강그라운드 (C++) (0) | 2024.02.03 |
백준 11779번: 최소비용 구하기 2 (C++) (0) | 2024.02.03 |
백준 1753번: 최단경로 (C++) (0) | 2024.02.03 |
백준 21940번: 가운데에서 만나기 (C++) (0) | 2024.02.03 |