首页 > 代码库 > [BZOJ1097][POI2007]旅游景点atr
[BZOJ1097][POI2007]旅游景点atr
[BZOJ1097][POI2007]旅游景点atr
试题描述
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需要的。
输入
第一行包含3个整数N(2<=N<=20000),M(1<=M<=200000),K(0<=K<=20),意义如上所述。
输出
只包含一行,包含一个整数,表示最短的旅行距离。
输入示例
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
输出示例
19
数据规模及约定
见“输入”
题解
虽然点数很多,但是我们只需要关心 K+2 个点(K 个必须停留的节点以及起点和终点)之间的最短路就好了,于是可以做最多 22 次最短路预处理处 Dis[i][j] 表示第 i 个关键点到第 j 个关键点的距离。
接下来就是 dp,f(S, i) 表示已经在集合 S 中的点停留过了,现在在节点 i 所需要的最短距离。你可以记录一个 bef[i] 表示在 i 停留之前需要停留的节点集合,然后转移的时候看看 bef[i] 是不是当前状态 S 的子集,这就是细节了。
注意特判 K = 0 的情况!!!
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <algorithm> #include <queue> using namespace std; int read() { int x = 0, f = 1; char c = getchar(); while(!isdigit(c)){ if(c == ‘-‘) f = -1; c = getchar(); } while(isdigit(c)){ x = x * 10 + c - ‘0‘; c = getchar(); } return x * f; } #define maxn 20010 #define maxm 400010 #define maxk 25 #define maxs 1048576 #define oo (1ll << 60) #define LL long long int n, m, K, head[maxn], to[maxm], nxt[maxm], dist[maxm], idk[maxk]; LL Dis[maxk][maxk]; void AddEdge(int a, int b, int c) { to[++m] = b; dist[m] = c; nxt[m] = head[a]; head[a] = m; swap(a, b); to[++m] = b; dist[m] = c; nxt[m] = head[a]; head[a] = m; return ; } LL d[maxn]; bool vis[maxn]; struct Node { int u, d; Node() {} Node(int _, int __): u(_), d(__) {} bool operator < (const Node& t) const { return d > t.d; } }; priority_queue <Node> Q; void ShortPath(int si) { int s = idk[si]; for(int i = 1; i <= n; i++) d[i] = oo; memset(vis, 0, sizeof(vis)); d[s] = 0; Q.push(Node(s, 0)); while(!Q.empty()) { int u = Q.top().u; Q.pop(); if(vis[u]) continue; vis[u] = 1; for(int e = head[u]; e; e = nxt[e]) if(d[to[e]] > d[u] + dist[e]) { d[to[e]] = d[u] + dist[e]; if(!vis[to[e]]) Q.push(Node(to[e], d[to[e]])); } } for(int i = 1; i <= K + 2; i++) if(i != si) Dis[si][i] = d[idk[i]]; return ; } int bef[maxk]; LL f[maxs][maxk]; void up(LL& a, LL b) { a = min(a, b); return ; } int main() { n = read(); int m = read(); K = read(); for(int i = 1; i <= m; i++) { int a = read(), b = read(), c = read(); AddEdge(a, b, c); } for(int i = 2; i <= K + 1; i++) idk[i-1] = i; idk[K+1] = 1; idk[K+2] = n; m = read(); for(int i = 1; i <= m; i++) { int a = read() - 1, b = read() - 1; bef[b] |= (1 << a - 1); } for(int i = 1; i <= K + 2; i++) ShortPath(i); int all = (1 << K) - 1; for(int S = 0; S <= all; S++) for(int i = 1; i <= K; i++) f[S][i] = oo; for(int i = 1; i <= K; i++) if(!bef[i]) f[1<<i-1][i] = Dis[K+1][i]; for(int S = 0; S <= all; S++) for(int i = 1; i <= K; i++) if(f[S][i] < oo) for(int j = 1; j <= K; j++) if((S >> j - 1 & 1) == 0 && (S & bef[j]) == bef[j]) up(f[S|(1<<j-1)][j], f[S][i] + Dis[i][j]); LL ans = oo; for(int i = 1; i <= K; i++) if(f[all][i] < oo) up(ans, f[all][i] + Dis[i][K+2]); printf("%lld\n", K ? ans : Dis[1][2]); return 0; }
[BZOJ1097][POI2007]旅游景点atr
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。