algorithm/BOJ
BOJ 4888번 문시티 건설
_JunHo
2020. 2. 3. 16:31
BOJ : https://www.acmicpc.net/problem/4888
4888번: 문시티 건설
문제 인류의 과학 기술이 발전하여 달에도 도시를 지을 수 있게 되었다. 하지만 여전히 달에 무언가를 짓는 것은 굉장히 값비싼 비용이 필요하므로, N개의 도시가 있을 때 도시 간의 도로를 가능한 한 조금 지으려고 한다. 우리는 도로들이 크기 N인 싸이클을 형성하도록 만들려고 한다. 각 도시 쌍마다 사이를 왕복하는 도로를 건설하는 데 비용이 정해져 있다. 또한, 도시 i에서 도시 j로 가는 도로를 건설하면 추가적인 건설 없이 도시 j에서도 도시 i로 갈 수
www.acmicpc.net
채점 50%에서 틀렸다고 나온다.
어떤 부분이 틀렸는지 모르겠다....
나중에 반례나 설명을 듣게되면 다시풀어봐야겠다
작성해둔 코드
|
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
|
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#define MAX 999999999
using namespace std;
typedef pair<long long, long long> pii;
int N, C;
pii location[9];
long long dp[9][1 << 9];
long long cost[9][9];
int visit_fin;
void init() {
visit_fin = (1 << N) - 1;
for (int i = 0; i < N; i++)
cin >> location[i].first >> location[i].second;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
cin >> cost[i][j];
//for (int i = 0; i < N; i++)
// for (int j = 0; j < (1 << N); j++)
// dp[i][j] = 0;
memset(dp, 0, sizeof(dp));
}
long long ccw(pii a, pii b, pii c) {
int S = (b.first - a.first) * (c.second - a.second) - (b.second - a.second) * (c.first - a.first);
if (S < 0) return -1;
else if (S > 0) return 1;
return 0;
}
long long ccw_check(pii a, pii b, pii c, pii d) {
int ab = ccw(a, b, c) * ccw(a, b, d);
int cd = ccw(c, d, a) * ccw(c, d, b);
if (ab == 0 && cd == 0) {
if (a > b) swap(a, b);
if (c > d) swap(c, d);
return a <= d && b >= c;
}
return ab <= 0 && cd <= 0;
}
long long TSP(int start, int visit, vector<pii> v) {
vector<pii> in;
for (int i = 0; i < v.size(); i++) in.push_back(v[i]);
in.push_back({ location[start].first, location[start].second });
if (visit == visit_fin) {
if (cost[start][0] == 0) return MAX;
else {
in.push_back({ location[0].first, location[0].second });
long long cnt = 0;
for (int i = 0; i < in.size() - 3; i++) {
pii a = in[i];
pii b = in[i + 1];
for (int j = i + 2; j < in.size() - 1; j++) {
pii c = in[j];
pii d = in[j + 1];
if (c != a && d != a)
cnt += ccw_check(a, b, c, d)*2;
}
}
if (cnt) return cost[start][0] + ((cnt * (cnt - 1) * C / 2));
else return cost[start][0];
}
}
long long& result = dp[start][visit];
if (result) return dp[start][visit];
long long len = MAX;
for (int i = 1; i < N; i++) {
if (cost[start][i] != 0 && (visit & (1 << i)) == 0)
len = min(len, cost[start][i] + TSP(i, (visit | 1 << i), in));
}
return result = len;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
for (int t = 1; ; t++) {
cin >> N >> C;
if (!N && !C) break;
init();
vector<pii> v;
cout << t << ". " << TSP(0, 1, v) << "\n";
}
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter
|