[백준/C++] 1504번: 특정한 최단 경로

문제

https://www.acmicpc.net/problem/1504

1504번: 특정한 최단 경로

---

문제 요약

1번 정점부터 N번 정점까지 존재하는 방향성이 없는 그래프가 주어졌을 때, 1번 정점에서 N번 정점으로 최단

거리를 출력한다.

 

단, 임의로 주어진 두 정점을 반드시 통과해야 한다.

 

한 번 이동했던 정점 또는 간선을 다시 이동할 수 있다.

---

코드

#include<iostream>
#include<vector>
#include<tuple>
#include<cstring>
#include<queue>
#include<algorithm>

#define MAX_N 800

using namespace std;

int n, e, v1, v2; 

vector<tuple<int, int>> edges[MAX_N + 1];

int dist[MAX_N + 1]; // dist[i]: 출발 정점에서 각 노드까지의 최단 거리
int visited[MAX_N + 1]; 

queue<int> q;

void dijstra(int start) {

	// dist 초기화
	for (int i = 1; i <= n; i++) {
		dist[i] = 1e9;
	}
	dist[start] = 0; // 출발 정점에서 출발 정점까지의 거리 0

	// 다익스트라 시작
	q.push(start);
	while (!q.empty()) {
		int x = q.front();
		q.pop();

		for (int i = 0; i < edges[x].size(); i++) {
			int y, w;
			tie(y, w) = edges[x][i];
			if (dist[y] > dist[x] + w) {
				dist[y] = dist[x] + w;
				q.push(y);
			}
		}
	}
}

int main() {
	cin >> n >> e;

	// 그래프 입력
	for (int i = 0; i < e; i++) {
		int a, b, w;
		cin >> a >> b >> w;
		edges[a].push_back({ b, w });
		edges[b].push_back({ a, w });
	}

	cin >> v1 >> v2; // 반드시 거쳐야 하는 정점

	// 첫 번째 경우의 수: 1 -> v1 -> v2 -> n
	// 두 번째 경우의 수: 1 -> v2 -> v1 -> n
	int route1 = 0;
	int route2 = 0;
	bool flag1 = true;
	bool flag2 = true;

	dijstra(1);
	if (dist[v1] == 1e9) flag1 = false;
	if (dist[v2] == 1e9) flag2 = false;
	route1 += dist[v1]; // 1 -> v1
	route2 += dist[v2]; // 1 -> v2

	dijstra(v1);
	if (dist[v2] == 1e9) flag1 = false;
	if (dist[n] == 1e9) flag2 = false;
	route1 += dist[v2]; // v1 -> v2
	route2 += dist[n]; // v1 -> n

	dijstra(v2);
	if (dist[n] == 1e9) flag1 = false;
	if (dist[v1] == 1e9) flag2 = false;
	route1 += dist[n]; // v2 -> n
	route2 += dist[v1]; // v2 -> v1

	if (!flag1 && !flag2) cout << -1;
	else cout << min(route1, route2);
	
	return 0;
}

---

코드 설명

두 정점 v1, v2를 통과하는 1번 정점에서 N번 정점까지 가는 최단 경로는 두 경우의 수에서만 존재할 수 있다.

첫 번째 경우의 수: 1번 정점 -> v1 -> v2 -> N번 정점

두 번째 경우의 수: 1번 정점 -> v2 -> v1 -> N번 정점

 

즉, 각각 1번 정점, v1, v2에서 다익스트라 총 3번을 이용하면 모든 최단 경로의 경우의 수를 구할 수 있다.

 

1. 그래프 정보와 반드시 통과해야 하는 두 정점 v1, v2를 입력 받는다.

 

2. 시작 정점을 바꿔가며 다익스트라 알고리즘을 사용하여 각 노드들까지의 최단 거리를 계산한다.

 

3. 그 과정에서 원하는 최단 거리가 초기값이라면 (이동할 방법이 없다면)  flag 변수를 통해 체크해둔다.

 

4. 탐색이 종료된 후, 두 경우의 수 모두 flag가 체크되어 있다면, v1, v2를 통과하여 1번 정점에서 N번 정점까지 갈 수 없다는 의미이므로 -1을 출력하고, 아니라면 두 경우의 수 중 최소값을 출력한다.