반응형
https://www.acmicpc.net/problem/1504
참고
최단 경로는 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;
}
반응형
'알고리즘 > BAEKJOON' 카테고리의 다른 글
BOJ 1991 : 트리 순회 (0) | 2023.04.07 |
---|---|
BOJ 6593 : 상범 빌딩 (0) | 2023.03.26 |
BOJ 12899 : 데이터 구조 (0) | 2023.03.04 |
BOJ 1168 : 요세푸스 문제 2 (1) | 2023.03.04 |
BOJ 2042 : 구간 합 구하기 with 다이나믹 세그먼트 트리 (Dynamic Segment Tree) (0) | 2023.02.08 |
댓글