【洛谷 P2226】 [HNOI2001]遥控赛车比赛（最短路）

题目链接

首先拆点，把每个点拆成4个点，表示到达这个点的时候赛车的朝向。

然后考虑连边。

相邻同向并且都是可以走的点直接连边权1的边。

至于怎么转向，只需在每个点\(i\)向每个方向一直拓展直到不能走为止，如果当前点的深度大于灵敏度，从\(i\)向这个点的其它3个方向都连一条边权为这个点的深度的边。

然后跑\(SPFA\)（至于为什么是\(SPFA\)，我才不会告诉你是博主懒），这样你可以获得\(90pts\)。

为什么？因为我们最多要跑\(10\)次，而每次连边的时间复杂度都是\(O(n^3)\)级别的，加上要跑\(SPFA\)，很容易超时。

所以考虑一个优化，显然每次连边有很多重复的地方，因为灵敏度为\(2\)的情况肯定也把灵敏度为\(3\)的情况的所有边都连了。

所以我们不妨反过来跑，灵敏度从\(10\)到\(1\)，每次只连长度刚好为灵敏度的转向边，用栈记录一下答案就行了。

\(90pts\)：

#include <cstdio>

#include <queue>

#include <cstring>

#include <iostream>

#define Open(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);

#define Close fclose(stdin); fclose(stdout);

#define O(x) cout << #x << "=" << x << endl;

using namespace std;

const int MAXN = 10010 << 2;

const int MAXM = 5000000;

struct Edge{

    int next, to, dis;

}e[MAXM << 1];

int head[MAXN], num, dis[MAXN], vis[MAXN], a[110][110];

inline void Add(int u, int v, int dis){

    e[++num] = (Edge){ head[u], v, dis }; head[u] = num;

}

int n, m, N, l[] = { -1, 1, 0, 0 }, r[] = { 0, 0, -1, 1 }, sx, sy, px, py;

inline int id(int x, int y, int direct){

    return direct * N + (x - 1) * m + y;

}

queue <int> q;

int work(int check){

    num = 0; memset(head, 0, sizeof head);

    memset(dis, 127, sizeof dis);

    for(int i = 1; i <= n; ++i)

        for(int j = 1; j <= m; ++j){

            if(!a[i][j]) continue;

            for(int k = 0; k < 4; ++k){

                int x = i + l[k], y = j + r[k];

                if(!a[x][y]) continue;

                Add(id(i, j, k), id(x, y, k), 1);

                for(int o = 1; a[x][y]; x += l[k], y += r[k], ++o)

                    if(o >= check)

                        for(int l = 0; l < 4; ++l)

                            if(l != k)

                                Add(id(i, j, k), id(x, y, l), o);

            }

        }

    dis[id(sx, sy, 0)] = dis[id(sx, sy, 1)] = dis[id(sx, sy, 2)] = dis[id(sx, sy, 3)] = 0;

    vis[id(sx, sy, 0)] = vis[id(sx, sy, 1)] = vis[id(sx, sy, 2)] = vis[id(sx, sy, 3)] = 1;

    q.push(id(sx, sy, 0)); q.push(id(sx, sy, 1)); q.push(id(sx, sy, 2)); q.push(id(sx, sy, 3));

    while(q.size()){

        int u = q.front(); q.pop();

        vis[u] = 0;

        for(int i = head[u]; i; i = e[i].next)

            if(dis[e[i].to] > dis[u] + e[i].dis){

                dis[e[i].to] = dis[u] + e[i].dis;

                if(!vis[e[i].to]){

                    vis[e[i].to] = 1;

                    q.push(e[i].to);

                }

            }

    }

    int ans = min(min(dis[id(px, py, 0)], dis[id(px, py, 1)]), min(dis[id(px, py, 2)], dis[id(px, py, 3)]));

    if(ans < 10000000) return printf("%d %d\n", check, ans), 0;

    else return 1;

}

