백준 1504 - 특정한 최단 경로(C++)

문제 링크입니다. https://www.acmicpc.net/problem/1504

1504번: 특정한 최단 경로

다익스트라를 여러번 사용하면 되는 문제입니다.

다익스트라를 여러번 사용해야 되는 문제입니다.

다익스트라 알고리즘을 모르신다면 https://junseok.tistory.com/187 를 참고해주세요

문제에서 주어진 두 정점을 무조건 지났을 때의 최솟값을 구하는 문제입니다. 이 두점을 First, Second로 정하겠습니다.

 

1번 정점에서 시작해 First와 Second를 지나고 N점까지 도착할 수 있는 길은 2가지입니다.

1. 1번 정점 -> First -> Second -> N

2. 2번 정점 -> Second -> First -> N

이 두 방법중 하나 이상이 가능할 때, 최솟값을 비교한 뒤, 출력해주면 됩니다.

두 방법 전부 불가능할 때, -1를 출력해주면 됩니다.

 

그렇다면 먼저 구해야할 것은 

"1 -> First로 갈 수 있냐" , "1 - > Second로 갈 수 있냐" 를 확인해야합니다.

 

그 다음으로는 "First -> Second로 갈 때의 값"을 구해야합니다. "Second -> First로 갈 때의 값"을 구하지 않아도 되는 이유는 간선이 양방향이기에, 둘 중 한개의 값만 구하면 다른 값도 같은 값으로 나오기 때문입니다.

 

마지막으로는 "First -> N으로 갈 때의 값" , "Second -> N으로 갈 때의 값" 을 각각 구해주면 됩니다.

구한 값을 각각의 루트 값에 더해주면 됩니다.

 

 

1. 1 -> First로 갈 수 있냐 , 1 - > Second로 갈 수 있냐

	Dijkstra(1);
	ans_A = Distance[First];
	ans_B = Distance[Second];
	if (ans_A == INF) go_A = false;
	if (ans_B == INF) go_B = false;

다익스트라를 1번 점에서 시작합니다.

1번 점에서 시작했을 때, First or Second에 도착하지 못했다면 N번 점까지 도달하지 못한다는 의미임으로 false로 바꿔줬습니다.

 

 

2. First -> Second로 갈 때의 값

Dijkstra(First);
	if (go_A) ans_A += Distance[Second];
	if (go_B) ans_B += Distance[Second];

First에서 시작해서 Second로 도착한 값을 구해줍니다.

1번과 First가 연결되어 있다면(go_A 값이 true일 때) 해당 값을 더해줍니다.

1번과 Second가 연결되어 있다면(go_B 값이 true일 때) 해당 값을 더해줍니다.

 

 

3. First -> N으로 갈 때의 값 , Second -> N으로 갈 때의 값

	Dijkstra(Second);
	if (go_A) ans_A += Distance[N];
	Dijkstra(First);
	if (go_B) ans_B += Distance[N];

Second에서 시작해 N으로 가는 값을 구했다면 "1번 정점 -> First -> Second -> N" 의 경우입니다. 따라서 해당 값에 더해줍니다.

First에서 시작해 N으로 가는 값을 구했다면 "2번 정점 -> Second -> First -> N" 의 경우입니다. 따라서 해당 값에 더해줍니다.

 

 

자세한 것은 코드를 참고해주세요

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#define INF 210000000000

using namespace std;

priority_queue < pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> q;
long long Distance[801];
int N, M;
int First, Second;
vector<pair<int, int>> line[801];

void reset_Distance() {
	for (int i = 1; i <= N; i++) {
		Distance[i] = INF;
	}
}

void Dijkstra(int start) {
	reset_Distance();
	Distance[start] = 0;
	q.push({ 0, start });
	while (!q.empty()) {
		int x = q.top().second;
		int cost = q.top().first;
		q.pop();
		for (int i = 0; i < line[x].size(); i++) {
			int xx = line[x][i].first;
			int Cost = line[x][i].second;
			if (Distance[xx] > Distance[x] + Cost) {
				Distance[xx] = Distance[x] + Cost;
				q.push({ Distance[xx] , xx });
			}
		}
	}
}

void solve() {
	bool go_A = true, go_B = true;
	long long ans_A = 0, ans_B = 0;
	/////////////////////////////////////////////// 길찾기 시작
	Dijkstra(1);
	ans_A = Distance[First];
	ans_B = Distance[Second];
	if (ans_A == INF) go_A = false;
	if (ans_B == INF) go_B = false;
	Dijkstra(First);
	if (go_A) ans_A += Distance[Second];
	if (go_B) ans_B += Distance[Second];
	Dijkstra(Second);
	if (go_A) ans_A += Distance[N];
	Dijkstra(First);
	if (go_B) ans_B += Distance[N];
	////////////////////////////////////////////// 길찾기 완료
	if (!go_A && !go_B) cout << "-1";
	else {
		long long ans = min(ans_A, ans_B);
		if (ans == INF) cout << "-1";
		else cout << ans;
	}
}

int main()
{
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int x, y, cost;
		cin >> x >> y >> cost;
		line[x].push_back({ y,cost });
		line[y].push_back({ x,cost });
	}
	cin >> First >> Second;
	solve();
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요