首页 > 代码库 > BZOJ1097: [POI2007]旅游景点atr
BZOJ1097: [POI2007]旅游景点atr
1097: [POI2007]旅游景点atr
Time Limit: 30 Sec Memory Limit: 357 MBSubmit: 1006 Solved: 189
[Submit][Status]
Description
FGD想从成都去上海旅游。在旅途中他希望经过一些城市并在那里欣赏风景，品尝风味小吃或者做其他的有趣的事情。经过这些城市的顺序不是完全随意的，比如说FGD不希望在刚吃过一顿大餐之后立刻去下一个城市登山，而是希望去另外什么地方喝下午茶。幸运的是,FGD的旅程不是既定的，他可以在某些旅行方案之间进行选择。由于FGD非常讨厌乘车的颠簸，他希望在满足他的要求的情况下，旅行的距离尽量短，这样他就有足够的精力来欣赏风景或者是泡MM了^_^. 整个城市交通网络包含N个城市以及城市与城市之间的双向道路M条。城市自1至N依次编号，道路亦然。没有从某个城市直接到它自己的道路，两个城市之间最多只有一条道路直接相连，但可以有多条连接两个城市的路径。任意两条道路如果相遇，则相遇点也必然是这N个城市之一，在中途，由于修建了立交桥和下穿隧道，道路是不会相交的。每条道路都有一个固定长度。在中途，FGD想要经过K(K<=N-2)个城市。成都编号为1，上海编号为N,而FGD想要经过的N个城市编号依次为2,3,…,K+1. 举例来说，假设交通网络如下图。FGD想要经过城市2,3,4,5，并且在2停留的时候在3之前，而在4,5停留的时候在3之后。那么最短的旅行方案是1-2-4-3-4-5-8,总长度为19。注意FGD为了从城市2到城市4可以路过城市3,但不在城市3停留。这样就不违反FGD的要求了。并且由于FGD想要走最短的路径，因此这个方案正是FGD需要的。
Input
第一行包含3个整数N(2<=N<=20000),M(1<=M<=200000),K(0<=K<=20),意义如上所述。以下M行，每行包含3个整数X，Y，Z，(1<=X
Output
只包含一行，包含一个整数，表示最短的旅行距离。
Sample Input
8 15 4
1 2 3
1 3 4
1 4 4
1 6 2
1 7 3
2 3 6
2 4 2
2 5 2
3 4 3
3 6 3
3 8 6
4 5 2
4 8 6
5 7 4
5 8 6
3
2 3
3 4
3 5
1 2 3
1 3 4
1 4 4
1 6 2
1 7 3
2 3 6
2 4 2
2 5 2
3 4 3
3 6 3
3 8 6
4 5 2
4 8 6
5 7 4
5 8 6
3
2 3
3 4
3 5
Sample Output
19
HINT
上面对应于题目中给出的例子。
Source
题解：
这题这么卡常数有意思吗？
我觉的一道题目只要思路足够巧妙，数据范围只要让暴力过不了就行了，卧槽，2^20 *20*20怎么看都是要T的节奏。。。
首先k+1次spfa肯定是要做的，然后考虑先到谁后到谁对答案有影响，而k有很小，自然让我们想到了状压DP，
所以用dp[x][y]表示当前已到的节点集合为y，目前处于x点，更新后续状态即可，也可以记忆化，可以去除一些冗余状态，但就是有一些点G=0。。。
卧槽！！！！！！！！！！！！！
这样写T：
1 inline int dfs(int x,int y) 2 { 3 if(dp[x][y]>=0)return dp[x][y]; 4 if(y==(1<<k)-1)return d[x][n-1]; 5 dp[x][y]=inf; 6 for1(i,k) 7 if(!(y&(1<<(i-1)))&&((y&a[i])==a[i])) 8 dp[x][y]=min(dp[x][y],d[x][i]+dfs(i,y|(1<<(i-1)))); 9 return dp[x][y]; 10 }
这样写A：
1 inline int dfs(int x,int y) 2 { 3 if(dp[x][y]>=0)return dp[x][y]; 4 if(y==(1<<k)-1)return d[x][n-1]; 5 dp[x][y]=inf; 6 for1(i,k) 7 if((y&a[i])==a[i]) 8 dp[x][y]=min(dp[x][y],d[x][i]+dfs(i,y|(1<<(i-1)))); 9 return dp[x][y]; 10 }
jry：出题人，咱们天台见。
代码：
我的
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set>10 #include<queue>11 #include<string>12 #define inf 100000000013 #define maxn 5000014 #define maxm 50000015 #define eps 1e-1016 #define ll long long17 #define pa pair<int,int>18 #define for0(i,n) for(int i=0;i<=(n);i++)19 #define for1(i,n) for(int i=1;i<=(n);i++)20 #define for2(i,x,y) for(int i=(x);i<=(y);i++)21 using namespace std;22 inline int read()23 {24 int x=0,f=1;char ch=getchar();25 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}26 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}27 return x*f;28 }29 struct edge{int go,next,w;}e[2*maxm];30 int n,m,k,tot,a[25],q[maxn],d[25][maxn],head[maxn],dp[22][1<<21];31 bool v[maxn];32 inline void ins(int x,int y,int z)33 {34 e[++tot].go=y;e[tot].w=z;e[tot].next=head[x];head[x]=tot;35 }36 inline void insert(int x,int y,int z)37 {38 ins(x,y,z);ins(y,x,z);39 }40 inline void spfa(int s)41 {42 for(int i=0;i<n;++i) d[s][i]=inf;43 memset(v,0,sizeof(v));44 int l=0,r=1,x,y;q[1]=s;d[s][s]=0;45 while(l!=r)46 {47 x=q[++l];if(l==maxn)l=0;v[x]=0;48 for(int i=head[x];i;i=e[i].next)49 if(d[s][x]+e[i].w<d[s][y=e[i].go])50 {51 d[s][y]=d[s][x]+e[i].w;52 if(!v[y]){v[y]=1;q[++r]=y;if(r==maxn)r=0;}53 }54 }55 }56 inline int dfs(int x,int y)57 {58 if(dp[x][y]>=0)return dp[x][y];59 if(y==(1<<k)-1)return d[x][n-1];60 dp[x][y]=inf;61 for1(i,k)62 if((y&a[i])==a[i])63 dp[x][y]=min(dp[x][y],d[x][i]+dfs(i,y|(1<<(i-1))));64 return dp[x][y]; 65 }66 int main()67 {68 freopen("input.txt","r",stdin);69 freopen("output.txt","w",stdout);70 n=read();m=read();k=read();71 int x,y,z;72 for1(i,m)x=read()-1,y=read()-1,z=read(),insert(x,y,z);73 for0(i,k)spfa(i);74 m=read();75 memset(dp,-1,sizeof(dp));76 for1(i,m)x=read()-1,y=read()-1,a[y]|=1<<(x-1);77 printf("%d\n",dfs(0,0));78 return 0;79 }
大吧的
1 #include<cstdio> 2 #include<queue> 3 #include<vector> 4 #include<algorithm> 5 #include<cstring> 6 #include<iostream> 7 using namespace std; 8 #define N 30000 9 #define M 50000010 struct node{11 int w,u;12 bool operator<(const node&rhs)const{13 return w>rhs.w;14 }15 };priority_queue<node>Q;16 int to[M],mm=0,G[N],wei[M],nex[M];17 void addedge(int u,int v,int w)18 {19 nex[mm]=G[u];G[u]=mm;wei[mm]=w;to[mm]=v;mm++;20 }21 int dis[N],n,m,k,depend[30],d[30][30],dp[1<<20][21];22 void shortest(int S)23 {24 for(int i=0;i<=n;i++)dis[i]=~0U>>3;25 dis[S]=0;Q.push((node){0,S});26 while(!Q.empty())27 {28 int u=Q.top().u;Q.pop();29 for(int i=G[u];~i;i=nex[i])30 {31 int v=to[i];32 if(dis[v]>dis[u]+wei[i])33 {34 dis[v]=wei[i]+dis[u];35 Q.push((node){dis[v],v});36 }37 }38 }39 }40 bool check(int state,int kth)41 {42 return (state&depend[kth])==depend[kth];43 }44 int dfs(int state,int now)45 {46 if(dp[state][now]>=0)return dp[state][now];47 if(state==(1<<k)-1)return d[now][k+1];48 dp[state][now]=~0U>>3;49 for(int i=1;i<=k;i++)50 if(check(state,i-1)){51 dp[state][now]=min(dp[state][now],dfs(state|(1<<(i-1)),i)+d[now][i]);52 } 53 return dp[state][now];54 }55 int main(){56 freopen("input.txt","r",stdin);57 freopen("output.txt","w",stdout);58 memset(G,-1,sizeof(G));59 scanf("%d%d%d",&n,&m,&k);60 for(int i=1,a,b,c;i<=m;i++)61 {62 scanf("%d%d%d",&a,&b,&c);63 a--;64 b--;65 addedge(a,b,c);66 addedge(b,a,c);67 }scanf("%d",&m);68 for(int i=1,a,b;i<=m;i++)69 {70 scanf("%d%d",&a,&b);71 a-=2;b-=2;72 depend[b]|=(1<<a);73 }for(int i=0;i<=k;i++)74 {75 shortest(i);76 for(int j=0;j<=k;j++)d[i][j]=dis[j];77 d[i][k+1]=dis[n-1];78 }79 memset(dp,-1,sizeof(dp));80 printf("%d\n",dfs(0,0));81 }
BZOJ1097: [POI2007]旅游景点atr
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。