int main(){

    scanf("%d%d%d%d%d%d", &n, &m, &sx, &sy, &px, &py); N = n * m;

    for(int i = 1; i <= n; ++i)

        for(int j = 1; j <= m; ++j)

            scanf("%d", &a[i][j]);

    for(int i = 1; i <= 10; ++i)

        if(work(i))

            break;

    return 0;

}

\(100pts\)

#include <cstdio>

#include <queue>

#include <cstring>

#include <iostream>

#define Open(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);

#define Close fclose(stdin); fclose(stdout);

#define O(x) cout << #x << "=" << x << endl;

using namespace std;

const int MAXN = 10010 << 2;

const int MAXM = 5000000;

struct Edge{

    int next, to, dis;

}e[MAXM << 1];

int head[MAXN], num, dis[MAXN], vis[MAXN], a[110][110], s[12], top;

inline void Add(int u, int v, int dis){

    e[++num] = (Edge){ head[u], v, dis }; head[u] = num;

}

int n, m, N, l[] = { -1, 1, 0, 0 }, r[] = { 0, 0, -1, 1 }, sx, sy, px, py;

inline int id(int x, int y, int direct){

    return direct * N + (x - 1) * m + y;

}

queue <int> q;

void work(int check){

    for(int i = 1; i <= n; ++i)

        for(int j = 1; j <= m; ++j){

            if(!a[i][j]) continue;

            for(int k = 0; k < 4; ++k){

                for(int p = 1, x = i + l[k], y = j + r[k]; a[x][y]; ++p, x += l[k], y += r[k])

                    if(p == check){

                        for(int l = 0; l < 4; ++l)

                            if(l != k)

                                Add(id(i, j, k), id(x, y, l), check);

                        break;

                    }

            }

        }

    memset(dis, 127, sizeof dis);

    dis[id(sx, sy, 0)] = dis[id(sx, sy, 1)] = dis[id(sx, sy, 2)] = dis[id(sx, sy, 3)] = 0;

    vis[id(sx, sy, 0)] = vis[id(sx, sy, 1)] = vis[id(sx, sy, 2)] = vis[id(sx, sy, 3)] = 1;

    q.push(id(sx, sy, 0)); q.push(id(sx, sy, 1)); q.push(id(sx, sy, 2)); q.push(id(sx, sy, 3));

    while(q.size()){

        int u = q.front(); q.pop();

        vis[u] = 0;

        for(int i = head[u]; i; i = e[i].next)

            if(dis[e[i].to] > dis[u] + e[i].dis){

                dis[e[i].to] = dis[u] + e[i].dis;

                if(!vis[e[i].to]){

                    vis[e[i].to] = 1;

                    q.push(e[i].to);

                }

            }

    }

    int ans = min(min(dis[id(px, py, 0)], dis[id(px, py, 1)]), min(dis[id(px, py, 2)], dis[id(px, py, 3)]));

    if(ans < 10000000) s[++top] = ans;

}

int main(){

    scanf("%d%d%d%d%d%d", &n, &m, &sx, &sy, &px, &py); N = n * m;

    for(int i = 1; i <= n; ++i)

        for(int j = 1; j <= m; ++j)

            scanf("%d", &a[i][j]);

    for(int i = 1; i <= n; ++i)

        for(int j = 1; j <= m; ++j){

            if(!a[i][j]) continue;

            for(int k = 0; k < 4; ++k){

                int x = i + l[k], y = j + r[k];

                if(!a[x][y]) continue;

                Add(id(i, j, k), id(x, y, k), 1);

            }

        }

    for(int i = 10; i; --i)

        work(i);

    for(int Top = top, i = 1; i <= Top; ++i)

        printf("%d %d\n", i, s[top--]);

    return 0;

}

巴特西

【洛谷 P2226】 [HNOI2001]遥控赛车比赛（最短路）

最新文章

热门文章