詳見:https://www.luogu.com.cn/problem/P1433

• 有可以簡便記錄存儲勾股定理的方式,但是我要簡便,就是直接傳結(jié)構(gòu)體的點,就用不了這個,或許可以用哈希,但是會搞得更麻煩

• 其實感覺更多的因素是懶~~~

就不寫基礎(chǔ)原理了,直接看注釋吧

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

int all, n;
double ans = 200000000;

struct point {
	double x, y;
} a[100];

double dp[1 << 15][20] = {};

int lowbit(int x) {
	return x & (-x);
}

// 快速log2 很巧妙的思路 
int log2_fast(int n) {  
    int result = 0;  
    if(n&0xffff0000) { result += 16; n >>= 16; }  
    if(n&0x0000ff00) { result += 8; n >>= 8; }  
    if(n&0x000000f0) { result += 4; n >>= 4; }  
    if(n&0x0000000c) { result += 2; n >>= 2; }  
    if(n&0x00000002) { result += 1; n >>= 1; }  
    return result; 
}

double gougu(point x, point y) {
	double xc, yc;
	xc = abs(x.x - y.x);
	yc = abs(x.y - y.y);
	return sqrt(xc*xc+yc*yc);
}

// 用引用節(jié)省內(nèi)存,假設(shè)遞歸次數(shù)較多這個是重要的!!! 
void dfs(double di, int state, point& be) {
	// 剪枝優(yōu)化, 根據(jù)已走的路程判斷當(dāng)前分支是否可以做得更好
	if(di >= ans) {
		return;
	}
	// 深搜結(jié)束 
	if(state == all) {
		// 選擇最優(yōu) 
		ans = min(di, ans);
		return;
	}
	// 解析狀壓,轉(zhuǎn)換為二進制其實使用 int vis = all - state; 效果也是一摸一樣的 
	int vis = all&(~state);
	for(int i=vis; i; i -= lowbit(i)) {
		int x = lowbit(i);
		// 轉(zhuǎn)換為數(shù)組下標(biāo) 
		int j = log2_fast(x);
		// 求出給下一個深搜的參數(shù) 
		int nextState = state+x;
		double nextdi = di+gougu(be, a[j]);
		// 剪枝,很簡單的道理,這條路走了,就不走了
		// 記錄成double的原因是就算當(dāng)前坐在的節(jié)點和狀態(tài)相同,走的距離也可以不相同,所以需要更多的信息作比較  
		if(dp[nextState][j]!=0 && dp[nextState][j]<=nextdi) {
			continue;
		}
		// 記錄 
		dp[nextState][j] = nextdi;
		// 接著深搜 
		dfs(nextdi, nextState, a[j]);
	}
}

int main() {
	// 初始化 
	cin >> n;
	all = (1<<n)-1;
	for(int i = 0; i<n; i++) {
		cin >> a[i].x >> a[i].y;
	}
	point t;
	t.x = t.y = 0; 
	// 深搜的參數(shù)有三個,分別為距離,狀壓后的是否使用和當(dāng)前點
	dfs(0, 0, t);
	printf("%.2f", ans);
	return 0;
}

/**
 * 本程序使用了map來,記憶化勾股定理的數(shù),map很慢,會超時,實測不使用map來存儲也可以過 
 * 非要用map的話就吸氧罷(O2),吸氧后的和不吸氧的普通的差不多耗時
 **/
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>

using namespace std;

int all, n;
double ans = 200000000;

struct point {
	double x, y;
} a[100];

map<pair<double, double>, double> dis;

double dp[1 << 15][20] = {};

int lowbit(int x) {
	return x & (-x);
}

// 快速log2 很巧妙的思路 
int log2_fast(int n) {  
    int result = 0;  
    if(n&0xffff0000) { result += 16; n >>= 16; }  
    if(n&0x0000ff00) { result += 8; n >>= 8; }  
    if(n&0x000000f0) { result += 4; n >>= 4; }  
    if(n&0x0000000c) { result += 2; n >>= 2; }  
    if(n&0x00000002) { result += 1; n >>= 1; }  
    return result; 
}

double gougu(point x, point y) {
	// 算差,利用差來記憶數(shù)據(jù) 
	double xc, yc;
	xc = abs(x.x - y.x);
	yc = abs(x.y - y.y);
	if(xc > yc) {
		swap(xc, yc);
	}
	pair<double, double> t(xc, yc);
	if(dis[t] != 0) {
		return dis[t];
	}
	return dis[t] = sqrt(xc*xc+yc*yc);
}

// 用引用節(jié)省內(nèi)存,假設(shè)遞歸次數(shù)較多這個是重要的!!! 
void dfs(double di, int state, point& be) {
	// 剪枝優(yōu)化, 根據(jù)已走的路程判斷當(dāng)前分支是否可以做得更好
	if(di >= ans) {
		return;
	}
	// 深搜結(jié)束 
	if(state == all) {
		// 選擇最優(yōu) 
		ans = min(di, ans);
		return;
	}
	// 解析狀壓,轉(zhuǎn)換為二進制其實使用 int vis = all - state; 效果也是一摸一樣的 
	int vis = all&(~state);
	for(int i=vis; i; i -= lowbit(i)) {
		int x = lowbit(i);
		// 轉(zhuǎn)換為數(shù)組下標(biāo) 
		int j = log2_fast(x);
		// 求出給下一個深搜的參數(shù) 
		int nextState = state+x;
		double nextdi = di+gougu(be, a[j]);
		// 剪枝,很簡單的道理,這條路走了,就不走了
		// 記錄成double的原因是就算當(dāng)前坐在的節(jié)點和狀態(tài)相同,走的距離也可以不相同,所以需要更多的信息作比較  
		if(dp[nextState][j]!=0 && dp[nextState][j]<=nextdi) {
			continue;
		}
		// 記錄 
		dp[nextState][j] = nextdi;
		// 接著深搜 
		dfs(nextdi, nextState, a[j]);
	}
}

int main() {
	// 初始化 
	dis.clear();
	cin >> n;
	all = (1<<n)-1;
	for(int i = 0; i<n; i++) {
		cin >> a[i].x >> a[i].y;
	}
	point t;
	t.x = t.y = 0; 
	// 深搜的參數(shù)有三個,分別為距離,狀壓后的是否使用和當(dāng)前點
	dfs(0, 0, t);
	printf("%.2f", ans);
	return 0;
}

寫這篇題解的時候運氣太背啦!!!

先是luogu爆網(wǎng)關(guān),然后博客園爆網(wǎng)關(guān)
感覺最近互聯(lián)網(wǎng)不太平啊