「CODEVS2800」送外卖
题目描述 Description
有一个送外卖的，他手上有n份订单，他要把n份东西，分别送达n个不同的客户的手上。n个不同的客户分别在1~n个编号的城市中。送外卖的从0号城市出发，然后n个城市都要走一次（一个城市可以走多次），最后还要回到0点（他的单位），请问最短时间是多少。现在已知任意两个城市的直接通路的时间。
输入描述 Input Description
第一行一个正整数n （1<=n<=15）
接下来是一个（n+1）*(n+1)的矩阵，矩阵中的数均为不超过10000的正整数。矩阵的i行j列表示第i-1号城市和j-1号城市之间直接通路的时间。当然城市a到城市b的直接通路时间和城市b到城市a的直接通路时间不一定相同，也就是说道路都是单向的。
输出描述 Output Description
一个正整数表示最少花费的时间
样例输入 Sample Input
样例输出 Sample Output
8
数据范围及提示 Data Size & Hint
1<=n<=15
代码
深搜20分。。。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int n,ed,cnt; int mp[16],f[16][1<<16],head[16]; struct data{int to,next,v;}e[500]; void insert(int u,int v,int w) { cnt++; e[cnt].to=v; e[cnt].next=head[u]; e[cnt].v=w; head[u]=cnt; } int hash(int a[16]) { int s=0; for(int i=0;i<=n;i++) s+=a[i]<<i; return s; } void search(int k,int a[16]) { int i=head[k],now=hash(a); while(i) { bool temp=a[e[i].to]; a[e[i].to]=1; int to=hash(a); if(f[k][now]+e[i].v<f[e[i].to][to]) { f[e[i].to][to]=f[k][now]+e[i].v; search(e[i].to,a); } a[e[i].to]=temp; i=e[i].next; } } int main() { scanf("%d",&n); memset(f,127/3,sizeof(f)); ed=(1<<(n+1))-1;f[0][0]=0; for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) { int x; scanf("%d",&x); if(i!=j)insert(i,j,x); } search(0,mp); printf("%d\n",f[0][ed]); return 0; } |
状态压缩DP AC
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int n,ed; int mp[16][16],f[16][1<<16]; int main() { memset(f,127/3,sizeof(f)); scanf("%d",&n);ed=(1<<(n+1))-1; for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) scanf("%d",&mp[i][j]); for(int k=0;k<=n;k++) for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) mp[i][j]=min(mp[i][j],mp[i][k]+mp[k][j]); f[0][0]=0; for(int i=0;i<=ed;i++) for(int now=0;now<=n;now++) for(int from=0;from<=n;from++) { if((i|(1<<now))!=i)continue; f[now][i]=min(f[now][i],f[from][i-(1<<now)]+mp[from][now]); f[now][i]=min(f[now][i],f[from][i]+mp[from][now]); } printf("%d\n",f[0][ed]); return 0; } |
Subscribe
计数器 9301783
OI 课件=>
OI 课件=>