「BZOJ1097」[POI2007] 旅游景点atr
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
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
HINT
上面对应于题目中给出的例子。
题解
首先预处理一下K+1个点间的最短路。。。
然后状压dp一下，应该很好yy吧。。。
状压注意去掉冗余情况不然一般会T
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 |
#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=0,f=1;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; } int n,m,K,cnt,ed; int bin[22],a[22]; int dis[22][22],d[20005],last[20005]; int f[1048576][22]; bool vis[20005]; struct data{int to,next,v;}e[400005]; 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=1;i<=n;i++)d[i]=inf; for(int i=1;i<=n;i++)vis[i]=0; d[x]=0;q.push(make_pair(0,x)); while(!q.empty()) { int now=q.top().second;q.pop(); if(vis[now])continue;vis[now]=1; 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=1;i<=K+1;i++) dis[x][i]=d[i]; dis[x][0]=d[n]; } void dp() { for(int now=0;now<=ed;now++) for(int x=1;x<=K+1;x++) if(f[now][x]!=-1) for(int i=2;i<=K+1;i++) { int to=(now|bin[i-2]); if((now&a[i])==a[i]) if(f[to][i]>f[now][x]+dis[x][i]||f[to][i]==-1) f[to][i]=f[now][x]+dis[x][i]; } } int main() { bin[0]=1;for(int i=1;i<22;i++)bin[i]=bin[i-1]<<1; n=read();m=read();K=read();ed=bin[K]-1; for(int i=1;i<=m;i++) { int u=read(),v=read(),w=read(); insert(u,v,w); } for(int i=1;i<=K+1;i++)dijkstra(i); int x=read(); for(int i=1;i<=x;i++) { int u=read(),v=read(); a[v]+=bin[u-2]; } memset(f,-1,sizeof(f)); f[0][1]=0; dp(); int ans=inf; for(int i=1;i<=K+1;i++) if(f[ed][i]!=-1)ans=min(ans,f[ed][i]+dis[i][0]); printf("%d",ans); return 0; } |
OI 课件=>
