评测记录

dfs 记忆化 + 状压，已经去重边了，不是很懂为什么会 WA。

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
template<int N,int M,class T=int> struct graph{
	int cnt,head[N+10],nxt[M*2+10];
	struct edge{
		int u,v;T w;
		edge(int u=0,int v=0,T w=T()):u(u),v(v),w(w){}
	} e[M*2+10];
	edge operator[](int i){return e[i];}
	graph():cnt(0){memset(head,0,sizeof head);}
	void add(int u,int v,T w=T()){e[++cnt]=edge(u,v,w),nxt[cnt]=head[u],head[u]=cnt;}
	void link(int u,int v,T w=T()){add(u,v,w),add(v,u,w);}
};
int n,m,dis[20];
//graph<20,1010> g;
int g[20][20];
int bfs(int s,int t=1){
	queue<int> q;
	memset(dis,0x3f,sizeof dis);
	dis[s]=1,q.push(s);
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int v=1;v<=n;v++){
			if(g[u][v]==g[0][0]) continue;
			int w=1;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				q.push(v);
			}
		}
	}
	return dis[t];
}
//bool vis[20];
int f[1<<20];
int dfs(int cnt,int vis){
	if(!cnt) return 0;
	if(f[vis]) return f[vis];
	int ans=1e9;
	for(int u=1;u<=n;u++){
//		if(vis[u]){
		if(vis&(1<<u)){
			for(int v=1;v<=n;v++){
//				if(!vis[v]&&g[u][v]!=g[0][0]){
				if(!(vis&(1<<v))&&g[u][v]!=g[0][0]){
//					vis[v]=1;
					ans=min(ans,dfs(cnt-1,vis|(1<<v))+g[u][v]*dis[u]);
//					vis[v]=0;
				}
			}
		}
	}
	return f[vis]=ans;
}
int check(int s){
	bfs(s);
	memset(f,0,sizeof f);
//	vis[s]=1;
	return dfs(n-1,1<<s);
}
int main(){
	scanf("%d%d",&n,&m);
	memset(g,0x3f,sizeof g);
	for(int i=1;i<=n;i++) g[i][i]=0;
	for(int i=1;i<=m;i++){int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		g[u][v]=min(g[u][v],w);
		g[v][u]=min(g[v][u],w);
	}
	int ans=1e9;
	for(int i=1;i<=n;i++) ans=min(ans,check(i));
	printf("%d\n",ans);
	return 0;
}