[백준 2398] 3인 통화
문제 www.acmicpc.net/problem/2398 알고리즘 Dijkstra 풀이 세명이 통화를 하기 위해 간선들을 연결하기 위한 최소비용, 그 때 사용하는 간선들을 출력하는 문제입니다. 사람들이 그래프 위에서 움직여 최적의 장소에서 모이는 문제로 해석해보겠습니다. 각 사람마다 각 노드마다의 최소거리를 알 수 있다면 즉, 한 지점마다 세 사람의 최소거리를 안다면 우리는 어디 지점에서 세 사람이 만나야 하는지 알 수 있습니다. 사람마다 다익스트라를 돌려 총 세번의 다익스트라를 수행하고 그때마다 그 사람이 어디 노드에서 어디 노드로 갔는지를 기록하면 됩니다. 코드 #include #define rep(i, n) for (int i = 0; i < n; ++i) #define REP(i, n) for (..
Algorithm
2021. 4. 24. 15:02
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 좌표압축
- implementation
- 이분매칭
- hld
- dijkstra
- knapsack
- bfs
- 트라이
- Fenwick
- Suffix Array
- 이분탐색
- Oracle
- spring
- 2-SAT
- 동적계획법
- 펜윅트리
- 정렬
- 스위핑
- spring boot
- 세그먼트트리
- union find
- greedy
- sorting
- Segment tree
- sweeping
- dfs
- kmp
- SCC
- string
- DP
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
글 보관함