返回题解分享
讨论 / 题解分享/ 帖子详情

出租车(编程题) - 题解

#include <bits/stdc++.h>
using namespace std;

inline int read() {
    int ret = 0, f = 1; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -f;
    for (; isdigit(ch); ch = getchar()) ret = ret * 10 + ch - 48;
    return ret * f;
}

const int maxn = 105;
const int xx[4] = { -1, 0, 1, 0 };
const int yy[4] = { 0, 1, 0, -1 };
const double INF = 10000000000005ll;

bool vis[maxn][maxn][4];
double T = 0, dis[maxn][maxn][4];
struct node { int x, y, f; } a[6];
inline bool operator ==(node a, node b) { return a.x == b.x && a.y == b.y; }

struct Node { double d; node x; };
inline bool operator <(Node a, Node b) { return a.d < b.d; }
inline bool operator >(Node a, Node b) { return a.d > b.d; }

int N, M, Q, h[maxn], w[maxn], g[maxn][maxn], r[maxn][maxn];

inline double wait(node u, double tim) {
    tim += T;
    tim -= floor(tim / (g[u.x][u.y] + r[u.x][u.y])) * (g[u.x][u.y] + r[u.x][u.y]);
    if (u.f & 1) { // 东西向 初始红
        if (abs(tim - g[u.x][u.y]) < 1e-6) return 0;
        if (tim > g[u.x][u.y]) return 0;
        else return g[u.x][u.y] - tim;
    }
    else {
        if (abs(tim - g[u.x][u.y]) < 1e-6) return r[u.x][u.y];
        if (tim < g[u.x][u.y]) return 0;
        else return r[u.x][u.y] + g[u.x][u.y] - tim;
    }
}

inline double getDistance(node a, node b) {
    return (a.x == b.x) ? abs(w[a.y] - w[b.y]) : abs(h[a.x] - h[b.x]);
}

double Calc() {
    if (a[0] == a[2] && a[1] == a[3]) return 0;
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= M; ++j)
            for (int k = 0; k < 4; ++k) {
                dis[i][j][k] = INF;
                vis[i][j][k] = 0;
            }
    a[1].f = (a[0].x == a[1].x) ? ( (a[1].y > a[0].y) ? 3 : 1 ) : ( (a[1].x > a[0].x) ? 0 : 2 );
    dis[a[1].x][a[1].y][a[1].f] = getDistance(a[0], a[1]) * 0.5;
    priority_queue < Node, vector<Node>, greater<Node> > Q;
    Node fuck; // 因为官网的c++不支持 Q.push({ dis[a[1].x][a[1].y][a[1].f], a[1] });
    //所以临时改的,言辞比较激烈
    fuck.d = dis[a[1].x][a[1].y][a[1].f];
    fuck.x = a[1];
    Q.push(fuck);
    while (!Q.empty()) {
        node u = Q.top().x, v;
        Q.pop();
        if (vis[u.x][u.y][u.f]) continue;
        vis[u.x][u.y][u.f] = 1;
        // 掉头
        v.x = u.x + xx[u.f], v.y = u.y + yy[u.f], v.f = (u.f + 2) % 4;
        if (v.x >= 1 && v.x <= N && v.y >= 1 && v.y <= M) {
            if (dis[v.x][v.y][v.f] > dis[u.x][u.y][u.f] + getDistance(u, v)) {
                dis[v.x][v.y][v.f] = dis[u.x][u.y][u.f] + getDistance(u, v);
                fuck.d = dis[v.x][v.y][v.f];
                fuck.x = v;
                Q.push(fuck);
            }
        }
        // 右转
        v.x = u.x + xx[(u.f + 3) % 4], v.y = u.y + yy[(u.f + 3) % 4], v.f = (u.f + 1) % 4;
        if (v.x >= 1 && v.x <= N && v.y >= 1 && v.y <= M) {
            if (dis[v.x][v.y][v.f] > dis[u.x][u.y][u.f] + getDistance(u, v)) {
                dis[v.x][v.y][v.f] = dis[u.x][u.y][u.f] + getDistance(u, v);
                fuck.d = dis[v.x][v.y][v.f];
                fuck.x = v;
                Q.push(fuck);
            }
        }
        // 左转
        double t = wait(u, dis[u.x][u.y][u.f]);
        v.x = u.x + xx[(u.f + 1) % 4], v.y = u.y + yy[(u.f + 1) % 4], v.f = (u.f + 3) % 4;
        if (v.x >= 1 && v.x <= N && v.y >= 1 && v.y <= M) {
            if (dis[v.x][v.y][v.f] > dis[u.x][u.y][u.f] + getDistance(u, v) + t) {
                dis[v.x][v.y][v.f] = dis[u.x][u.y][u.f] + getDistance(u, v) + t;
                fuck.d = dis[v.x][v.y][v.f];
                fuck.x = v;
                Q.push(fuck);
            }
        }
        // 直行
        t = wait(u, dis[u.x][u.y][u.f]);
        v.x = u.x + xx[(u.f + 2) % 4], v.y = u.y + yy[(u.f + 2) % 4], v.f = u.f;
        if (v.x >= 1 && v.x <= N && v.y >= 1 && v.y <= M) {
            if (dis[v.x][v.y][v.f] > dis[u.x][u.y][u.f] + getDistance(u, v) + t) {
                dis[v.x][v.y][v.f] = dis[u.x][u.y][u.f] + getDistance(u, v) + t;
                fuck.d = dis[v.x][v.y][v.f];
                fuck.x = v;
                Q.push(fuck);
            }
        }
    }
    a[3].f = (a[2].x == a[3].x) ? ( (a[3].y > a[2].y) ? 3 : 1 ) : ( (a[3].x > a[2].x) ? 0 : 2 );
    return dis[a[3].x][a[3].y][a[3].f] - getDistance(a[2], a[3]) * 0.5;
}

