首页 > 代码库 > BZOJ 1097: [POI2007]旅游景点atr [DP 状压 最短路]
BZOJ 1097: [POI2007]旅游景点atr [DP 状压 最短路]
传送门
题意：
一个无向图，从$1$到$n$，要求必须经过$2,3,...,k+1$，给出一些限制关系，要求在经过$v \le k+1$之前必须经过$u \le k+1$
求最短路
预处理出$1...k+1$到其他点的最短路
然后$f[i][s]$表示当前在$i$已经经过的点的集合为$s$的最短路
只考虑$1,2,...,k+1$就行了，
注意$1$也要考虑，一个点可能经过多次
然后实测dij比spfa快....我想试$pb\_ds$来着结果发现我的电脑上没有ext/pb_ds/priority_queue.hpp
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>using namespace std;typedef long long ll;const int N=2e4+5,M=2e5+5,K=22,S=(1<<20)+5,INF=1e9;inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return x*f;}int n,m,k,u,v,w;int need[K],f[K][S];int d[K][N];struct Edge{ int v,w,ne;}e[M<<1];int cnt,h[N];inline void ins(int u,int v,int w){ cnt++; e[cnt].v=v;e[cnt].w=w;e[cnt].ne=h[u];h[u]=cnt; cnt++; e[cnt].v=u;e[cnt].w=w;e[cnt].ne=h[v];h[v]=cnt;}int q[N],head,tail,inq[N];inline void lop(int &x){if(x==N) x=1;else if(x==0) x=N-1;}void spfa(int s,int *d){ head=tail=1; d[s]=0;inq[s]=1; q[tail++]=s; while(head!=tail){ int u=q[head++];inq[u]=0;lop(head); for(int i=h[u];i;i=e[i].ne){ int v=e[i].v; if(d[v]>d[u]+e[i].w){ d[v]=d[u]+e[i].w; if(!inq[v]){ inq[v]=1; if(d[v]<d[q[head]]) head--,lop(head),q[head]=v; else q[tail++]=v,lop(tail); } } } }}int main(){ freopen("in","r",stdin); n=read();m=read();k=read(); for(int i=1;i<=m;i++) u=read(),v=read(),w=read(),ins(u,v,w); memset(d,127,sizeof(d)); for(int i=1;i<=k+1;i++) spfa(i,d[i]); int c=read(); while(c--) u=read()-2,v=read(),need[v]|=(1<<u); memset(f,-1,sizeof(f)); int All=1<<k; f[1][0]=0; for(int s=0;s<All;s++) for(int i=1;i<=k+1;i++) if(f[i][s]!=-1){ for(int j=2;j<=k+1;j++) if(j!=i && (need[j]&s)==need[j] ){ int t=s|(1<<(j-2)); if(f[j][t]>f[i][s]+d[i][j] || f[j][t]==-1) f[j][t]=f[i][s]+d[i][j]; } } int ans=INF; for(int i=1;i<=k+1;i++) if(f[i][All-1]!=-1) ans=min(ans,f[i][All-1]+d[i][n]); printf("%d",ans);}
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <queue>using namespace std;#define pii pair<int,int>#define MP make_pair#define fir first#define sec secondtypedef long long ll;const int N=2e4+5,M=2e5+5,K=22,S=(1<<20)+5,INF=1e9;inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return x*f;}int n,m,k,u,v,w;int need[K],f[K][S];int d[K][N];struct Edge{ int v,w,ne;}e[M<<1];int cnt,h[N];inline void ins(int u,int v,int w){ cnt++; e[cnt].v=v;e[cnt].w=w;e[cnt].ne=h[u];h[u]=cnt; cnt++; e[cnt].v=u;e[cnt].w=w;e[cnt].ne=h[v];h[v]=cnt;}priority_queue<pii,vector<pii>,greater<pii> > q;bool done[N];void dij(int s,int *d){ for(int i=1;i<=n;i++) d[i]=INF,done[i]=0; d[s]=0; q.push(MP(d[s],s)); while(!q.empty()){ int u=q.top().sec;q.pop(); if(done[u]) continue;done[u]=1; for(int i=h[u];i;i=e[i].ne) if(d[e[i].v]>d[u]+e[i].w){ d[e[i].v]=d[u]+e[i].w; q.push(MP(d[e[i].v],e[i].v)); } }}int main(){ freopen("in","r",stdin); n=read();m=read();k=read(); for(int i=1;i<=m;i++) u=read(),v=read(),w=read(),ins(u,v,w); memset(d,127,sizeof(d)); for(int i=1;i<=k+1;i++) dij(i,d[i]); int c=read(); while(c--) u=read()-2,v=read(),need[v]|=(1<<u); memset(f,-1,sizeof(f)); int All=1<<k; f[1][0]=0; for(int s=0;s<All;s++) for(int i=1;i<=k+1;i++) if(f[i][s]!=-1){ for(int j=2;j<=k+1;j++) if(j!=i && (need[j]&s)==need[j] ){ int t=s|(1<<(j-2)); if(f[j][t]>f[i][s]+d[i][j] || f[j][t]==-1) f[j][t]=f[i][s]+d[i][j]; } } int ans=INF; for(int i=1;i<=k+1;i++) if(f[i][All-1]!=-1) ans=min(ans,f[i][All-1]+d[i][n]); printf("%d",ans);}
BZOJ 1097: [POI2007]旅游景点atr [DP 状压 最短路]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。