首页 > 代码库 > [状压dp]HDOJ3001 Travelling

[状压dp]HDOJ3001 Travelling

2024-07-28 07:36:14   223人阅读

题意: 走n个城市, m条路, 起点任意, 每个城市走不超过两次, 求最小花费, 不能走输出-1.

1<=n<=10

分析: 每个城市的拜访次数为0 1 2, 所以三进制状压, 先预处理10位(n最大为10)的三进制数

 

 1 int num[12], vis[60005][12]; 2  3 void init() 4 { 5     num[0]=1; 6     for(int i=1; i<=10; i++) 7         num[i]=num[i-1]*3; 8     memset(vis, -1, sizeof(vis)); 9     for(int i=0; i<=num[10]; i++)10     {11         int x=i;12         for(int j=0; j<=10; j++)13         {14             vis[i][j]=x%3;15             x/=3;16         }17     }18 }

 

  1 #include <cstdio>  2 #include <cstdlib>  3 #include <cstring>  4 #include <climits>  5 #include <cctype>  6 #include <cmath>  7 #include <string>  8 #include <sstream>  9 #include <iostream> 10 #include <algorithm> 11 #include <iomanip> 12 using namespace std; 13 #include <queue> 14 #include <stack> 15 #include <vector> 16 #include <deque> 17 #include <set> 18 #include <map> 19 typedef long long LL; 20 typedef long double LD; 21 #define pi acos(-1.0) 22 #define lson l, m, rt<<1 23 #define rson m+1, r, rt<<1|1 24 typedef pair<int, int> PI; 25 typedef pair<int, PI> PP; 26 #ifdef _WIN32 27 #define LLD "%I64d" 28 #else 29 #define LLD "%lld" 30 #endif 31 //#pragma comment(linker, "/STACK:1024000000,1024000000") 32 //LL quick(LL a, LL b){LL ans=1;while(b){if(b & 1)ans*=a;a=a*a;b>>=1;}return ans;} 33 //inline int read(){char ch=‘ ‘;int ans=0;while(ch<‘0‘ || ch>‘9‘)ch=getchar();while(ch<=‘9‘ && ch>=‘0‘){ans=ans*10+ch-‘0‘;ch=getchar();}return ans;} 34 //inline void print(LL x){printf(LLD, x);puts("");} 35 //inline void read(int &x){char c = getchar();while(c < ‘0‘) c = getchar();x = c - ‘0‘; c = getchar();while(c >= ‘0‘){x = x * 10 + (c - ‘0‘); c = getchar();}} 36  37 #define INF 2139062143 38 int dp[60005][12]; 39 int mp[12][12]; 40 int num[12], vis[60005][12]; 41 void init() 42 { 43     num[0]=1; 44     for(int i=1; i<=10; i++) 45         num[i]=num[i-1]*3; 46     memset(vis, -1, sizeof(vis)); 47     for(int i=0; i<=num[10]; i++) 48     { 49         int x=i; 50         for(int j=0; j<=10; j++) 51         { 52             vis[i][j]=x%3; 53             x/=3; 54         } 55     } 56 } 57 int main() 58 { 59 #ifndef ONLINE_JUDGE 60     freopen("in.txt", "r", stdin); 61     freopen("out.txt", "w", stdout); 62 #endif 63     init(); 64     int n, m; 65     while(~scanf("%d%d", &n, &m)) 66     { 67         memset(dp, 127, sizeof(dp)); 68         memset(mp, 127, sizeof(mp)); 69         for(int i=0; i<n; i++) 70             dp[num[i]][i]=0; 71         while(m--) 72         { 73             int a, b, c; 74             scanf("%d%d%d", &a, &b, &c); 75             mp[a-1][b-1]=mp[b-1][a-1]=min(mp[a-1][b-1], c); 76         } 77         int ans=INF; 78         for(int i=0;i<num[n];i++) // n个城市走过次数的状态i 79         { 80             bool flag=0; 81             for(int j=0;j<n;j++)   // 当前在j 82             { 83                 if(!vis[i][j]) 84                     flag=1; 85                 if(dp[i][j]==INF) 86                     continue; 87                 for(int k=0;k<n;k++)   // 走去 k 88                     if(j!=k) 89                     { 90                         if(vis[i][k]>=2) 91                             continue; 92                         if(mp[j][k]==INF) 93                             continue; 94                         dp[i+num[k]][k]=min(dp[i+num[k]][k], dp[i][j]+mp[j][k]); 95                     } 96             } 97             if(!flag) 98                 for(int j=0;j<n;j++) 99                     ans=min(ans, dp[i][j]);100         }101         if(ans==INF)102             printf("-1\n");103         else104             printf("%d\n", ans);105     }106     return 0;107 }
HDOJ3001

 

[状压dp]HDOJ3001 Travelling


联系
我们