백준/1504번(최단 경로)/C++

문제 설명

 

필수로 지나야 하는 정점이 두 개 주어지는 최단 경로 문제. 

 

주의할 점:

필수 정점의 순서는 주어지지 않는다. v1을 먼저 가도 되고, v2를 먼저 가도 된다.

 

 

 

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

#define MAX 805
#define INF 98765432

using namespace std;

int N, E, v1, v2;

vector <pair<int, int>> graph[MAX];
int d[MAX];


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

void input(){
	cin >> N >> E;

	for (int i = 0; i < E; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		graph[a].push_back(make_pair(b, c));
		graph[b].push_back(make_pair(a, c));
	}

	cin >> v1 >> v2;
}

int Ndijkstra(int start, int end) {
	priority_queue<pair<int, int>> pq;
	d[start] = 0;
	pq.push(make_pair(0, start));

	while (pq.empty() == 0) {
		int current = pq.top().second;
		int cDistance = -pq.top().first;
		pq.pop();

		if (cDistance > d[current]) continue;

		for (int i = 0; i < graph[current].size(); i++) {
			int next = graph[current][i].first;
			int nDistance = cDistance + graph[current][i].second;

			if (d[next] > nDistance) {
				d[next] = nDistance;
				pq.push(make_pair(-d[next], next));
			}
		}
	}

	return d[end];
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int result1, result2;

	input();
	init();
	result1 = Ndijkstra(1, v1);
	init();
	result1 += Ndijkstra(v1, v2);
	init();
	result1 += Ndijkstra(v2, N);

	init();
	result2 = Ndijkstra(1, v2);
	init();
	result2 += Ndijkstra(v2, v1);
	init();
	result2 += Ndijkstra(v1, N);

	int result = min(result1, result2);

	if (result >= INF) {
		cout << -1;
	}
	else {
		cout << result;
	}
}

 

 

 

디버깅 기록

: Dijkstra 알고리즘을 활용해서 1부터 v1까지, v1부터 v2까지, v2부터 N까지의 최단 경로를 각각 구한 후 합산한다는 아이디어는 좋았다. 다만, v1과 v2의 순서가 정해져 있지 않다는 점을 간과해 틀렸었다. 가능한 모든 경우의 수를 머리로 그리려고 노력해봐야지. 그리고 처음에는 input함수 안에서 init함수를 시행시켰는데 제대로 시행되지 않았다. 이제 와서 생각해보니, N을 입력받기도 전에 N을 포함하고 있는 for문이 들어있는 init함수를 시행시켜서 그런 것 같다. 전역변수를 사용할 때는 주의, 또 주의!