luogu3959 宝藏

状压搜索轻轻松松就过了……考场上代码太丑了T了几个点

#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

int n, m, uu, vv, ww, w[15][15], dis[15], dp[100005], ans;

const int oo=0x3f3f3f3f;

void dfs(int x){

	for(int i=1; i<=n; i++)

		if(x&(1<<(i-1)))

			for(int j=1; j<=n; j++)

				if(!(x&(1<<(j-1))) && w[i][j]<oo)

					if(dp[x|(1<<(j-1))]>dp[x]+dis[i]*w[i][j]){

						int t=dis[j];

						dis[j] = dis[i] + 1;

						dp[x|(1<<(j-1))] = dp[x] + dis[i] * w[i][j];

						dfs(x|(1<<(j-1)));

						dis[j] = t;

					}

}

int main(){

	cin>>n>>m;

	ans = oo;

	memset(w, 0x3f, sizeof(w));

	for(int i=1; i<=m; i++){

		scanf("%d %d %d", &uu, &vv, &ww);

		w[uu][vv] = w[vv][uu] = min(w[vv][uu], ww);

	}

	for(int i=1; i<=n; i++){

		memset(dis, 0x3f, sizeof(dis));

		memset(dp, 0x3f, sizeof(dp));

		dp[1<<(i-1)] = 0;

		dis[i] = 1;

		dfs(1<<(i-1));

		ans = min(ans, dp[(1<<n)-1]);

	}

	cout<<ans;

	return 0;

}

巴特西

luogu3959 宝藏

最新文章

热门文章