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

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

1504번: 특정한 최단 경로

 

1번 집에서 주어진 두 집(n1, n2)을 거친 후 N번째 집까지 가는 거리 중 최단 거리를 구하는 문제이다. 

 

위 문제에서 양방향은 같은 간선의 길이를 가지므로, 1번에서 두 집을 거쳐서 N까지 가는 경우의 수는 두가지이다. 

 

1 -> n1 + n1 -> n2 + n2 -> N

 

vs 

 

1 -> n2 + n2 -> n1 + n1 -> N

 

위에 화살표들은 연결된 상태가 아니라 최단거리를 나타내는 것이다. 

 

그래서 두 가지 거리 중 더 작은 거리를 출력한다. 

 

이제 최단거리를 어떻게 구하냐이다.

 

플로이드 와샬을 사용하기로 생각했다. 다 익스트라로 구할 수 있지만 플로이드 와샬의 구현이 훨씬 간편하고, O(N^3) 약 10^8 이라서 일단 사용했다. 

 

만약 다익스트라로 문제를 푼다면 1에서, n1에서, n2에서 세번 사용해야 했을 것이다. 

 

플로이드 와샬은 헷갈릴만한 딱 한가지만 기억하면 된다. 

 

삼중 반복문에서

i,j,k중 i가 지나는 점.

#include<iostream>
#include<algorithm>
using namespace std;
#define MAX 801

int grap[MAX][MAX];
int N, E, a, b, c, num1, num2, INF = 987654321;
bool answer = true;

void floid() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			for (int a = 1; a <= N; a++) {
				if (grap[j][a] > grap[j][i] + grap[i][a])
					grap[j][a] = grap[j][i] + grap[i][a];
			}
		}
	}

}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin >> N >> E;
	for (int i = 0; i < E; i++) {
		cin >> a >> b >> c;
		grap[a][b] = c;
		grap[b][a] = c;
	}
	cin >> num1 >> num2;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (i == j) continue;
			if (grap[i][j] == 0) grap[i][j] = 987654321;
		}
	}
	floid();
	if (grap[1][num1] == INF || grap[num1][num2] == INF || grap[num2][N] == INF) answer = false;
	if(answer)
		cout << min((grap[1][num1] + grap[num1][num2] + grap[num2][N]), (grap[1][num2] + grap[num2][num1] + grap[num1][N])) << "\n";
	else cout << -1 << "\n";
}

 

문제 조건에서 중복된 거리로 이동할 수 있다고 했지만 어차피 최단 거리를 구하는 문제라서 그냥 무시했다. 

 

그리고 만약에 거리가 그대로 INF인 경우에는 경로가 존재하지 않는다고 보고 -1을 출력했다.