BOJ 1504 : 특정한 최단 경로

알고리즘 문제 전체 링크

 

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

 

참고

- BOJ 11779 : 최소비용 구하기 2

 

 

최단 경로는 BOJ 11779 : 최소비용 구하기 2에서 사용한 다익스트라를 이용해서 구할 수 있다.

 

이 문제에서는 임의의 두 정점(n1, n2)을 통과하는 최단 경로를 구하려고 하므로,

다익스트라를 여러 번 사용하면 된다.

 

즉, 출발점 - n1 - n2 - 도착점에 대해 각각 다익스트라를 이용해 거리를 구한다.

여기서 n1이 반드시 n2 보다 먼저 도착해야할 이유는 없다.

n1 - n2와 n2 - n1 경로를 비교해서 더 작은 경우가 정답이 된다.

ans1 = getDijkstra(1, n1) + getDijkstra(n1, n2) + getDijkstra(n2, N);
ans2 = getDijkstra(1, n2) + getDijkstra(n2, n1) + getDijkstra(n1, N);
ans3 = (ans1 < ans2) ? ans1 : ans2;

 

전체 코드는 다음과 같다.

#include <stdio.h>

typedef long long int ll;

#define MAX (810)
#define INF (0x7fff0000)

int N, M;
int map[MAX][MAX];

typedef struct st2
{
	int node;
	int value;
}EDGE;

EDGE heap[100100];
int hn;

EDGE pop()
{
	EDGE ret, tmp;

	ret = heap[1];
	heap[1] = heap[hn];
	heap[hn--].value = INF;

	for (int i = 1; i * 2 <= hn;)
	{
		if (heap[i].value < heap[i * 2].value && heap[i].value < heap[i * 2 + 1].value) break;
		else if (heap[i * 2].value < heap[i * 2 + 1].value)
		{
			tmp = heap[i * 2];
			heap[i * 2] = heap[i];
			heap[i] = tmp;

			i = i * 2;
		}
		else
		{
			tmp = heap[i * 2 + 1];
			heap[i * 2 + 1] = heap[i];
			heap[i] = tmp;

			i = i * 2 + 1;
		}
	}

	return ret;
}

void push(EDGE x)
{
	EDGE tmp;
	heap[++hn] = x;

	for (int i = hn; i > 1; i /= 2)
	{
		if (heap[i / 2].value < heap[i].value) break;

		tmp = heap[i];
		heap[i] = heap[i / 2];
		heap[i / 2] = tmp;
	}
}


ll getDijkstra(int node, int end)
{
	ll dist[MAX];
	int visit[MAX] = { 0 };

	for (int i = 1; i <= N; i++) dist[i] = INF;

	dist[node] = 0;
	push({ node, 0 });

	while (hn)
	{
		EDGE tmp;
		tmp = pop();

		if (visit[tmp.node]) continue;
		visit[tmp.node] = 1;

		for (int i = 1; i <= N; i++)
		{
			if (!map[tmp.node][i] || tmp.node == i) continue;

			if (dist[i] > dist[tmp.node] + map[tmp.node][i])
			{
				dist[i] = dist[tmp.node] + map[tmp.node][i];
				push({ i, dist[i] });
			}
		}
	}

	return dist[end];
}

int main()
{
	int n1, n2;
	ll ans1, ans2, ans3;

	scanf("%d %d", &N, &M);

	for (int i = 0; i < M; i++)
	{
		int p, c, w;

		scanf("%d %d %d", &p, &c, &w);

		if (p == c) continue;
		if (map[p][c] == 0) map[p][c] = map[c][p] = w;
		else if (map[p][c] > w) map[p][c] = map[c][p] = w;
	}

	scanf("%d %d", &n1, &n2);

	ans1 = getDijkstra(1, n1) + getDijkstra(n1, n2) + getDijkstra(n2, N);
	ans2 = getDijkstra(1, n2) + getDijkstra(n2, n1) + getDijkstra(n1, N);
	ans3 = (ans1 < ans2) ? ans1 : ans2;

	if (ans3 >= INF) printf("-1\n");
	else printf("%lld\n", ans3);

	return 0;
}