首页 > 代码库 > 【BZOJ4456】 [Zjoi2016]旅行者 / 【UOJ #184】 【ZJOI2016】旅行者
【BZOJ4456】 [Zjoi2016]旅行者 / 【UOJ #184】 【ZJOI2016】旅行者
Description
小Y来到了一个新的城市旅行。她发现了这个城市的布局是网格状的，也就是有n条从东到西的道路和m条从南到北
的道路，这些道路两两相交形成n×m个路口 (i,j)(1≤i≤n,1≤j≤m)。她发现不同的道路路况不同，所以通过不
同的路口需要不同的时间。通过调查发现，从路口(i,j)到路口(i,j+1)需要时间 r(i,j)，从路口(i,j)到路口(i+1
,j)需要时间c(i,j)。注意这里的道路是双向的。小Y有q个询问，她想知道从路口(x1,y1)到路口(x2,y2)最少需要
花多少时间。
Input
第一行包含 2 个正整数n,m，表示城市的大小。
接下来n行，每行包含m?1个整数，第i行第j个正整数表示从一个路口到另一个路口的时间r(i,j)。
接下来n?1行，每行包含m个整数，第i行第j个正整数表示从一个路口到另一个路口的时间c(i,j)。
接下来一行，包含1个正整数q，表示小Y的询问个数。
接下来q行，每行包含4个正整数 x1,y1,x2,y2，表示两个路口的位置。
Output
输出共q行，每行包含一个整数表示从一个路口到另一个路口最少需要花的时间。
Sample Input
2 2
2
3
6 4
2
1 1 2 2
1 2 2 1
2
3
6 4
2
1 1 2 2
1 2 2 1
Sample Output
6
7
7
Solution
网格图求任意两点间的最短路。
可以用分治来解决。
之前校内训练的时候CJK学长出了一道IOI2013的题，就是用线段树来维护网格图的最短路。这题也很类似，离线询问以后，每次把长边拿出来分治，考虑经过中间这一排点的和没经过这一排点的。没经过的递归下去做，经过的就跑一遍堆优化dj或者spfa就好了。
Code
1 #include <cstdio> 2 #include <cstring> 3 4 #define R register 5 #define maxn 20010 6 #define cmin(_a, _b) (_a > (_b) ? _a = (_b) : 0) 7 #define id(_a, _b) (((_a) - 1) * m + (_b) - 1) 8 #define id1(_x) ((_x) / m + 1) 9 #define id2(_x) ((_x) % m + 1) 10 int n, m; 11 struct Edge { 12 Edge *next; 13 int to, w; 14 } *last[maxn], e[maxn << 4], *ecnt = e; 15 inline void link(R int a, R int b, R int w) 16 { 17 *++ecnt = (Edge) {last[a], b, w}; last[a] = ecnt; 18 *++ecnt = (Edge) {last[b], a, w}; last[b] = ecnt; 19 } 20 struct Ques { 21 int x1, y1, x2, y2, id; 22 } qu[100010], tmp[100010]; 23 int ans[100010], dis[maxn], q[maxn * 50], r[maxn], c[maxn]; 24 bool inq[maxn]; 25 #define inf 0x7fffffff 26 struct Data { 27 int pos, dis; 28 inline bool operator < (const Data &that) const {return dis > that.dis;} 29 } ; 30 #include <queue> 31 std::priority_queue<Data> hp; 32 void spfa(R int s, R int nl, R int nr, R int ml, R int mr) 33 { 34 //for (R int i = nl; i <= nr; ++i) for (R int j = ml; j <= mr; ++j) dis[id(i, j)] = inf; 35 /* 36 R int head = maxn * 20, tail = maxn * 20 + 1; 37 q[maxn * 20 + 1] = s; dis[s] = 0; 38 */ 39 hp.push((Data) {s, dis[s] = 0}); 40 while (/*head < tail*/!hp.empty()) 41 { 42 // R int now = q[++head]; inq[now] = 0; 43 R Data tp = hp.top(); hp.pop(); 44 R int now = tp.pos; 45 for (R Edge *iter = last[now]; iter; iter = iter -> next) 46 if (dis[iter -> to] > dis[now] + iter -> w && nl <= id1(iter -> to) && id1(iter -> to) <= nr && ml <= id2(iter -> to) && id2(iter -> to) <= mr) 47 { 48 dis[iter -> to] = dis[now] + iter -> w; 49 // !inq[iter -> to] ? inq[dis[iter -> to] < dis[q[head + 1]] ? q[head--] = iter -> to : q[++tail] = iter -> to] = 1 : 0; 50 hp.push((Data) {iter -> to, dis[iter -> to]}); 51 } 52 } 53 } 54 void work(R int nl, R int nr, R int ml, R int mr, R int ql, R int qr) 55 { 56 if (nl > nr || ml > mr) return ; 57 if (ql > qr) return ; 58 if (nr - nl + 1 <= mr - ml + 1) 59 { 60 R int mid = ml + mr >> 1; 61 for (R int i = nl; i <= nr; ++i) for (R int j = ml; j <= mr; ++j) dis[id(i, j)] = inf; 62 for (R int i = nl; i <= nr; ++i) 63 { 64 if (i != nl) 65 { 66 for (R int ii = nl; ii <= nr; ++ii) for (R int jj = ml; jj <= mr; ++jj) 67 dis[id(ii, jj)] += c[id(i - 1, mid)]; 68 } 69 spfa(id(i, mid), nl, nr, ml, mr); 70 for (R int j = ql; j <= qr; ++j) 71 cmin(ans[qu[j].id], dis[id(qu[j].x1, qu[j].y1)] + dis[id(qu[j].x2, qu[j].y2)]); 72 } 73 R int qql = ql - 1, qqr = qr + 1; 74 for (R int i = ql; i <= qr; ++i) 75 if (qu[i].y1 < mid && qu[i].y2 < mid) 76 tmp[++qql] = qu[i]; 77 else if (qu[i].y1 > mid && qu[i].y2 > mid) 78 tmp[--qqr] = qu[i]; 79 80 for (R int i = ql; i <= qql; ++i) qu[i] = tmp[i]; 81 for (R int i = qqr; i <= qr; ++i) qu[i] = tmp[i]; 82 work(nl, nr, ml, mid - 1, ql, qql); 83 work(nl, nr, mid + 1, mr, qqr, qr); 84 } 85 else 86 { 87 R int mid = nl + nr >> 1; 88 for (R int i = nl; i <= nr; ++i) for (R int j = ml; j <= mr; ++j) dis[id(i, j)] = inf; 89 for (R int i = ml; i <= mr; ++i) 90 { 91 if (i != ml) 92 { 93 for (R int ii = nl; ii <= nr; ++ii) for (R int jj = ml; jj <= mr; ++jj) 94 dis[id(ii, jj)] += r[id(mid, i - 1)]; 95 } 96 spfa(id(mid, i), nl, nr, ml, mr); 97 for (R int j = ql; j <= qr; ++j) 98 cmin(ans[qu[j].id], dis[id(qu[j].x1, qu[j].y1)] + dis[id(qu[j].x2, qu[j].y2)]); 99 }100 R int qql = ql - 1, qqr = qr + 1;101 for (R int i = ql; i <= qr; ++i)102 if (qu[i].x1 < mid && qu[i].x2 < mid)103 tmp[++qql] = qu[i];104 else if (qu[i].x1 > mid && qu[i].x2 > mid)105 tmp[--qqr] = qu[i];106 107 for (R int i = ql; i <= qql; ++i) qu[i] = tmp[i];108 for (R int i = qqr; i <= qr; ++i) qu[i] = tmp[i];109 work(nl, mid - 1, ml, mr, ql, qql);110 work(mid + 1, nr, ml, mr, qqr, qr);111 }112 }113 int main()114 {115 scanf("%d%d", &n, &m);116 for (R int i = 1; i <= n; ++i) for (R int j = 1; j < m; ++j)117 {R int w; scanf("%d", &w); link(id(i, j), id(i, j + 1), w); r[id(i, j)] = w;}118 for (R int i = 1; i < n; ++i) for (R int j = 1; j <= m; ++j)119 {R int w; scanf("%d", &w); link(id(i, j), id(i + 1, j), w); c[id(i, j)] = w;}120 R int Q; scanf("%d", &Q);121 for (R int i = 1; i <= Q; ++i) scanf("%d%d%d%d", &qu[i].x1, &qu[i].y1, &qu[i].x2, &qu[i].y2), qu[i].id = i;122 memset(ans, 63, (Q + 1) << 2);123 work(1, n, 1, m, 1, Q);124 for (R int i = 1; i <= Q; ++i) printf("%d\n", ans[i]);125 return 0;126 }
【BZOJ4456】 [Zjoi2016]旅行者 / 【UOJ #184】 【ZJOI2016】旅行者
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。