tjut 3001

#include<stdio.h> #include<string.h> #define INF 0x7fffffff int n, m, minn; int load[12][12]; int bit[11] = {1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049}; int dp[60000][12]; int num[60000][12];//记录每个数的三进制数 int min(int a, int b) { return a < b ? a : b; } void make_trb() { int i, j, b; for(i = 0; i < bit[10]; i++) { b = i; for(j = 0; j < 10; j++) { num[i][j] = b % 3; b /= 3; } } }//计算所有数的三进制表示 void init() { int i, j; memset(load, -1, sizeof(load)); for(i = 0; i < bit[n]; i++) { for(j = 0; j < n; j++) dp[i][j] = INF; } for(j = 0; j < n; j++) dp[ bit[j] ][j] = 0;//对每个点定为初始点0 } int comp_dp() { int i, j, flag, l, next; minn = INF; for(i = 0; i < bit[n]; i++) { flag = 1;//表示所有位都为1，即所有的城市都遍历过1次以上 for(j = 0; j < n; j++)//跟二进制一样遍历所有终点 { if(num[i][j] == 0) flag = 0; if(dp[i][j] == INF) continue; for(l = 0; l < n; l++) { if(j == l || num[i][l] >= 2 || load[l][j] == -1) continue; next = i + bit[l]; dp[next][l] = min(dp[next][l], dp[i][j] + load[j][l]); }//由于跟访问路径有关，所以for l 0 -> n，用来历遍所有起点 } if(flag == 1) { for(j = 0; j < n; j++) minn = min(minn , dp[i][j]); } } return 0; } int main() { int i, j, a, b, c; make_trb();//计算所有数的三进制表示 while(scanf("%d%d", &n, &m) != EOF) { init(); for(i = 0; i < m; i++) { scanf("%d%d%d", &a, &b, &c); if(load[a-1][b-1] == -1) load[b-1][a-1] = load[a-1][b-1] = c; else load[b-1][a-1] = load[a-1][b-1] = min(load[a-1][b-1], c); } comp_dp(); if(minn == INF) minn = -1; printf("%d\n", minn); } return 0; }