讨论/《美团 2021 届秋季校园招聘笔试真题》 - 十字路口/
《美团 2021 届秋季校园招聘笔试真题》 - 十字路口
共 2 个回复

smjb水数据
dij不加vis都能过
时间内存都超100%
服了

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fastio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
const int N = 105;
struct Node {
    int x, y;
    Node() {}
    Node(int _x, int _y) {x=_x;y=_y;}
    bool operator < (const Node other) const {
        return x == other.x ? (y < other.y) : (x < other.x);
    }
    int id(int n) {
        return (x - 1) * n + y;
    }
}pos[N * N];
int a[N][N], b[N][N];
Node st, ed;
int dis[N * N], vis[N * N], n, m, dx[4] = {0, 0, 1, -1}, dy[4] = {-1, 1, 0, 0};
bool check(int x, int y) {
    return x > 0 && y > 0 && x <= n && y <= m;
}
void solve() {
    cin >> n >> m;
    cin >> st.x >> st.y;
    cin >> ed.x >> ed.y;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            dis[Node(i, j).id(n)] = 1e18;
            cin >> a[i][j];
        }
    }
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            cin >> b[i][j];
        }
    }
    priority_queue<pair<int, Node> ,vector<pair<int, Node>>, greater<pair<int, Node>>>s;
    dis[st.id(n)] = 0;
    s.push({0, st});
    while(!s.empty()) {
        int disu = (s.top()).first;
        auto u = (s.top()).second;
        s.pop();
        if(vis[u.id(n)]) continue;
        vis[u.id(n)] = 1;
        if(disu != dis[u.id(n)]) continue;
        for(int i=0;i<4;i++) {
            int nowx = u.x + dx[i], nowy = u.y + dy[i];
            int con = a[u.x][u.y] + b[u.x][u.y];
            Node v(nowx, nowy);
            if(!check(nowx, nowy)) continue;
            int delta;
            if(dy[i] == 0) { // updown
                int iner_pos = disu % con;
                if(iner_pos < a[u.x][u.y]) {
                    delta = 1;
                } else {
                    delta = con - iner_pos + 1;
                }

            } else {
                int iner_pos = disu % con;
                if(iner_pos >= a[u.x][u.y]) {
                    delta = 1;
                } else {
                    delta = a[u.x][u.y] - iner_pos + 1;
                }
            }
            if(dis[v.id(n)] > disu + delta) {
                dis[v.id(n)] = disu + delta;
                if(!vis[v.id(n)])
                s.push({dis[v.id(n)], v});
            }
        }
    }
    cout << dis[ed.id(n)];
}
signed main() {
    //fastio;
    int t = 1;
    while(t--) solve();
    return 0;
}

dij模板题