Bzoj1097 [poi2007]旅游景点atr

Posted by yjjr's blog on February 6, 2018

标签:状压DP,最短路

Description

  FGD想从成都去上海旅游。在旅途中他希望经过一些城市并在那里欣赏风景,品尝风味小吃或者做其他的有趣的事情。经过这些城市的顺序不是完全随意的,比如说FGD不希望在刚吃过一顿大餐之后立刻去下一个城市登山,而是希望去另外什么地方喝下午茶。幸运的是,FGD的旅程不是既定的,他可以在某些旅行方案之间进行选择。由于FGD非常讨厌乘车的颠簸,他希望在满足他的要求的情况下,旅行的距离尽量短,这样他就有足够的精力来欣赏风景或者是泡MM^_^.整个城市交通网络包含N个城市以及城市与城市之间的双向道路M条。城市自1N依次编号,道路亦然。没有从某个城市直接到它自己的道路,两个城市之间最多只有一条道路直接相连,但可以有多条连接两个城市的路径。任意两条道路如果相遇,则相遇点也必然是这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),意义如上所述。

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

http://www.lydsy.com/JudgeOnline/images/1097.jpg上面对应于题目中给出的例子。

 

题意:求1àn的最短路,这条最短路要按给定的顺序经过K个点

 

SPFA预处理出k+1个点到其余点的最小距离

F[i][j]表示当前位于j点,状态为i(访问过的点的集合)

无脑转移

Code

#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<queue>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define mem(x,num) memset(x,num,sizeof x)
#define LL long long
using namespace std;

const int inf=1000000000,maxn=20006;
int n,m,k,cnt=0,ed,ans=inf;
int bin[23],a[23],dis[23][23],d[maxn],head[maxn],f[2000006][23];
bool visit[maxn];
struct edge{int to,next,w;}e[500006];

inline LL read()
{
	LL f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

void spfa(int x)
{
	int dist[maxn];
	queue<LL>q;
	mem(visit,0);
	rep(i,1,n)dist[i]=inf;
	q.push(x),visit[x]=1,dist[x]=0;
	while(!q.empty()){
		int now=q.front();q.pop();visit[now]=0;
		#define reg(x) for(int i=head[x];i;i=e[i].next)
		reg(now)
		    if(dist[e[i].to]>dist[now]+e[i].w){
				dist[e[i].to]=dist[now]+e[i].w;
				if(!visit[e[i].to])
					q.push(e[i].to),visit[e[i].to]=1;
			}
	}
	rep(i,1,k+1)dis[x][i]=dist[i];
	dis[x][0]=dist[n];
}

void dp()
{
	rep(now,0,ed)
	    rep(x,1,k+1)
			if(f[now][x]!=-1)
				rep(i,2,k+1){
					int v=(now|bin[i-2]);
					if((now&a[i])==a[i])
						if(f[v][i]>f[now][x]+dis[x][i]||f[v][i]==-1)
							f[v][i]=f[now][x]+dis[x][i];
				}
}
int main()
{
	bin[0]=1;rep(i,1,22)bin[i]=bin[i-1]<<1;
	n=read(),m=read(),k=read();ed=bin[k]-1;
	rep(i,1,m){
		int u=read(),v=read(),w=read();
		e[++cnt]=(edge){v,head[u],w};head[u]=cnt;
		e[++cnt]=(edge){u,head[v],w};head[v]=cnt;
	}
	rep(i,1,k+1)spfa(i);
	int x=read();
	rep(i,1,x){
		int u=read(),v=read();
		a[v]+=bin[u-2];
	}
	mem(f,-1);
	f[0][1]=0;
	dp();
	rep(i,1,k+1)
		if(f[ed][i]!=-1)ans=min(ans,f[ed][i]+dis[i][0]);
	printf("%d\n",ans);
	return 0;
}


本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr