0%

BZOJ 2834 解题报告

发表于 更新于 分类于 ， ，

题意简述

有一个\(n * n(n \leq 2 * 10 ^ 4)\)的矩阵，矩阵上只能横着或竖着移动，移动代价是\(2/每格\)。矩阵上还有\(m(m \leq 10 ^ 5)\)个点可以原地不动改变移动的方向（横着变为竖着，竖着变为横着），代价为\(1/每次\)。给定起点和终点，求从起点移动到终点的最小代价。如果从起点出发无法到达终点，输出\(-1\)。

时间限制（总）：10s 空间限制：128MB

题目链接

BZOJ 2834

题解

题目要求最小代价，所以考虑使用最短路算法解决。由于\(n ^ 2\)过大，所以只考虑能改变方向的\(m\)个点以及起点和终点。分别处理竖着移动和横着移动的情况，对每个点拆点，设点的编号为\(i\)，那么拆点后点的编号就是\(2 \times i和2 \times i + 1\)。第一个点用于横向连边，第二个点用于纵向连边。然后同行和同列的相邻两点间连无向边，边权为矩阵上两点距离\(\times 2\)。如果不是起点或终点，则拆成的两个点之间连一条边权为\(1\)的无向边，否则连一条边权为\(0\)的无向边。之后使用最短路算法就可以得到答案。注意不要忘记判断不可达的状况。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <utility>
#include <cmath>

using namespace std;

const int MAXM = 800010;
const int MAXN = 200010;
const int INF = 0x3f3f3f3f;

template<typename T>
T read() {
    T result = 0;int f = 1;char c = getchar();
    while(c > '9' || c < '0') {if(c == '-') f *= -1;c = getchar();}
    while(c <= '9' && c >= '0') {result = result * 10 + c - '0';c = getchar();}
    return result * f;
}

struct Graph {
    struct Edge {
        int next,to,weight;
    };
    Edge edges[MAXM];
    int tot,heads[MAXN];

    Graph() : tot(0) {
        memset(heads,-1,sizeof(heads));
    }

    void addEdge(int u,int v,int w) {
        edges[tot].next = heads[u];
        edges[tot].to = v;
        edges[tot].weight = w;
        heads[u] = tot++;
    }

    void addTwoEdges(int u,int v,int w) {
        addEdge(u,v,w);
        addEdge(v,u,w);
    }

} graph;

int dis[MAXN];
bool visit[MAXN];

void spfa(int S) {
    queue<int> que;
    que.push(S);
    memset(dis,INF,sizeof(dis));
    memset(visit,false,sizeof(visit));
    visit[S] = true;
    dis[S] = 0;
    while(!que.empty()) {
        int now = que.front();
        que.pop();
        visit[now] = false;
        for(int i = graph.heads[now];i != -1;i = graph.edges[i].next) {
            Graph::Edge &tmpEdge = graph.edges[i];
            if(dis[now] + tmpEdge.weight >= dis[tmpEdge.to]) continue;
            dis[tmpEdge.to] = dis[now] + tmpEdge.weight;
            if(!visit[tmpEdge.to]) {
                visit[tmpEdge.to] = true;
                que.push(tmpEdge.to);
            }
        }
    }
}

struct Data {
    int x,y,id;

    Data() : x(0) , y(0) , id(0) { }

    Data(int x,int y,int id) : x(x) , y(y) , id(id) { }
} datas[MAXN];

bool comp1(const Data &a,const Data &b) {
    if(a.x == b.x) return a.y < b.y;
    return a.x < b.x;
}

bool comp2(const Data &a,const Data &b) {
    if(a.y == b.y) return a.x < b.x;
    return a.y < b.y;
}

int main() {
    int n = read<int>(),m = read<int>(),S = m,T = m + 1;
    for(int i = 0;i < m + 2;i++) {
        int x = read<int>(),y = read<int>();
        datas[i] = Data(x,y,i);
    }
    for(int i = 0;i < m;i++) {
        graph.addTwoEdges(2 * i,2 * i + 1,1);
    }
    sort(datas,datas + m + 2,comp1);
    for(int i = 1;i < m + 2;i++) {
        if(datas[i].x == datas[i - 1].x) {
            graph.addTwoEdges(2 * datas[i].id,2 * datas[i - 1].id,2 * (datas[i].y - datas[i - 1].y));
        }
    }
    sort(datas,datas + m + 2,comp2);
    for(int i = 1;i < m + 2;i++) {
        if(datas[i].y == datas[i - 1].y) {
            graph.addTwoEdges(2 * datas[i].id + 1,2 * datas[i - 1].id + 1,2 * (datas[i].x - datas[i - 1].x));
        }
    }
    S *= 2;
    T *= 2;
    graph.addTwoEdges(S,S + 1,0);
    graph.addTwoEdges(T,T + 1,0);
    spfa(S);
    if(dis[T] == INF) {
        printf("-1\n");
    }else {
        printf("%d\n",dis[T]);
    }
    return 0;
}