[C++]백준 - 1504번 문제

[C++]백준 - 1504번 문제

1504번: 특정한 최단 경로 (acmicpc.net)

1504번 : 특정한 최단 경로

방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.

세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존재하며, 그 거리가 c라는 뜻이다. (1 ≤ c ≤ 1,000) 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 v1과 v2가 주어진다. (v1 ≠ v2, v1 ≠ N, v2 ≠ 1)

출력

첫째 줄에 두 개의 정점을 지나는 최단 경로의 길이를 출력한다. 그러한 경로가 없을 때에는 -1을 출력한다.

생각해 볼 점

다익스트라를 사용하여 최단 거리를 구할 것입니다.

그런데, 경유지 A와 경유지 B를 거쳐서갈 것이므로,

결과적으로 다음과 같은 경로를 갖게 됩니다.

1번 경우

0 -> A -> B -> 도착점

2번 경우

0 -> B -> A -> 도착점

그러면 다익스트라를 총 3번을 이용해야함을 알 수 있습니다.

우선 시작점(0)에서 다익스트라 알고리즘을 사용해보면,

0 -> A의 최단거리

0 -> B의 최단거리

그리고, 0 -> 도착점이 연결되어 있는지를 확인할 수 있습니다.

만약, 도착점이 갱신되지 않고 INF 상태라면 -1을 출력하고 여기서 종료합니다.

다음은 A에서 다익스트라 알고리즘을 사용하여

A -> B의 최단거리

A -> 도착점의 최단거리

두가지의 최단거리를 구할 수 있습니다.

마지막으로 B에서 다익스트라 알고리즘을 사용하여

B -> 도착점의 최단거리

B -> A의 최단거리

두가지의 최단거리를 구할 수 있습니다.

주황색 글씨로 되어있는 것들을 합치면 1번 경우를,

파란색 글씨로 되어있는 것들을 합치면 2번 경우를 완성할 수 있습니다.

두 경우를 비교하여 더 짧은 쪽이 정답이 됩니다.

하지만, 여기까지만 풀면 오답을 볼 수 있습니다.

예제 입력이 다음과 같다면 어떨까요?

2 1

1 2 1

즉, 시작점이 A 혹은 B일 수 있고, 도착점이 A 혹은 B일 수 있습니다.

시작점과 도착점이 A, B 노드와 같을 경우에는 중복 연산이 일어날 수 있으니, 해당 경우를 배제해주셔야 합니다.

코드

#include #include #include #include using namespace std; //비교 함수 struct cmp { bool operator()(pair A, pair B) { return A.second > B.second; } }; vector> *graph; int* dist; priority_queue, vector>, cmp> pq; //다익스트라 void dijk() { while(!pq.empty()) { pair current = pq.top(); pq.pop(); if(0 < dist[current.first] && dist[current.first] < current.second) continue; for(pair next : graph[current.first]) { int d = dist[current.first] + next.second; if(d < dist[next.first] || dist[next.first] == 0) { dist[next.first] = d; pq.push({next.first, d}); } } } } int main() { int N, E; scanf("%d %d", &N;, &E;); graph = new vector>[N]; dist = new int[N]; fill_n(dist, N, 0); for(int i = 0; i < E; i++) { int a, b, c; scanf("%d %d %d", &a;, &b;, &c;); graph[a-1].push_back({b-1, c}); graph[b-1].push_back({a-1, c}); } //경유할 노드들 int node_A, node_B; scanf("%d %d", &node;_A, &node;_B); node_A--; node_B--; //result_A = 0 -> A -> B -> N-1 //result_B = 0 -> B -> A -> N-1 int result_A = 0; int result_B = 0; //A 혹은 B가 시작점이라면 실행하지 않음 if(node_A != 0 && node_B != 0) { //0번 노드 다익스트라 pq.push({0, 0}); dijk(); result_A += dist[node_A]; result_B += dist[node_B]; //A 노드, B 노드, 도착점 셋 중 하나라도 도달할 수 없다면 종료 if(dist[node_A] == 0 || dist[node_B] == 0 || dist[N - 1] == 0) { printf("-1"); delete[] graph; delete[] dist; return 0; } } //A가 도착점이라면 실행하지 않음 if(node_A != N - 1) { //A 경유지 다익스트라 fill_n(dist, N, 0); pq.push({node_A, 0}); dijk(); result_A += dist[node_B]; result_B += dist[N - 1]; } //B가 도착점이라면 실행하지 않음 if(node_B != N - 1) { //2번 경유지 -> 도착 fill_n(dist, N, 0); pq.push({node_B, 0}); dijk(); result_A += dist[N - 1]; result_B += dist[node_A]; } //A 노드, B 노드, 도착점 셋 중 하나라도 도달할 수 없다면 종료 if(dist[node_A] == 0 || dist[node_B] == 0 || dist[N - 1] == 0) { printf("-1"); delete[] graph; delete[] dist; return 0; } printf("%d", min(result_A, result_B)); delete[] graph; delete[] dist; return 0; }

그 외

from http://popoli31.tistory.com/88 by ccl(A) rewrite - 2021-08-25 17:00:07