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

9370번: 미확인 도착지 (acmicpc.net)

9370번: 미확인 도착지

 

9370번 : 미확인 도착지

---

(취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 출발했다는 것, 그리고 목적지 후보들 중 하나가 그들의 목적지라는 것이다. 그들이 급한 상황이기 때문에 목적지까지 우회하지 않고 최단거리로 갈 것이라 확신한다. 이상이다. (취익)

어휴! (요란한 옷차림을 했을지도 모를) 듀오가 어디에도 보이지 않는다. 다행히도 당신은 후각이 개만큼 뛰어나다. 이 후각으로 그들이 g와 h 교차로 사이에 있는 도로를 지나갔다는 것을 알아냈다.

이 듀오는 대체 어디로 가고 있는 것일까?

예제 입력의 두 번째 케이스를 시각화한 것이다. 이 듀오는 회색 원에서 두 검은 원 중 하나로 가고 있고 점선으로 표시된 도로에서 냄새를 맡았다. 따라서 그들은 6으로 향하고 있다.

 

입력

---

첫 번째 줄에는 테스트 케이스의 T(1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스마다

• 첫 번째 줄에 3개의 정수 n, m, t (2 ≤ n ≤ 2 000, 1 ≤ m ≤ 50 000 and 1 ≤ t ≤ 100)가 주어진다. 각각 교차로, 도로, 목적지 후보의 개수이다.
• 두 번째 줄에 3개의 정수 s, g, h (1 ≤ s, g, h ≤ n)가 주어진다. s는 예술가들의 출발지이고, g, h는 문제 설명에 나와 있다. (g ≠ h)
• 그 다음 m개의 각 줄마다 3개의 정수 a, b, d (1 ≤ a < b ≤ n and 1 ≤ d ≤ 1 000)가 주어진다. a와 b 사이에 길이 d의 양방향 도로가 있다는 뜻이다.
• 그 다음 t개의 각 줄마다 정수 x가 주어지는데, t개의 목적지 후보들을 의미한다. 이 t개의 지점들은 서로 다른 위치이며 모두 s와 같지 않다.

교차로 사이에는 도로가 많아봐야 1개이다. m개의 줄 중에서 g와 h 사이의 도로를 나타낸 것이 존재한다. 또한 이 도로는 목적지 후보들 중 적어도 1개로 향하는 최단 경로의 일부이다.

 

 

출력

---

테스트 케이스마다

• 입력에서 주어진 목적지 후보들 중 불가능한 경우들을 제외한 목적지들을 공백으로 분리시킨 오름차순의 정수들로 출력한다.

 

 

 

---

 

생각해 볼 점

---

1504번 문제와 유사하게, 다익스트라를 여러번 사용하여 푸는 문제입니다.

 

1504번은 A지점과 B지점을 경유하여 최단거리를 구했다면,

 

이 문제는 A와 B 사이의 경로를 지났음을 가정하고 최단거리를 구하므로

 

최단 거리 사이에 반드시 A와 B사이의 경로가 들어가야 합니다.

 

최단거리를 구하는 경우를 나누어 보면

 

1. 시작 -> A -> B -> 도착

2. 시작 -> B -> A -> 도착

 

이렇게 두가지로 나누어지므로,

 

노드 i에서 실행한 다익스트라를 Dijk(i)라고 하면,

 

다익스트라 알고리즘을 사용하여

 

Dijk(시작), Dijk(A), Dijk(B)를 구합니다.

 

1. Dijk(시작)

 

A지점, B 지점, 그리고 도착점으로의 최단거리를 구합니다. 도착점까지의 최단거리는 따로 저장해둡니다.

 

2. Dijk(A)

 

이 결과를 통해 A -> 도착점까지의 최단거리를 알 수 있습니다. 2번 경우를 계산합니다.

 

3. Dijk(B)

 

이 결과를 통해 B -> 도착점까지의 최단거리를 알 수 있습니다. 1번 경우를 계산합니다.

 

1번 경우의 계산식

 

Case 1 = (시작 -> A까지의 최단거리) + (A -> B의 거리) + (B -> 도착점까지의 최단거리)

Case 2 = (시작 -> B까지의 최단거리) + (B -> A의 거리) + (A -> 도착점까지의 최단거리)

 

도착점 후보가 여러개이므로, 모든 도착점이 1번에서 구한 최단거리와 동일한 지 확인하고,

동일하다면 노드 번호를 출력합니다.

 

마지막으로, 이전과 동일하게 시작점과 도착점이 A혹은 B가 아닌지 체크해야합니다.

 

예시 사례)

 

1

2 1 1

1 1 2

1 2 3

2

 

답 : 2

 

 

코드

---

#include <iostream>
#include <queue>
#include <vector>
#include <set>
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())
    {
        int current = pq.top().first;
        int curr_len = pq.top().second;
        pq.pop();
        if(dist[current] != 0 && dist[current] < curr_len) continue;
        for(pair<int, int> next : graph[current])
        {
            int next_len = curr_len + next.second;
            if(dist[next.first] == 0 || next_len < dist[next.first])
            {
                dist[next.first] = next_len;
                pq.push({next.first, next_len});
            }
        }
    }
}

