3055: 礼物运送
Time Limit: 3 Sec Memory Limit: 128 MB
Submit: 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
题解;
我看到这题思路还是比较直的。
首先把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
代码：
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<string>
#define inf 1000000000
#define maxn 19*(1<<19)
#define maxm 500+100
#define eps 1e-10
#define ll long long
#define for0(i,n) for(int i=0;i<=(n);i++)
#define for1(i,n) for(int i=1;i<=(n);i++)
#define for2(i,x,y) for(int i=(x);i<=(y);i++)
#define for3(i,x,y) for(int i=(x);i>=(y);i--)
#define mod 1000000007
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=*x+ch-'';ch=getchar();}
return x*f;
}
int d[][<<],g[][],n,m;
struct rec{int x,y;}q[maxn+];
bool v[][<<],vv[<<];
inline void spfa()
{
for0(i,n)for0(j,(<<n)-)d[i][j]=inf;
d[][]=;
int l=,r=;q[].x=,q[].y=;
while(l<r)
{
int x=q[++l].x,y=q[l].y;v[x][y]=;if(l==maxn)l=;
for1(i,n)
if(i!=x&&g[x][i])
{
int yy=y|(<<(i-));
if(d[x][y]+g[x][i]<d[i][yy])
{
d[i][yy]=d[x][y]+g[x][i];
if(!v[i][yy])
{
v[i][yy]=;
q[++r].x=i;
q[r].y=yy;
if(r==maxn)r=;
}
}
}
}
//for1(i,n)for0(j,(1<<n)-1)cout<<i<<' '<<j<<' '<<d[i][j]<<endl;
}
inline void dfs(int x)
{
if(vv[x])return;
vv[x]=;
for1(i,n)d[][x]=min(d[][x],d[i][x]);
for1(i,n)
if(!(x&(<<(i-))))
{
int y=x|(<<(i-));
dfs(y);;
if(d[][x]>d[][y])d[][x]=d[][y];
}
}
int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
n=read();m=read();
for1(i,m){int x=read(),y=read(),z=read();g[x][y]=z;g[y][x]=z;}
spfa();
dfs();
int ans=inf;
for0(i,(<<n)-)ans=min(ans,max(d[][i],d[][(<<n)--i]));
printf("%d\n",ans);
return ;
}