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

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

1504번: 특정한 최단 경로

 

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 <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

//비교 함수
struct cmp
{
    bool operator()(pair<int, int> A, pair<int, int> B)
    {
        return A.second > B.second;
    }
};

vector<pair<int, int>> *graph;
int* dist;
priority_queue<pair<int, int>, vector<pair<int,int>>, cmp> pq;

//다익스트라
void dijk()
{
    while(!pq.empty())
	{
	    pair<int, int> current = pq.top();
	    pq.pop();
	    
	    if(0 < dist[current.first] && dist[current.first] < current.second) continue;
	    for(pair<int, int> 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<pair<int, int>>[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;
}

 

그 외

---