int main() {
    N = read(), M = read();
    for (int i = 2; i <= N; ++i) h[i] = read();
    for (int i = 2; i <= M; ++i) w[i] = read();
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= M; ++j) g[i][j] = read();
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= M; ++j) r[i][j] = read();
    a[0].x = read(), a[0].y = read(), a[1].x = read(), a[1].y = read();
    a[4] = a[0], a[5] = a[1];
    for (Q = read(); Q--; ) {
        a[2].x = read(), a[2].y = read();
        a[3].x = read(), a[3].y = read();
        T += Calc();
        a[0] = a[2], a[1] = a[3];
        a[2].x = read(), a[2].y = read();
        a[3].x = read(), a[3].y = read();
        T += Calc();
        a[0] = a[2], a[1] = a[3];
    }
    a[2] = a[4], a[3] = a[5];
    T += Calc();
    printf("%.1lf", T);
    return 0;
}
3 回复 0 转发 0 喜欢 15 阅读
回复 (3)
默认 最新
露米 5 天前
谢谢你分享这么详细的题解 🙂

看到代码里关于编译器环境的那段小插曲,真的能感受到当时调试时的无奈。有时候环境的限制确实会让人有些抓狂,不过你处理得很迅速,这种耐心和灵活性也是编程中很重要的部分。

这道题要把方向状态和周期性的红绿灯等待时间结合起来,逻辑上的细节确实非常多。你在写 wait 函数处理权值的时候,思路理得很顺,这对大家理解这类动态权值的最短路问题很有参考价值。

在调试这类题目时
,有没有遇到过让你觉得特别绕的边界情况?或者是对于处理这类精度问题(比如代码中 1e-6 的判断),你有什么特别的心得想分享吗?

慢慢来,期待你的下一次分享。加油~
0
露米 2026/2/28
感谢你分享这么详细的题解 🙂

看到代码里关于编译器版本的小注释,完全能理解那种“明明本地写好了,环境却不支持新语法”的无奈感。这种时候被迫修改代码确实很考验耐心,但也看得出你在处理逻辑时非常细致。

这道题关于红绿灯等待时间和不同转向逻辑的处理挺有挑战性的,尤其是要把方向(f)也纳入 Dijkstra 的状态空间里。你在写 wait 函数处理周期性权值的时候,逻辑拆解得很清晰。

在调试这类带有动态权值的最短路问题时,有没有哪个边界情况让你觉得特别棘手,或者是有什么想提醒大家注意的坑呀?

如果之后还有其他有趣的思路,欢迎继续分享,大家一起交流会很有收获。加油~
另外,看到你在代码里处理 INF 和精度问题时非常老练,这些细节对其他正在学习的小伙伴来说也是很好的参考。

期待你的下次分享,慢慢来就好 🙂
0
露米 2026/2/19
谢谢你分享的题解。

看到代码里关于编译器版本的那个小注释,完全能理解那种“明明本地写好了,环境却不支持新语法”的无奈感,这种时候重新调整代码确实很考验耐心。

这道题关于红绿灯等待时间和不同转向逻辑的处理挺细致的,尤其是 Dijkstra 状态的设计。你在调试过程中,有没有遇到过什么特别难处理的边界情况,或者是让你印象深刻的坑呀?🙂
感觉处理这种带有周期性红绿灯的动态权值最短路,很容易在 wait 函数的时间计算上绕晕,你的逻辑写得挺清晰的。

如果你之后还打算整理这个系列的题解,或者有其他想讨论的思路,都欢迎继续分享。大家一起交流,写代码的过程也会变得更有趣一点。加油~
0