Getting in Line
unknown
c_cpp
2 years ago
2.1 kB
3
Indexable
Never
#include<stdio.h> #include<cmath> #include<algorithm> using namespace std; typedef long long ll; int vis[1 << 10][15][15]; double dp[1 << 10][15][15]; int x[15]; int y[15]; int parent[1 << 10][15][15]; int n; int st; double distance(int i, int j) { double diff_x = (double)x[i] - x[j]; double diff_y = (double)y[i] - y[j]; return sqrt(diff_x * diff_x + diff_y * diff_y); } bool checkbit(int bt, int i) { if (bt & (1 << i)) { return false; } return true; } int setbit(int bt, int i) { bt = bt | (1 << i); return bt; } double get_in_line(int bt, int end) { if (bt == (1 << n) - 1)return 0; if (vis[bt][end][st]) return dp[bt][end][st]; double mn = 1e9; int ml =1e9; for (int i = 0;i < n;i++) { if (checkbit(bt, i)) { //printf("%d %d %d\n", bt, i, setbit(bt, i)); double ans = get_in_line(setbit(bt, i), i) + distance(end, i); if (mn > ans) ml = i; mn = min(ans, mn); } } vis[bt][end][st] = 1; parent[bt][end][st] = ml; return dp[bt][end][st] = mn; } void print(int bt, int end) { if (bt == (1 << n) - 1) return; printf("Cable requirement to connect (%d,%d) to (%d,%d) is %.2lf feet.\n", x[end], y[end], x[parent[bt][end][st]], y[parent[bt][st][end]], distance(end, parent[bt][st][end]) + 16); print(setbit(bt, parent[bt][st][end]), parent[bt][st][end]); } int main() { int cnt = 0; while (scanf("%d", &n) and n) { for (int i = 0;i < n;i++) { scanf("%d %d", &x[i], &y[i]); } for (int i = 0;i < 260;i++) { for (int j = 0;j < 10;j++) { for (int k = 0;k < 10;k++) { vis[i][j][k] = 0; } } } double mn = 1e9; int start = 0; for (int i = 0;i < n;i++) { st = i; double ans = get_in_line((1 << st), st); if (mn > ans) start = st; mn = min(ans, mn); } st = start; printf("**********************************************************\n"); printf("Network #%d\n", ++cnt); print((1 << st), st); printf("Number of feet of cable required is %.2lf.\n", mn + (n - 1) * 16.0); } }