BZOJ-1097: [POI2007]旅游景点atr

[文章目录]

Description

给你n个点,m条边的无向图,请设计一条路线从1出发,到达n,路上访问了K个节点,并且满足一些形如A B(表示访问B之前一定访问过A)的条件。保证A,B属于K个节点之内。当然,你可以途经B节点(并不访问)到达A节点进行访问,然后到达B节点访问。求路线的最短长度N(2<=N<=20000),M(1<=M<=200000),K(0<=K<=20)

K很小啊。限定也只在K个点之间。
预处理出K个点还有1节点到所有点的最短路,(K次堆优化dij)。之后状压DP,dp[s][i]表示已经访问的状态为s,当前在i节点。由此转移。需要特判k为0的情况。时间复杂度其实状压的复杂度完全少于这个。

#include <vector>
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int dp[1100000][20];
vector<int>v[22];
int n,m,k,ans=0x7fffffff,d[22][21000];
int head[21000],to[401000],nxt[401000],date[401000],cnt;
inline void add(int x,int y,int z)
{to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt; date[cnt]=z;}
struct node
{
    int v,dis;
};
bool operator < (node x,node y){return x.dis>y.dis;}
priority_queue<node>he;
void dijkstra(int x,int dis[])
{
    memset(dis,0x3f,sizeof (int)*(n+10)); dis[x]=0;
    he.push((node){x,0}); int y;
    while(he.size())
    {
        x=he.top().v; y=he.top().dis; he.pop();
        if(y>dis[x]) continue;
        for(int i=head[x];i;i=nxt[i]) if(dis[to[i]]>y+date[i])
        {
            dis[to[i]]=y+date[i];
            he.push((node){to[i],dis[to[i]]});
        }
    }
}
bool check(int s,int x)
{
    x+=2;
    for(int i=0;i!=v[x].size();++i)
        if(!(s&(1<<(v[x][i]-2)))) return false;
    return true;
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    int x,y,z;
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z); add(y,x,z);
    }
    for(int i=1;i<=k+1;++i)
        dijkstra(i,d[i]);
    scanf("%d",&z);
    while(z--)
    {
        scanf("%d%d",&x,&y);
        v[y].push_back(x);
    }
    memset(dp,0x3f,sizeof dp);
    for(int i=2;i<=k+1;++i) if(!v[i].size()) dp[(1<<(i-2))][i-2]=d[1][i];
    for(int s=1;s<(1<<k);++s)
        for(int i=0;i<k;++i) if(s&(1<<i))
            for(int j=0;j<k;++j) if((s&(1<<j))==0&&check(s,j))
                dp[s|(1<<j)][j]=min(dp[s|(1<<j)][j],dp[s][i]+d[i+2][j+2]);
    for(int i=0;i<k;++i) ans=min(ans,dp[(1<<k)-1][i]+d[i+2][n]);
    if(!k) printf("%d",d[1][n]);
    else printf("%d",ans);
    return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注