本文共 1607 字，大约阅读时间需要 5 分钟。
题意：小明想去n个城市游玩，m条路，从一个城市到达另一个城市有一定的花费，每个城市最多可以走两次
求最少的花费
题解：因为每个城市最多走两次，可以用三进制，保存状态，感觉同二进制没区别，不过想了半天没想通，
看了一下题解，懂了。
#include#include #include #include using namespace std;#define M 60000#define INF 0x3f3f3f3fint s[12];int t[M][12],map[12][12];int n,m;int dp[M][12];void init(){ s[0] = 1; for(int i = 1;i <= 11;i++){ s[i] = s[i-1] * 3 ; } for(int i = 0;i < 59049;i++){ int tmp = i; for(int j = 0;j < 10;j++){ t[i][j] = tmp % 3; tmp /= 3; } }}int main(){ init(); int u,v,w; while(cin >> n >> m){ memset(map,INF,sizeof(map)); for(int i = 0;i < m;i++){ cin >> u >> v >> w ; u -- ; v --; map[u][v] = map[v][u] = min(map[u][v],w); } memset(dp,INF,sizeof(dp)); for(int i = 0;i < n;i++) dp[s[i]][i] = 0; //初始化第i个状态只有1个城市花费为0 int ans = INF; for(int i = 0;i < s[n];i++){ bool flag = true ;//如果城市都被走过 for(int j = 0;j < n;j++){ if(!t[i][j]) flag = false; if(dp[i][j] != INF){ for(int k = 0;k < n;k++){ if(k == j || t[i][k] == 2 || map[j][k] == INF) continue; dp[i+s[k]][k] = min(dp[i+s[k]][k],dp[i][j] + map[j][k]); } } } if(flag) { for(int l = 0;l < n;l++){ ans = min(ans,dp[i][l]); } } } if(ans == INF) cout << "-1" << endl; else cout << ans << endl; }}
转载地址：http://qdsgi.baihongyu.com/