bzoj [POI2007]旅游景点atr 状态压缩+Dij

时间：2021-04-12 21:31:41

[POI2007]旅游景点atr

Time Limit: 30 Sec  Memory Limit: 357 MB
Submit: 2258  Solved: 595
[Submit][Status][Discuss]

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,总长度为1
9。注意FGD为了从城市2到城市4可以路过城市3,但不在城市3停留。这样就不违反FGD的要求了。并且由于FGD想要
走最短的路径，因此这个方案正是FGD需要的。

Input

　　第一行包含3个整数N(2<=N<=20000),M(1<=M<=200000),K(0<=K<=20),意义如上所述。

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

Sample Output

19

HINT

bzoj [POI2007]旅游景点atr 状态压缩+Dij 上面对应于题目中给出的例子。

Source

题解：k十分的小然后处理出两两之间的最短路，然后状态压缩dp一下

 #include<iostream>

 #include<cstdio>

 #include<cstdlib>

 #include<algorithm>

 #include<cmath>

 #include<cstring>

 #include<set>

 #include<queue>

 #define pa pair<int,int>

 #define inf 1000000000

 #define ll long long

 using namespace std;

 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 n,m,K,cnt,ed;

 int bin[],a[];

 int dis[][],d[],last[];

 int f[][];

 bool vis[];

 struct data{int to,next,v;}e[];

 void insert(int u,int v,int w)

 {

     e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w;

     e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;e[cnt].v=w;

 }

 void dijkstra(int x)

 {

     priority_queue<pa,vector<pa>,greater<pa> >q;

     for(int i=;i<=n;i++)d[i]=inf;

     for(int i=;i<=n;i++)vis[i]=;

     d[x]=;q.push(make_pair(,x));

     while(!q.empty())

     {

         int now=q.top().second;q.pop();

         if(vis[now])continue;vis[now]=;

         for(int i=last[now];i;i=e[i].next)

             if(d[now]+e[i].v<d[e[i].to])

             {

                 d[e[i].to]=d[now]+e[i].v;

                 q.push(make_pair(d[e[i].to],e[i].to));

             }

     }

     for(int i=;i<=K+;i++)

         dis[x][i]=d[i];

     dis[x][]=d[n];

 }

 void dp()

 {

     for(int now=;now<=ed;now++)

         for(int x=;x<=K+;x++)

             if(f[now][x]!=-)

                 for(int i=;i<=K+;i++)

                 {

                     int to=(now|bin[i-]);

                     if((now&a[i])==a[i])

                         if(f[to][i]>f[now][x]+dis[x][i]||f[to][i]==-)

                             f[to][i]=f[now][x]+dis[x][i];

                 }

 }

 int main()

 {

     bin[]=;for(int i=;i<;i++)bin[i]=bin[i-]<<;

     n=read();m=read();K=read();ed=bin[K]-;

     for(int i=;i<=m;i++)

     {

         int u=read(),v=read(),w=read();

         insert(u,v,w);

     }

     for(int i=;i<=K+;i++)dijkstra(i);

     int x=read();

     for(int i=;i<=x;i++)

     {

         int u=read(),v=read();

         a[v]+=bin[u-];

     }

     memset(f,-,sizeof(f));

     f[][]=;

     dp();

     int ans=inf;

     for(int i=;i<=K+;i++)

         if(f[ed][i]!=-)ans=min(ans,f[ed][i]+dis[i][]);

     printf("%d",ans);

     return ;

 }

相关文章