NC20522. [ZJOI2016]旅行者
描述
输入描述
第一行包含 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，表示两个路口的位置。
输出描述
输出共q行，每行包含一个整数表示从一个路口到另一个路口最少需要花的时间。
示例1
输入:
2 2 2 3 6 4 2 1 1 2 2 1 2 2 1
输出:
6 7
C++14(g++5.4) 解法, 执行用时: 767ms, 内存消耗: 6264K, 提交时间: 2020-04-29 17:09:05
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int read()
{
int x = 0, f = 1; char ch = getchar();
while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
while (isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }
return x * f;
}
const int MAX = 200033;
const int inf = 100000000;
#define id(i, j) ((i - 1) * m + (j))
int n, m, cnte, Q, cntid;
int invx[20033], invy[20033];
int fir[20033];
struct Query
{
int x, y, xx, yy, id;
} q[100033], tmp[100033];
struct edge
{
int to, nxt, w;
edge() {}
edge(int a, int b, int c)
{
to = a, nxt = b, w = c;
}
} e[200033];
void addedge(int u, int v, int w)
{
e[++cnte] = edge(v, fir[u], w), fir[u] = cnte;
e[++cnte] = edge(u, fir[v], w), fir[v] = cnte;
}
int ans[100033], dis[20033];
int que[2000033];
bool inq[20033];
void dijkstra(int s, int xl, int xr, int yl, int yr, int h)
{
int d = dis[s];
for (int i = xl; i <= xr; i++)
for (int j = yl; j <= yr; j++)
dis[id(i, j)] = h ? dis[id(i, j)] + d : inf;
dis[s] = 0;
inq[s] = 1;
int l = 10000, r = 10000;
que[r++] = s;
while (l != r)
{
int u = que[l++];
inq[u] = 0;
for (int i = fir[u]; i; i = e[i].nxt)
{
int v = e[i].to;
int vy = invy[v], vx = invx[v];
if (vx >= xl && vx <= xr && vy >= yl && vy <= yr)
if (dis[v] > dis[u] + e[i].w)
{
dis[v] = dis[u] + e[i].w;
if (!inq[v])
{
if (dis[v] <= dis[que[l]])
que[--l] = v;
else que[r++] = v;
inq[v] = 1;
}
}
}
}
}
void solve(int xl, int xr, int yl, int yr, int ql, int qr)
{
if (ql > qr) return;
if (xr - xl > yr - yl)
{
int mid = (xl + xr) >> 1;
for (int i = yl; i <= yr; i++)
{
dijkstra(id(mid, i), xl, xr, yl, yr, i - yl);
for (int j = ql; j <= qr; j++)
ans[q[j].id] = min(ans[q[j].id], dis[id(q[j].x, q[j].y)] + dis[id(q[j].xx, q[j].yy)]);
}
int l = ql - 1, r = qr + 1;
for (int i = ql; i <= qr; i++)
{
if (q[i].x < mid && q[i].xx < mid)
tmp[++l] = q[i];
else if (q[i].x > mid && q[i].xx > mid)
tmp[--r] = q[i];
}
for (int i = ql; i <= l; i++)
q[i] = tmp[i];
for (int i = r; i <= qr; i++)
q[i] = tmp[i];
solve(xl, mid - 1, yl, yr, ql, l);
solve(mid + 1, xr, yl, yr, r, qr);
}
else
{
int mid = (yl + yr) >> 1;
for (int i = xl; i <= xr; i++)
{
dijkstra(id(i, mid), xl, xr, yl, yr, i - xl);
for (int j = ql; j <= qr; j++)
ans[q[j].id] = min(ans[q[j].id], dis[id(q[j].x, q[j].y)] + dis[id(q[j].xx, q[j].yy)]);
}
int l = ql - 1, r = qr + 1;
for (int i = ql; i <= qr; i++)
{
if (q[i].y < mid && q[i].yy < mid)
tmp[++l] = q[i];
else if (q[i].y > mid && q[i].yy > mid)
tmp[--r] = q[i];
}
for (int i = ql; i <= l; i++)
q[i] = tmp[i];
for (int i = r; i <= qr; i++)
q[i] = tmp[i];
solve(xl, xr, yl, mid - 1, ql, l);
solve(xl, xr, mid + 1, yr, r, qr);
}
}
int main()
{
memset(ans, 63, sizeof ans);
n = read(), m = read();
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
cntid++;
invx[cntid] = i, invy[cntid] = j;
}
for (int i = 1; i <= n; i++)
for (int j = 1; j < m; j++)
addedge(id(i, j), id(i, j + 1), read());
for (int i = 1; i < n; i++)
for (int j = 1; j <= m; j++)
addedge(id(i, j), id(i + 1, j), read());
Q = read();
for (int i = 1; i <= Q; i++)
{
q[i].x = read(), q[i].y = read();
q[i].xx = read(), q[i].yy = read();
q[i].id = i;
}
solve(1, n, 1, m, 1, Q);
for (int i = 1; i <= Q; i++)
printf("%d\n", ans[i]);
return 0;
}
C++(g++ 7.5.0) 解法, 执行用时: 1768ms, 内存消耗: 5580K, 提交时间: 2022-09-29 03:38:17
#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
using PII = pair<int, int>;
const int N = 250010, M = 2500010, INF = 0x3f3f3f3f;
const int dir[][2] = {-1, 0, 0, 1, 1, 0, 0, -1};
int n, m, Q;
int dis[N];
bool vis[N];
struct Node {
int x0, y0, x1, y1, id;
} q[N], tmp[N];
vector<vector<int>> r, c, id;
int ans[N];
int v[4][N];
void dijkstra(int xl, int xr, int yl, int yr, int S) {
priority_queue<PII, vector<PII>, greater<PII>> heap;
for (int i = xl; i <= xr; i++)
for (int j = yl; j <= yr; j++)
dis[id[i][j]] = INF, vis[id[i][j]] = false;
dis[S] = 0, heap.push({0, S});
while (heap.size()) {
auto [d, t] = heap.top();
heap.pop();
if (vis[t]) continue;
vis[t] = true;
int x = (t - 1) / m + 1, y = (t - 1) % m + 1;
for (int u = 0; u < 4; u++) {
int tx = x + dir[u][0], ty = y + dir[u][1];
if (tx < xl || tx > xr || ty < yl || ty > yr) continue;
int nt = id[tx][ty];
if (d + v[u][t] < dis[nt]) {
dis[nt] = d + v[u][t];
heap.push({dis[nt], nt});
}
}
}
}
void solve(int xl, int xr, int yl, int yr, int ql, int qr) {
if (xl > xr || yl > yr || ql > qr) return;
int deltax = xr - xl, deltay = yr - yl;
if (deltax > deltay) {
int mid = xl + xr >> 1;
for (int i = yl; i <= yr; i++) {
dijkstra(xl, xr, yl, yr, id[mid][i]);
for (int j = ql; j <= qr; j++) {
auto& [x0, y0, x1, y1, o] = q[j];
ans[o] = min(ans[o], dis[id[x0][y0]] + dis[id[x1][y1]]);
}
}
int l = ql - 1, r = qr + 1;
for (int i = ql; i <= qr; i++) {
if (q[i].x0 < mid && q[i].x1 < mid) tmp[++l] = q[i];
else if (q[i].x0 > mid && q[i].x1 > mid) tmp[--r] = q[i];
}
for (int i = ql; i <= l; i++) q[i] = tmp[i];
for (int i = r; i <= qr; i++) q[i] = tmp[i];
solve(xl, mid, yl, yr, ql, l);
solve(mid + 1, xr, yl, yr, r, qr);
}
else {
int mid = yl + yr >> 1;
for (int i = xl; i <= xr; i++) {
dijkstra(xl, xr, yl, yr, id[i][mid]);
for (int j = ql; j <= qr; j++) {
auto& [x0, y0, x1, y1, o] = q[j];
ans[o] = min(ans[o], dis[id[x0][y0]] + dis[id[x1][y1]]);
}
}
int l = ql - 1, r = qr + 1;
for (int i = ql; i <= qr; i++) {
if (q[i].y0 < mid && q[i].y1 < mid) tmp[++l] = q[i];
else if (q[i].y0 > mid && q[i].y1 > mid) tmp[--r] = q[i];
}
for (int i = ql; i <= l; i++) q[i] = tmp[i];
for (int i = r; i <= qr; i++) q[i] = tmp[i];
solve(xl, xr, yl, mid, ql, l);
solve(xl, xr, mid + 1, yr, r, qr);
}
}
int main() {
cin >> n >> m;
c = r = id = vector<vector<int>>(n + 5, vector<int>(m + 5));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
id[i][j] = (i - 1) * m + j;
for (int i = 1; i <= n; i++) {
for (int j = 1; j < m; j++) {
cin >> r[i][j];
v[1][id[i][j]] = v[3][id[i][j + 1]] = r[i][j];
}
}
for (int i = 1; i < n; i++) {
for (int j = 1; j <= m; j++) {
cin >> c[i][j];
int t = id[i][j];
v[2][id[i][j]] = v[0][id[i + 1][j]] = c[i][j];
}
}
cin >> Q;
for (int i = 1; i <= Q; i++) {
auto& [x0, y0, x1, y1, id] = q[i];
cin >> x0 >> y0 >> x1 >> y1;
id = i;
}
memset(ans, 0x3f, sizeof ans);
solve(1, n, 1, m, 1, Q);
for (int i = 1; i <= Q; i++)
cout << ans[i] << '\n';
return 0;
}
C++(clang++ 11.0.1) 解法, 执行用时: 1663ms, 内存消耗: 5100K, 提交时间: 2022-10-24 16:52:13
#include<bits/stdc++.h>
using namespace std;
#define pos(x,y) (x-1)*m+y
#define add(x,y,z) G[x].push_back({y,z}),G[y].push_back({x,z})
typedef pair<int,int> pa;
const int MAXN=2e4+5;
const int MAXQ=1e5+5;
const int INF=0x3f3f3f3f;
struct point
{
int sx,sy,tx,ty;
}input[MAXQ];
vector<pa>G[MAXN];
int dis[MAXN];
bool vis[MAXN];
int query[MAXQ],tmp1[MAXQ],tmp2[MAXQ],ans[MAXQ];
int n,m,q;
void dijkstra(int lx,int rx,int ly,int ry,int s)
{
priority_queue< pa,vector<pa>,greater<pa> >q;
for(int i=lx;i<=rx;++i) for(int j=ly;j<=ry;++j) dis[pos(i,j)]=INF,vis[pos(i,j)]=0;
dis[s]=0,q.push({dis[s],s});
while(!q.empty())
{
int x=q.top().second;q.pop();
if(vis[x]) continue;
vis[x]=1;
for(auto [y,z]:G[x])
{
int xx,yy;
yy=(y%m==0)?m:y%m;
xx=(y-yy)/m+1;
if(!(lx<=xx && xx<=rx && ly<=yy && yy<=ry)) continue;
if(dis[y]>dis[x]+z) dis[y]=dis[x]+z,q.push({dis[y],y});
}
}
}
void dfs(int lx,int rx,int ly,int ry,int lq,int rq)
{
if(lx>rx || ly>ry || lq>rq) return;
if(rx-lx>ry-ly)
{
int mid=(lx+rx)>>1;
for(int i=ly;i<=ry;++i)
{
dijkstra(lx,rx,ly,ry,pos(mid,i));
for(int j=lq;j<=rq;++j) ans[query[j]]=min(ans[query[j]],dis[pos(input[query[j]].sx,input[query[j]].sy)]+dis[pos(input[query[j]].tx,input[query[j]].ty)]);
}
int cnt1=0,cnt2=0;
for(int i=lq;i<=rq;++i)
{
if((input[query[i]].sx<=mid && input[query[i]].tx>=mid) || (input[query[i]].tx<=mid && input[query[i]].sx>=mid)) continue;
if(input[query[i]].sx<mid) tmp1[++cnt1]=query[i];
else tmp2[++cnt2]=query[i];
}
for(int i=lq,j=1;j<=cnt1;++i,++j) query[i]=tmp1[j];
for(int i=lq+cnt1,j=1;j<=cnt2;++i,++j) query[i]=tmp2[j];
dfs(lx,mid-1,ly,ry,lq,lq+cnt1-1);
dfs(mid+1,rx,ly,ry,lq+cnt1,lq+cnt1+cnt2-1);
}
else
{
int mid=(ly+ry)>>1;
for(int i=lx;i<=rx;++i)
{
dijkstra(lx,rx,ly,ry,pos(i,mid));
for(int j=lq;j<=rq;++j) ans[query[j]]=min(ans[query[j]],dis[pos(input[query[j]].sx,input[query[j]].sy)]+dis[pos(input[query[j]].tx,input[query[j]].ty)]);
}
int cnt1=0,cnt2=0;
for(int i=lq;i<=rq;++i)
{
if((input[query[i]].sy<=mid && input[query[i]].ty>=mid) || (input[query[i]].ty<=mid && input[query[i]].sy>=mid)) continue;
if(input[query[i]].sy<mid) tmp1[++cnt1]=query[i];
else tmp2[++cnt2]=query[i];
}
for(int i=lq,j=1;j<=cnt1;++i,++j) query[i]=tmp1[j];
for(int i=lq+cnt1,j=1;j<=cnt2;++i,++j) query[i]=tmp2[j];
dfs(lx,rx,ly,mid-1,lq,lq+cnt1-1);
dfs(lx,rx,mid+1,ry,lq+cnt1,lq+cnt1+cnt2-1);
}
}
int main()
{
cin>>n>>m;
int x;
for(int i=1;i<=n;++i) for(int j=1;j<m;++j) scanf("%d",&x),add(pos(i,j),pos(i,j+1),x);
for(int i=1;i<n;++i) for(int j=1;j<=m;++j) scanf("%d",&x),add(pos(i,j),pos(i+1,j),x);
cin>>q;
for(int i=1;i<=q;++i) scanf("%d %d %d %d",&input[i].sx,&input[i].sy,&input[i].tx,&input[i].ty),query[i]=i;
memset(ans,0x3f,sizeof(ans));
dfs(1,n,1,m,1,q);
for(int i=1;i<=q;++i) printf("%d\n",ans[i]);
return 0;
}