반응형
https://www.acmicpc.net/problem/13905
13905번: 세부
첫 번째 줄에는 섬에 존재하는 집의 수 N(2≤N≤100,000)와 다리의 수 M(1≤M≤300,000)이 주어진다. 두 번째 줄에는 숭이의 출발 위치(s)와 혜빈이의 위치(e)가 주어진다. (1≤s, e≤N, s≠e). 다음 M개의 줄
www.acmicpc.net
[ 문제풀이 ]
1. 모든 간선을 입력받습니다.
2. 입력받은 간선을 길이를 기준으로 내림차순으로 정렬합니다.
3. for문으로 모든 간선을 탐색하면서 Union-Find를 활용하여 이어줍니다.
4. s와 e 노드가 연결되면 연결된 간선 중 가장 짧은 간선의 길이를 출력합니다.
5. s와 e 노드가 연결될 수 없다면 0을 출력합니다.
[ 소스코드 ]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 | #include<iostream> #include<algorithm> #include<vector> using namespace std; struct node { int h1; int h2; int k; }; bool cmp(node left, node right) { return left.k > right.k; } int N, M; int s, e; node arr[300001]; int vect[100001]; int Find(int num) { if (vect[num] == num) return num; return vect[num] = Find(vect[num]); } void Union(int a, int b) { int pa = Find(a); int pb = Find(b); vect[pb] = pa; } int main() { scanf("%d %d", &N, &M); scanf("%d %d", &s, &e); for (int i = 1; i <= N; i++) { vect[i] = i; } for (int i = 0; i < M; i++) { scanf("%d %d %d", &arr[i].h1, &arr[i].h2, &arr[i].k); } int ans = 987654321; sort(arr, arr + M, cmp); for (int i = 0; i < M; i++) { const int h1 = arr[i].h1; const int h2 = arr[i].h2; const int k = arr[i].k; if (Find(h1) != Find(h2)) { Union(h1, h2); ans = min(ans, k); } if (Find(s) == Find(e)) { printf("%d", ans); return 0; } } printf("0"); } | cs |
반응형
'백준' 카테고리의 다른 글
[ 백준 ] 16202번 - MST 게임 (C++) (0) | 2023.03.07 |
---|---|
[ 백준 ] 21924번 - 도시 건설 (C++) (0) | 2023.03.06 |
[ 백준 ] 5972번 - 택배 배송 (C++) (0) | 2023.03.04 |
[ 백준 ] 14284번 - 간선 이어가기 2 (C++) (0) | 2023.03.03 |
[ 백준 ] 17396번 - 백도어 (C++) (0) | 2023.03.02 |