首页 > 代码库 > 「Poetize9」礼物运送
「Poetize9」礼物运送
3055: 礼物运送
Time Limit: 3 Sec Memory Limit: 128 MBSubmit: 18 Solved: 12
[Submit][Status]
Description
机器人刚刚探查归来，探险队员们突然发现自己的脚下出现了一朵朵白云，把他们托向了空中。一阵飘飘然的感觉过后，队员们发现自己被传送到了一座空中花园。
“远道而来的客人，我们是守护Nescafe之塔的精灵。如果你们想拜访护法和圣主的话，就要由我们引路。因此，你们是不是该给我们一点礼物呢T_T？”
队员们往远处一看，发现花园中有N个木箱，M条柔软的羊毛小路，每条小路的两个端点都是木箱，并且通过它需要ti的时间。队员们需要往每个木箱中放一份礼物，不过由于精灵们不想让花园被过多地踩踏，因此运送礼物的任务最多只能由两位探险队员完成。
两位探险队员同时从1号木箱出发，可以在任意木箱处结束运送。运送完毕时，每只木箱应该被两位队员中至少一人访问过。运送任务所用的时间是两人中较慢的那个人结束运送任务的时间。请问这个时间最快是多少呢？
Input
第一行两个正整数N、M。
接下来M行每行三个整数xi、yi、ti，表示xi和yi之间有一条用时为ti的小路，小路是双向的。
Output
输出所需的最短时间。
Sample Input
6 6
1 2 10
2 3 10
3 4 5
4 5 10
5 6 20
2 5 10
1 2 10
2 3 10
3 4 5
4 5 10
5 6 20
2 5 10
Sample Output
40
HINT
Source
Poetize10
题解;
我看到这题思路还是比较直的。
首先把f[i][j]求出来，表示当前走过的集合为j，现在在i点的最短路。
令g[j]=min(f[i][j]) 1<=i<=n
再令 d[j]=min(d[k]) j&k=j
则 ans=min(max(d[j],d[!j])) 0<=j< 1<<n
d[j]的求法可以记忆化搜索。
忽然发现我居然不会写记忆化TAT
代码：
1 #include<cstdio> 2 3 #include<cstdlib> 4 5 #include<cmath> 6 7 #include<cstring> 8 9 #include<algorithm> 10 11 #include<iostream> 12 13 #include<vector> 14 15 #include<map> 16 17 #include<set> 18 19 #include<queue> 20 21 #include<string> 22 23 #define inf 1000000000 24 25 #define maxn 19*(1<<19) 26 27 #define maxm 500+100 28 29 #define eps 1e-10 30 31 #define ll long long 32 33 #define for0(i,n) for(int i=0;i<=(n);i++) 34 35 #define for1(i,n) for(int i=1;i<=(n);i++) 36 37 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 38 39 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 40 41 #define mod 1000000007 42 43 using namespace std; 44 45 inline int read() 46 47 { 48 49 int x=0,f=1;char ch=getchar(); 50 51 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 52 53 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 54 55 return x*f; 56 57 } 58 int d[19][1<<19],g[20][20],n,m; 59 struct rec{int x,y;}q[maxn+1]; 60 bool v[19][1<<19],vv[1<<19]; 61 inline void spfa() 62 { 63 for0(i,n)for0(j,(1<<n)-1)d[i][j]=inf; 64 d[1][1]=0; 65 int l=0,r=1;q[1].x=1,q[1].y=1; 66 while(l<r) 67 { 68 int x=q[++l].x,y=q[l].y;v[x][y]=0;if(l==maxn)l=0; 69 for1(i,n) 70 if(i!=x&&g[x][i]) 71 { 72 int yy=y|(1<<(i-1)); 73 if(d[x][y]+g[x][i]<d[i][yy]) 74 { 75 d[i][yy]=d[x][y]+g[x][i]; 76 if(!v[i][yy]) 77 { 78 v[i][yy]=1; 79 q[++r].x=i; 80 q[r].y=yy; 81 if(r==maxn)r=0; 82 } 83 } 84 } 85 } 86 //for1(i,n)for0(j,(1<<n)-1)cout<<i<<‘ ‘<<j<<‘ ‘<<d[i][j]<<endl; 87 } 88 inline void dfs(int x) 89 { 90 if(vv[x])return; 91 vv[x]=1; 92 for1(i,n)d[0][x]=min(d[0][x],d[i][x]); 93 for1(i,n) 94 if(!(x&(1<<(i-1)))) 95 { 96 int y=x|(1<<(i-1)); 97 dfs(y);; 98 if(d[0][x]>d[0][y])d[0][x]=d[0][y]; 99 } 100 }101 102 int main()103 104 {105 106 //freopen("input.txt","r",stdin);107 108 //freopen("output.txt","w",stdout);109 110 n=read();m=read();111 for1(i,m){int x=read(),y=read(),z=read();g[x][y]=z;g[y][x]=z;}112 spfa();113 dfs(0);114 int ans=inf;115 for0(i,(1<<n)-1)ans=min(ans,max(d[0][i],d[0][(1<<n)-1-i]));116 printf("%d\n",ans);117 118 return 0;119 120 }
「Poetize9」礼物运送
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。