다익스트라7 [백준] 28315 - Minimum Cost Roads (c++) https://www.acmicpc.net/problem/28315 문제 요약정점이 N개 간선이 M개인 그래프가 있다. 간선마다 길이와 설치비용이 주어진다.모든 (u,v) 쌍의 최단경로를 보장하는 최소 설치비용을 구해라.풀이 (MN^2)MST다익스트라길이가 l인 간선으로 u와 v가 연결 돼 있다고 생각해보자. l보다 작거나 같은 u-v 경로가 존재 한다면 이 간선은 없어도 된다. 또한 이 경로는 당연하게 l보다 작은 간선으로 구성되기 때문에 크루스칼을 응용해 이 문제를 해결할 수 있다. 간선을 (길이,비용) 순으로 정렬하고 순회하며 l보다 작거나 같은 경로가 없을 때만 설치 해주면 된다. 매 번 다익을 돌려도 되고 n^2을 돌아도 무리가 없다.#include using namespace std;#defi.. 2025. 2. 26. [백준] 16763 - Fine Dining (c++) https://www.acmicpc.net/problem/16763 문제 요약정점이 N개이고 간선이 M개인 무방향 그래프가 주어진다. K개에 정점에 건초 묶음이 있고 각각 맛의 정도가 다르다. 1~N-1번 정점에 소가 한마리씩 있고 N번 정점으로 이동해야 한다. 소는 건초 묶음이 있는 점점에 들르기만 하면 건초를 먹을 수 있고 한 정점의 건초를 여러 소가 먹을 수 있다. 각 소에게 (건초를 먹는 경로-건초 맛) 풀이 (MlogN)다익스트라다익스트라를 두 번 돌려서 풀 수 있다. N번 정점을 시작으로 다익을 한 번 돌려 각 건초더미에서 N번 정점으로 가는 최단경로를 구해준다. 건초더미를 모두 시작 정점으로 설정하고 시작 가중치를 (건초더미->N 경로 - 맛)으로 설정해 다익을 한 번 돌려주면 (건초를 거쳐.. 2025. 1. 22. [백준] 27630 - Unique Ability (c++) https://www.acmicpc.net/problem/27630 문제 요약간선마다 타입이 있는 무방향 가중치 그래프가 주어진다. 간선을 지나려면 플레이어와 간선의 타입이 같아야 한다. 플레이어의 타입을 바꾸는데 타입의 차이만큼 비용이 들 때 1에서 N으로 가는 최단경로의 비용을 구해라. 풀이 (MlogM)다익스트라한 정점에 대해 연결된 간선의 타입들을 저장해둔다. 정점을 (번호,타입) 쌍으로 나누어 같은 번호 인접한(정렬 순서) 타입끼리 간선을 만들어준다.이렇게 새로 구성한 그래프에서 다익스트라를 한 번 돌려서 최단경로를 구할 수 있다.#include using namespace std;#define ll long longint main() { cin.tie(0)->sync_with_stdio(.. 2025. 1. 12. [백준] 5719 - 거의 최단 경로 (c++) https://www.acmicpc.net/problem/5719 문제 요약방향 그래프가 주어진다. 시작점과 도착점이 주어질 때 모든 최단 경로에 속하는 간선을 하나도 사용하지 않은 경로 중 최단경로의 길이를 구해라. 풀이 (MlogN)다익스트라다익스트라를 한 번 돌리면서 한 정점에 대해 최단경로로 도달할 수 있는 전 정점들을 연결하는 그래프를 구성해준다. 보통 다익스트라는 새로운 비용이 원래 비용보다 작을 때만 pq에 추가해주는데 같을 때도 추가해주면 된다. vis배열을 만들어 한 정점 대해 업데이트는 한 번만 되게 한다. 그렇게 구성한 그래프에서 d부터 s까지 역추적 해가며 포함되는 간선을 모두 지우면 s->d 최단경로의 속하는 간선을 모두 지울 수 있다.다익스트라 한 번 더 돌려주면 끝#inclu.. 2025. 1. 12. [백준] 28354 - 링크 컷 토마토 (c++) https://www.acmicpc.net/problem/28354 문제 요약토마토가 정점인 무방향 그래프가 주어진다. 각 토마토는 익거나 익지 않았다. 익은 토마토와 안 익은 토마토가 하루동안 연결 돼있으면 안 익은 토마토가 익게 된다. 이 그래프의 연결 상태는 중간에 바뀔 수 있다. 단 토마토 (u,v) 쌍에 대해 연결 상태는 최대 한 번만 변한다. 각 토마토가 익는 시간을 구해라. 풀이 ((M+Q)logN)다익스트라한 연결에 대해 시작시간과 끝시간을 미리 구해둔다. 다익스트라를 돌리며 끝시간이 지나지 않는 간선으로만 max(현재시간,연결시작시간)+1로 업데이트 한다. #include using namespace std;#define ll long longint main() { cin.tie(0.. 2025. 1. 11. [백준] 31602 - There and Back Again (c++) https://www.acmicpc.net/problem/31602 문제 요약가중치 있는 무방향 그래프가 주어진다. 1번 정점에서 n번 정점을 거쳐 1번 정점으로 돌아와야 한다. 다만 1에서 n으로 갈 때 거친 간선의 집합과 n에서 1로 갈 때 거친 간선의 집합이 같으면 안 된다. 최소 비용을 구해라. 풀이 (MlogN)다익스트라1에서 n으로 가는 다익을 한 번 돌리고 거친 간선의 집합을 저장해 놓는다. n에서 1로 가는 다익을 돌릴 땐 정점을 두배로 늘려서 한 번이라도 집합에 포함되지 않는 간선을 지난 정점과 아닌 정점을 구분한다. #include using namespace std;#define int long longsigned main() { cin.tie(0)->sync_with_stdio.. 2025. 1. 10. 이전 1 2 다음