Pagini recente » Cod sursa (job #1017047) | Cod sursa (job #1366196) | Diferente pentru implica-te/arhiva-educationala intre reviziile 213 si 212 | Cod sursa (job #1007773) | Cod sursa (job #355115)
Cod sursa(job #355115)
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define FIN "bibel.in"
#define FOUT "bibel.out"
#define N 18
#define MAXST 131072
int d1[N][MAXST], d2[N][MAXST];
pair <int, int> v1[N], v2[N];
inline int dist(pair <int, int> a, pair <int, int> b)
{
return ((b.first - a.first) * (b.first - a.first) + (b.second - a.second) * (b.second - a.second));
}
void solve()
{
int i, st, k;
for (i = 0; i <= 17; ++ i)
{
memcpy(d1[i], d2[i], sizeof(d2[i]));
for (k = 0; k < (1 << 17); ++ k)
d2[i][k] = MAXST;
}
for (i = 0; i < v2[0].first; ++ i)
for (k = 0; k < v1[0].first; ++ k)
d2[i][(1 << i)] = min(d2[i][(1 << i)], d1[k][(1 << v1[0].first) - 1] + dist(v2[i + 1], v1[k + 1]));
for (st = 0; st < (1 << (v2[0].first)); ++ st)
for (i = 0; i < v2[0].first; ++ i)
if (st & (1 << i))
for (k = 0; k < v2[0].first; ++ k)
if (!(st & (1 << k)))
d2[i][st] = min(d2[i][st], d2[k][st - (1 << k)] + dist(v2[i + 1], v2[k + 1]));
}
int main()
{
int i, t = 0, a, b, r;
freopen(FIN, "r", stdin);
freopen(FOUT, "w", stdout);
v1[v1[0].first = 1] = make_pair(0, 0);
while (t != 2)
{
scanf("%d", &t);
if (!t)
{
scanf("%d%d", &a, &b);
v2[++ v2[0].first].first = a;
v2[v2[0].first].second = b;
}
if (t == 1)
{
solve();
for (i = 0, r = MAXST; i < v2[0].first; ++ i)
r = min(r, d2[i][(1 << v2[0].first) - 1]);
printf("%d\n", r);
memcpy(v1, v2, sizeof(v2));
v2[0].first = 0;
}
}
}