[백준] 12752번 - 도시들
문제
https://www.acmicpc.net/problem/12752
풀이
특별한 알고리즘은 없고, 단순 다익스트라 문제이다.
많은 도시들이 있고 그 중 K(K <= 5)개의 도시를 연결하는 도로의 최소 비용을 구하면 된다.
1. K = 1
도로가 필요 없음
2. K = 2
두 개의 도시를 연결하는 최소 비용을 구하면 된다. 간단하게 다익스트라 1번으로 구할 수 있다.
3. K = 3
아래와 같은 경우들이 있을 수 있다. 각 점에서 출발해서 어떤 점에서 만난다고 생각하면 쉽다. K개의 도시(0, 1, 2 정점)
N개의 정점에서 만나는 경우 중 비용 합의 최소 값을 구한다.
A정점에서 만나는 경우: cost[0][A] + cost[1][A] + cost[2][A]
B정점에서 만나는 경우: cost[0][B] + cost[1][B] + cost[2][B]
...
4. K = 4
중복으로 더해지는 간선이 존재할 수 있다. 아래와 같은 경우는 K=3일 때와 같이 답을 구할 수 있지만,
이렇게 되버리면 중복으로 더해지는 간선이 생기게 된다.
따라서 두 점씩 묶어서 계산해주면 된다. 하지만 아래와 같은 경우가 생길 수 있기 때문에 모든 조합을 고려해서 최소 비용을 구해줘야 한다.
(0, 2), (1, 3)으로 조합할 경우 A또는 B에서 만날 때 AB 간선이 중복으로 합해진다.
(0, 1), (2, 3)으로 조합하면 A정점에서 만날 때 cost[0][1][A] + cost[2][3][A]로 답을 구할 수 있다.
5. K = 5
두 개의 그룹으로 묶을 수 없기 때문에 3개의 그룹(2, 2, 1)으로 묶어주고 마찬가지로 모두 계산하면서 답을 구해주면 된다.
코드
풀 때는 몰랐는데 지금 보니까 N < 100,000 이었음
조합을 따로 구하려다가 몇 개 없길래 그냥 품
#include <vector>
#include <cstring>
#include <queue>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int N, K, M;
struct Node {
int n;
long long cost;
bool operator<(const Node& o) const {
return cost > o.cost;
}
};
priority_queue<Node> pq;
long long ret[5][200001];
long long result[5][5][200001];
vector<Node> graph[200001];
int hashMap[5];
void dijkstra(int index) {
int start = hashMap[index];
for (int i = 1; i <= N; ++i) {
//10^15
ret[index][i] = 1000000000000000;
}
pq.push({ start, 0 });
ret[index][start] = 0;
while (!pq.empty()) {
Node now = pq.top();
pq.pop();
if (now.cost > ret[index][now.n]) continue;
for (int i = 0; i < graph[now.n].size(); ++i) {
Node nxt = graph[now.n][i];
long long nxtCost = nxt.cost + ret[index][now.n];
if (nxtCost >= ret[index][nxt.n]) continue;
ret[index][nxt.n] = nxtCost;
pq.push({ nxt.n, nxtCost });
}
}
}
void dijkstra2(int a, int b) {
for (int i = 1; i <= N; ++i) {
//a, b, i
result[a][b][i] = ret[a][i] + ret[b][i];
pq.push({ i, result[a][b][i] });
}
//a, b로부터 어떤x의 최단거리
while (!pq.empty())
{
Node now = pq.top();
pq.pop();
if (now.cost > result[a][b][now.n]) continue;
for (int i = 0; i < graph[now.n].size(); ++i) {
Node nxt = graph[now.n][i];
long long nxtCost = nxt.cost + result[a][b][now.n];
if (result[a][b][nxt.n] <= nxtCost) continue;
result[a][b][nxt.n] = nxtCost;
pq.push({ nxt.n, nxtCost });
}
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N >> K >> M;
for (int i = 0; i < K; ++i) {
cin >> hashMap[i];
}
for (int i = 0; i < M; ++i) {
int a, b;
long long c;
cin >> a >> b >> c;
graph[a].push_back({ b, c });
graph[b].push_back({ a, c });
}
// 다익
for (int i = 0; i < K; ++i) {
dijkstra(i);
}
// K 3이하는 중복이 일어나진 않음
if (K < 4) {
int minIndex = 0;
long long minCost = 5000000000000000;
for (int i = 1; i <= N; ++i) {
long long currCost = 0;
for (int j = 0; j < K; ++j) {
currCost += ret[j][i];
}
if (minCost > currCost) {
minCost = currCost;
minIndex = i;
}
}
cout << minCost;
}
else if (K == 4) {
for (int a = 0; a < K - 1; ++a) {
for (int b = a + 1; b < K; ++b) {
//10개 case. -> 다익 10개?
dijkstra2(a, b);
}
}
int gp[3][4] = {
{0, 1, 2, 3}
,{0, 2, 1, 3}
,{0, 3, 1, 2}
};
int minIndex = 0;
long long minCost = 5000000000000000;
for (int i = 1; i <= N; ++i) {
for (int g = 0; g < 3; ++g) {
long long currCost = result[gp[g][0]][gp[g][1]][i] + result[gp[g][2]][gp[g][3]][i];
if (minCost > currCost) {
minCost = currCost;
minIndex = i;
}
}
}
cout << minCost;
}
else if (K == 5) {
//5 * 3개 = 15
for (int a = 0; a < K - 1; ++a) {
for (int b = a + 1; b < K; ++b) {
//10개 case. -> 다익 10개?
dijkstra2(a, b);
}
}
int gp[15][5] = {
{0, 1, 2, 3, 4},{0, 2, 1, 3, 4},{0, 3, 1, 2, 4},
{0, 1, 2, 4, 3},{0, 2, 1, 4, 3},{0, 4, 1, 2, 3},
{0, 1, 3, 4, 2},{0, 4, 1, 3, 2},{0, 3, 1, 4, 2},
{0, 4, 2, 3, 1},{0, 2, 3, 4, 1},{0, 3, 2, 4, 1},
{1, 4, 2, 3, 0},{2, 4, 1, 3, 0},{3, 4, 1, 2, 0},
};
int minIndex = 0;
long long minCost = 5000000000000000;
for (int i = 1; i <= N; ++i) {
for (int g = 0; g < 15; ++g) {
long long currCost = result[gp[g][0]][gp[g][1]][i] + result[gp[g][2]][gp[g][3]][i] + ret[gp[g][4]][i];
if (minCost > currCost) {
minCost = currCost;
minIndex = i;
}
}
}
cout << minCost;
}
return 0;
}