WC2009 最短路径问题

题目:

  一个 的方格图,每个点上有一个权值(非负),要求支持两种操作:
  1.修改一个点的权值(依然非负)。
  2.查询两点间的最短路径(四联通)。

思路:

  既然要求修改,而且又是一个长条形的方格图,可以考虑把最短路用类似 DP 方式表达出来,然后每次修改后通过线段树上的区间合并维护 DP 数组。
  首先想到的肯定是维护每个区间左侧第 个点到右侧第 个点的最短距离,然后每次查询时合并出要求的区间。但是这样会遗漏一些走到区间外的方案(比如左边的点先往左走再往右)。所以为了包括这种情况,还要再记录每个区间内左边界的点走一圈回到左边界的最短距离,右边也是一样。
  那么现在就有了三个 的数组需要维护()。考虑怎么合并两个区间,因为宽度只有 且权值都为正,所以一条路径最多回折两次(类似一个 形)。而有回折的情况可以先预处理出 表示从左区间的左界 出发,进入右区间再回到左区间的右界的最短距离( 类似)。
   是左区间, 是右区间, 是合并后的区间。
  
  那么 转移就如下:
  (没有回折)
  (有回折)
   的转移如下( 类似):
  (不超出左区间)
  (超出左区间)
  这样线段树上的维护就解决了,接下来的问题就是怎么表达答案了,答案只有下面 种,用 三个区间合并一下就能得到了。
  20190815.png

代码:

#include <bits/stdc++.h>
#define File(_) freopen(#_ ".in", "r", stdin), freopen(#_ ".out", "w", stdout)
#define ALL(x) x.begin(), x.end()
#define mcpy(a, b) memcpy(a, b, sizeof a)
#define mset(a, b) memset(a, b, sizeof a)
#define rep(i, a, b) for(int i(a), i##_END_(b); i <= i##_END_; i++) 
#define drep(i, a, b) for(int i(a), i##_END_(b); i >= i##_END_; i--)
using namespace std;
template<class T> inline bool tomax(T &a, T b) {return a < b ? a = b, 1 : 0;}
template<class T> inline bool tomin(T &a, T b) {return b < a ? a = b, 1 : 0;}
typedef long long ll;
typedef double db;

const int N = 1e5 + 5;
typedef int Array[6][6];

Array lm, mr;
struct Data {
    Array ll, rr, lr;
    Data operator+ (const Data d) const {
        Data ans;
        mset(lm, 63); mset(mr, 63);
        rep(i, 0, 5) rep(j, 0, 5)
            rep(k, 0, 5) {
                tomin(lm[i][j], lr[i][k] + d.ll[k][j]);
                tomin(mr[i][j], d.lr[k][j] + rr[k][i]);
            }
        mset(ans.lr, 63); mcpy(ans.ll, ll); mcpy(ans.rr, d.rr);
        rep(i, 0, 5) rep(j, 0, 5)
            rep(k, 0, 5) {
                tomin(ans.ll[i][j], lm[i][k] + lr[j][k]);
                tomin(ans.rr[i][j], mr[k][i] + d.lr[k][j]);
                tomin(ans.lr[i][j], lm[i][k] + mr[k][j]);
                tomin(ans.lr[i][j], lr[i][k] + d.lr[k][j]);
            }
        return ans;
    }
    void init(int a[]) {
        rep(i, 0, 5) {
            int s = 0;
            rep(j, i, 5) ll[i][j] = lr[i][j] = rr[i][j] = (s += a[j]);
            s = 0;
            drep(j, i, 0) ll[i][j] = lr[i][j] = rr[i][j] = (s += a[j]);
        }
    }
};

int val[N][6];
Data seg[N << 2];
#define ls (o << 1)
#define rs (o << 1 | 1)
#define mid (L + R >> 1)
#define lson ls, L, mid
#define rson rs, mid + 1, R
void build(int o, int L, int R) {
    if(L == R) return seg[o].init(val[L]);
    build(lson); build(rson);
    seg[o] = seg[ls] + seg[rs];
}
void upd(int x, int o, int L, int R) {
    if(L == R) return seg[o].init(val[L]);
    if(x <= mid) upd(x, lson);
    else upd(x, rson);
    seg[o] = seg[ls] + seg[rs];
}
Data qry(int l, int r, int o, int L, int R) {
    if(l == L && r == R) return seg[o];
    if(r <= mid) return qry(l, r, lson);
    else if(l > mid) return qry(l, r, rson);
    else return qry(l, mid, lson) + qry(mid + 1, r, rson);
}

int n, q;
int lr[6][6];
int query(int x1, int y1, int x2, int y2) {
    Data d1, d2 = qry(x1, x2, 1, 1, n), d3;
    if(x1 != 1) d1 = qry(1, x1 - 1, 1, 1, n);
    if(x2 != n) d3 = qry(x2 + 1, n, 1, 1, n);
    ll ans = d2.lr[y1][y2];
    if(x2 != n) {
        rep(i, 0, 5) rep(j, 0, 5) 
            tomin(ans, (ll) d2.lr[y1][i] + d3.ll[i][j] + d2.rr[j][y2]);
    }
    if(x1 != 1) {
        rep(i, 0, 5) rep(j, 0, 5)
            tomin(ans, (ll) d2.ll[y1][i] + d1.rr[i][j] + d2.lr[j][y2]);
    }
    if(x1 != 1 && x2 != n) {
        rep(i, 0, 5) rep(j, 0, 5) rep(k, 0, 5) rep(q, 0, 5) {
            tomin(ans, (ll) d2.ll[y1][i] + d1.rr[i][j] + d2.lr[j][k] + d3.ll[k][q] + d2.rr[q][y2]);
            tomin(ans, (ll) d2.lr[y1][i] + d3.ll[i][j] + d2.lr[k][j] + d1.rr[k][q] + d2.lr[q][y2]);
        }
    }
    return ans;
}

int main() {
    File(shortest);
    scanf("%d", &n);
    rep(i, 0, 5) rep(j, 1, n)
        scanf("%d", &val[j][i]);
    build(1, 1, n);
    scanf("%d", &q);
    while(q--) {
        int f, a, b, c, d;
        scanf("%d", &f);
        if(f == 1) {
            scanf("%d%d%d", &a, &b, &c);
            val[b][a - 1] = c;
            upd(b, 1, 1, n);
        }
        else {
            scanf("%d%d%d%d", &a, &b, &c, &d);
            if(b > d) swap(a, c), swap(b, d);
            printf("%d\n", query(b, a - 1, d, c - 1));
        }
    }
    return 0;
}