on
[C++]백준 - 9370번 문제
[C++]백준 - 9370번 문제
9370번: 미확인 도착지 (acmicpc.net)
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 #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()) { int current = pq.top().first; int curr_len = pq.top().second; pq.pop(); if(dist[current] != 0 && dist[current] < curr_len) continue; for(pair 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> dest; //<목적지, 최단 거리> graph = new vector>[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 results; //case A 마무리 fill_n(dist, n, 0); pq.push({h, 0}); dijk(); dist[h] = 0; for(pair 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 p : dest) { if(result_B + dist[p.first] == p.second) results.insert(p.first + 1); } //출력부 for(int result : results) printf("%d ", result); printf("
"); delete[] dist; delete[] graph; } return 0; }
그 외
문제에서 듀오는 반드시 최단거리로 이동한다고 말했으므로, 경유지를 포함해 구한 거리가 시작점 -> 도착지의 최단거리와 다를 경우 불가능이라 판단해야 합니다.
from http://popoli31.tistory.com/89 by ccl(A) rewrite - 2021-08-25 19:00:16