int main() 
{
	int T;
	scanf("%d", &T);
	
	for(int tc = 0; tc < T; tc++)
	{
	    int n, m, t;
	    scanf("%d %d %d", &n, &m, &t);
	    
	    vector<pair<int, int>> dest;    //<목적지, 최단 거리>
	    graph = new vector<pair<int, int>>[n];
	    dist = new int[n];
	    fill_n(dist, n, 0);
	    
	    //s, g, h와 g & h 사이의 거리
	    int s, g, h, gh_dist;
	    scanf("%d %d %d", &s, &g, &h);
	    s--; g--; h--;
	    
	    //간선 입력
	    for(int i = 0; i < m; i++)
	    {
	        int a, b, d;
	        scanf("%d %d %d", &a, &b, &d);
	        a--; b--;
	        
	        if((a == g && b == h) || (a == h && b == g)) gh_dist = d;
	        graph[a].push_back({b, d});
	        graph[b].push_back({a, d});
	    }
	    
	    //도착 후보지 입력
	    for(int i = 0; i < t; i++) 
	    {
	        int cand;
	        scanf("%d", &cand);
	        dest.push_back({cand - 1, 0});
	    }
	    
	    //Case A = s -> g -> h -> end
	    //Case B = s -> h -> g -> end
	    int result_A = gh_dist;
	    int result_B = gh_dist;
	    
	    pq.push({s, 0});
	    dijk();
	    if(s != g) result_A += dist[g];
	    if(s != h) result_B += dist[h];
	    
	    //각 목적지에 최단거리 입력, 오름차순 정렬
	    for(int i = 0; i < t; i++) dest[i].second = dist[dest[i].first];
	    set<int> results;
        
	    //case A 마무리
	    fill_n(dist, n, 0);
	    pq.push({h, 0});
	    dijk();
	    dist[h] = 0;
	    for(pair<int, int> p : dest)
	    {
	        if(result_A + dist[p.first] == p.second) results.insert(p.first + 1);    
	    }
	    
	    
	    //Case B 마무리
	    fill_n(dist, n , 0);
	    pq.push({g, 0});
	    dijk();
	    dist[g] = 0;
	    for(pair<int, int> p : dest)
	    {
	        if(result_B + dist[p.first] == p.second) results.insert(p.first + 1);
	    }
	    
	    //출력부
	    for(int result : results) printf("%d ", result);
	    printf("\n");
	    
	    delete[] dist;
	    delete[] graph;
	}
	return 0;
}

 

그 외

---

문제에서 듀오는 반드시 최단거리로 이동한다고 말했으므로, 경유지를 포함해 구한 거리가 시작점 -> 도착지의 최단거리와 다를 경우 불가능이라 판단해야 합니다.