Pagini recente » Cod sursa (job #2506941) | Cod sursa (job #54680) | Cod sursa (job #684812) | Cod sursa (job #1150710) | Cod sursa (job #2853991)
#include <bits/stdc++.h>
using namespace std;
ifstream f("bibel.in");
ofstream g("bibel.out");
const int N = 200, M = 17;
const long long INF64 = 0x3f3f3f3f3f3f3f3f;
int tip, x, y, n, d[M][M], m[N];
long long dp[M][1 << M], ans = INF64, last[M];
vector<pair<int, int>> nivel[N];
inline int dist(pair<int, int> a, pair<int, int> b){ // sau, mai bine zis, timpul necesar traversarii distantei dintre puncte
return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);
}
int main(){
while(f >> tip){
if(tip == 0){
f >> x >> y;
nivel[n].push_back({x, y});
m[n]++;
}else if(tip == 1)
n++;
else
break;
}
f.close();
for(int k = 0; k < m[0]; k++){
for(int j = 1; j < 1 << m[0]; j++){
dp[k][j] = INF64;
}
}
for(int j = 0; j < m[0]; j++)
dp[j][1 << j] = dist({0, 0}, nivel[0][j]); // setam valorile initiale (timpul pt. a parcurge dist. de la poz. initiala (0, 0) la punctele din primul nivel)
for(int i = 0; i < n; i++){
if(i){ // dist. de la bilele din nivelul anterior la cele din nivelul curent
for(int k = 0; k < m[i - 1]; k++) // ca sa nu gresim la cazul in care nivelul i - 1 are o singura bila
last[k] = dp[k][(1 << m[i - 1]) - 1];
for(int k = 0; k < m[i]; k++)
dp[k][1 << k] = INF64;
for(int j = 0; j < m[i - 1]; j++){
for(int k = 0; k < m[i]; k++){
dp[k][1 << k] = min(dp[k][1 << k], last[j] + dist(nivel[i - 1][j], nivel[i][k]));
}
}
for(int k = 0; k < m[i]; k++){ // resetam valorile pt. noul nivel
for(int j = 1; j < 1 << m[i]; j++){
if(j == 1 << k)
continue;
dp[k][j] = INF64;
}
}
}
for(int k = 0; k < m[i]; k++){ // precalculam dist. dintre punctele din nivelul curent
for(int t = 0; t < m[i]; t++){
d[k][t] = dist(nivel[i][k], nivel[i][t]);
}
}
for(int j = 1; j < 1 << m[i]; j++){
for(int k = 0; k < m[i]; k++){
if(j & (1 << k)){
for(int t = 0; t < m[i]; t++){
if(j & (1 << t))
continue;
dp[t][j + (1 << t)] = min(dp[t][j + (1 << t)], dp[k][j] + d[k][t]);
}
}
}
}
ans = INF64;
for(int k = 0; k < m[i]; k++)
ans = min(ans, dp[k][(1 << m[i]) - 1]);
g << ans << '\n';
}
g.close();
}