【BZOJ-1097】旅游景点atr SPFA + 状压DP

1097: [POI2007]旅游景点atr

Time Limit: 30 Sec  Memory Limit: 357 MB
Submit: 1531  Solved: 352
[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-1097】旅游景点atr         SPFA + 状压DP 上面对应于题目中给出的例子。

Source

Solution

SPFA预处理,状压DP

SPFA预处理出K+1个到各点的距离,状压DP,$dp[i][j]$表示当前状态为$i$(访问过的点的集合),现在在$j$点

转移很好转移..

PS:卡常数...我都以为我要T了...

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
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;
}
#define maxn 20010
#define maxm 400010
int N,M,K,C,dis[maxn],d[][maxn],ans; bool visit[maxn];
struct EdgeNode{int next,to,len,from;}edge[maxm];
int head[maxn],cnt;
void add(int u,int v,int w)
{
cnt++;
edge[cnt].to=v;edge[cnt].from=u;edge[cnt].len=w;edge[cnt].next=head[u];head[u]=cnt;
}
void insert(int u,int v,int w) {add(u,v,w); add(v,u,w);} #define inf 0x7fffffff
void SPFA(int S)
{
queue<int>q; memset(visit,,sizeof(visit));
for (int i=; i<=N; i++) dis[i]=inf;
q.push(S); visit[S]=; dis[S]=;
while (!q.empty())
{
int now=q.front(); q.pop(); visit[now]=;
for (int i=head[now]; i; i=edge[i].next)
if (dis[edge[i].to]>dis[now]+edge[i].len)
{
dis[edge[i].to]=dis[now]+edge[i].len;
if (!visit[edge[i].to])
q.push(edge[i].to),visit[edge[i].to]=;
}
}
for (int i=; i<=N; i++) d[S][i]=dis[i];
}
int Min(int a,int b)
{
if (a==-) return b;
if (a>b) return b; else return a;
}
int dp[<<][],zt[maxn];
void DP()
{
for (int i=; i<=(<<K)-; i++)
for (int j=; j<=K+; j++)
if (dp[i][j]!=-)
for (int k=; k<=K+; k++)
if ((i&zt[k])==zt[k])
dp[i|(<<(k-))][k]=Min(dp[i|(<<(k-))][k],dp[i][j]+d[j][k]);
}
int main()
{
N=read(),M=read(),K=read();
for (int u,v,w,i=; i<=M; i++)
u=read(),v=read(),w=read(),insert(u,v,w);
for (int i=; i<=K+; i++) SPFA(i);
C=read();
for (int x,y,i=; i<=C; i++)
x=read(),y=read(),zt[y]|=(<<(x-));
memset(dp,-,sizeof(dp)); dp[][]=;
DP(); ans=0x7fffffff;
for (int i=; i<=K+; i++)
if (dp[(<<K)-][i]!=-) ans=Min(dp[(<<K)-][i]+d[i][N],ans);
printf("%d",ans);
return ;
}

开了两个DeBug,第一次忘删了OLE,删了一个还剩一个又WA了...然后卡时..

上一篇:有损FLV视频的画面宽高比修改方案


下一篇:Loj 6433. 「PKUSC2018」最大前缀和 (状压dp)