A less slow pressure???

There's no purple question at all. The data is still so water.

I'm not going to tell you I'm hack ed.

Look at the data size, n < 12, decisive pressure.

Then the starting point needs to be enumerated, and the dp state is set:

f[i][j]= takes I as the starting point to minimize the cost of J status.

Where j is a binary number (denoted by decimal system) where 1 and 0 at the i-th place denote whether or not the i-th point has been reached (1 denotes that it has arrived and 0 denotes that it has not yet arrived).

(Because m is very large and n is very small, there will be multiple edges, so the adjacency matrix (e[u][v]) is used.)

The state transition equation can be listed as follows:

f[i][j]=min{f[i][k]+diss[i][k][u]*e[u][v]}

(j&(1<<(u-1))!=0,j&(1<<(v-1))!=0,i!=v,k=j^(1<<(v-1)),e[u][v]!=1e9)

(e[u][v]!=1e9 means that there is a boundary between u and v)

What do you mean? That is to say, we can find another state (k) which is only a little less than the current state (J). (obviously, it can not be a starting point), then expand from K to j, and take the least cost in all K.

But there's another question. What's the cost of this side?

According to the title description, the length of the edge is multiplied by the number of points (dis[i][j][u]) that uu passes through.

The question arises again. What about dis[i][j][u]?

Every time the state is changed, it can be transferred by the way.

The code is as follows:

#include<cstdio>

inline int read(){
	int r=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9')r=(r<<1)+(r<<3)+c-'0',c=getchar();
	return r*f;
}

int n,ans=1e9,m,f[15][5005],e[15][15],dis[15][5005][15];

inline int min(int a,int b){
	return a<b?a:b;
}

int main(){
	freopen("treasure.in","r",stdin);
	freopen("treasure.out","w",stdout);
	n=read(),m=read();
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			e[i][j]=1e9;
	for(int i=1;i<=m;i++){
		int u=read(),v=read();
		if(u-v)e[u][v]=e[v][u]=min(e[u][v],read());
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<1<<n;j++)
			f[i][j]=1e9;
	for(int i=1;i<=n;i++){
		f[i][1<<(i-1)]=0;
		dis[i][1<<(i-1)][i]=1;
		for(int j=(1<<(i-1))+1;j<1<<n;j++){
			if(!(j&(1<<(i-1))))continue;
			int x=j,u=1;
			while(x){
				if(x&1){
					for(int v=1;v<=n;v++){
						if(i==v||e[u][v]==1e9||!(j&(1<<(v-1))))continue;
						int k=j^(1<<(v-1));
						if(f[i][j]>f[i][k]+dis[i][k][u]*e[u][v]){
							f[i][j]=f[i][k]+dis[i][k][u]*e[u][v];
							for(int y=1;y<=n;y++)dis[i][j][y]=dis[i][k][y];
							dis[i][j][v]=dis[i][k][u]+1;
						}
					}
				}
				u++;
				x>>=1;
			}
		}
		ans=min(ans,f[i][(1<<n)-1]);
	}
	printf("%d",ans);
	return 0;
}