BOJ 백준온라인져지 1504 특정한 최단 경로 풀이

1 -> N 의 최단거리를 구하면 된다.

조건 

1. v1 를 거쳐야 된다.

2. v2 를 거쳐야 된다.

3. 양방향 그래프다.

문제를 보니 민힙을 구현한 다익스트라를 사용해야 될 것 같았다.

풀이 방법

1 -> v1 -> v2 -> N
1 -> v2 -> v1 -> N

2 개중에 낮은 distance 를 출력하면 된다.

둘다 INF 면 -1 를 출력

다익스트라 알고리즘을 정리해보면

u -> v 의 minimum distance 를 구하는 알고리즘.

민힙을 사용해서 구현하면,

현재점을 startVertex, startVertex 에 연결된 점을 endVertex 라고 하자.

u -> startVertex -> endVertex 의 거리가

u -> 이미 간 점 -> endVertex 의 거리보다 작거나 처음 갱신한다면,

민힙에 push 해주고, 거리를 u -> startVertex -> endVertex 의 거리로 갱신해준다.

	#include <cstdio>
	#include <queue>
	#include <vector>
	/**
	* https://www.acmicpc.net/problem/1504
	* BOJ 백준온라인져지 1504 특정한 최단 경로 풀이
	*/
	#define INF 1e+9
	using namespace std;
	int vertexCount;
	vector<vector<pair<int, int> > > edges;
	int dijkstra (int start, int end) {
	int *distance = new int[vertexCount];
	distance[start] = 0;
	priority_queue<pair<int, int> > queue;
	queue.push(make_pair(0, start));
	for (int i = 1; i < vertexCount; i++) {
	if (start == i) continue;
	distance[i] = INF;
	}
	while (queue.size()) {
	int start = queue.top().second, startDist = queue.top().first;
	queue.pop();
	for (int i = 0; i < edges[start].size(); i++) {
	int there = edges[start][i].first;
	int newDist = startDist + edges[start][i].second;
	if (distance[there] > newDist) {
	distance[there] = newDist;
	queue.push(make_pair(newDist, there));
	}
	}
	}
	return distance[end];
	}
	int main () {
	int edgeCount;
	scanf("%d%d", &vertexCount, &edgeCount);
	edgeCount++, vertexCount++;
	edges.resize(vertexCount);
	for (int i = 1; i < edgeCount; i++) {
	int u, v, w;
	scanf("%d%d%d", &u, &v, &w);
	edges[u].push_back(make_pair(v, w));
	edges[v].push_back(make_pair(u, w));
	}
	int v1, v2;
	scanf("%d%d", &v1, &v2);
	int result = INF;
	int temp = dijkstra(1, v1);
	if (temp != INF) {
	int temp2 = dijkstra(v1, v2);
	if (temp2 != INF) {
	int temp3 = dijkstra(v2, vertexCount - 1);
	if (temp3 != INF) {
	result = temp + temp2 + temp3;
	}
	}
	}
	temp = dijkstra(1, v2);
	if (temp != INF) {
	int temp2 = dijkstra(v2, v1);
	if (temp2 != INF) {
	int temp3 = dijkstra(v1, vertexCount - 1);
	if (temp3 != INF) {
	if (result > temp + temp2 + temp3)
	result = temp + temp2 + temp3;
	}
	}
	}
	printf("%d", result == INF ? -1 : result);
	}

view raw BOJ_1504.cpp hosted with ❤ by GitHub

위의 3줄을 반복하면 정답이 나옴