题意：有 n 个city，可以选择任一城市作为起点，每个城市不能访问超过2次，
城市之间有权值，问访问全部n个城市需要的最小权值。
思路：因为每个城市可以访问最多两次，所以用三进制表示访问的状态。
详细见代码注释！！！！
#include #include #include #include #include #include #include #include #include #include #include using namespace std; #define INF 1e8 #define inf 0x3f3f3f3f #define eps 1e-8 #define LL long long #define N 100001 #define mol 100000000 int dp[60000][15];//dp[i][j] 表示在状态 i 的情况访问到 j 的最小值 int g[15][15]; int n,m; int st[60000][11];//dp[i][j] i 状态的第 j 个城市可以访问几次 int bit[12];//初始所有可能状态 int main() { bit[0]=0;bit[1]=1; for(int i=2;i<=11;i++) bit[i]=3*bit[i-1]; for(int i=0;i<59050;i++) { int t=i; for(int j=1;j<=10&&t;j++) { st[i][j]=t%3; t/=3; } } while(~scanf("%d%d",&n,&m)) { int u,v,c; memset(dp,0x3f,sizeof(dp)); memset(g,0x3f,sizeof(g)); for(int i=0;i<=n;i++) dp[bit[i]][i]=0;//初始起点 为0 while(m--) { scanf("%d%d%d",&u,&v,&c); if(c