怎么就RE了?
查看原帖
怎么就RE了?
24056
vda96楼主2020/8/7 15:06
#include<bits/stdc++.h>
using namespace std;


typedef long long ll;
typedef pair<int, int> pii;

const int MAXH = 500 + 5, dx[] = { -1, 1, 0, 0 }, dy[] = { 0, 0, -1, 1 };
const ll inf = 0x3f3f3f3f3f3f3f3fll;

struct State { int x, y, k; };

typedef pair<ll, State> pls;

int h, w, n, A, B, C, sx, sy, gx, gy;

queue<pii> q;
ll minDis[MAXH][MAXH], dis[MAXH][MAXH][5];
priority_queue<pls, vector<pls>, greater<pls> > pq;

bool check(int x, int y) {
    return x >= 1 && x <= h && y >= 1 && y <= w;
}

bool operator<(const State &x, const State &y) {
    if (x.x == y.x && x.y == y.y)
        return x.k < y.k;
    if (x.x == y.x)
        return x.y < y.y;
    return x.x < y.x;
}

void update(const State &now, ll d) {
    if (d < dis[now.x][now.y][now.k]) {
        dis[now.x][now.y][now.k] = d;
        pq.push(pls(d, now));
    }
}

signed main() {
    scanf("%d%d%d%d%d%d", &h, &w, &A, &B, &C, &n);
    ++h, ++w;
    memset(minDis, 0x3f, sizeof(minDis));
    for (int i = 1, x, y; i <= n; ++i) {
        scanf("%d%d", &x, &y);
        ++x, ++y;
        if (i == 1) sx = x, sy = y;
        else if (i == n) gx = x, gy = y;
        q.push(make_pair(x, y)), minDis[x][y] = 0;
    }
    while (!q.empty()) {
        pii now = q.front(); q.pop();
        for (int i = 0; i < 4; ++i) {
            int nx = now.first + dx[i], ny = now.second + dy[i];
            if (minDis[nx][ny] == inf) minDis[nx][ny] = minDis[now.first][now.second] + C, q.push(make_pair(nx, ny));
        }
    }
    memset(dis, 0x3f, sizeof(dis));
    pq.push(pls(0, { sx, sy, 4 })), dis[sx][sy][4] = 0;
    while (!pq.empty()) {
        pls now = pq.top(); pq.pop(); ll d = now.first; State nowS = now.second;
        if (d > dis[nowS.x][nowS.y][nowS.k]) continue;
        if (nowS.x == gx && nowS.y == gy) {
            printf("%lld\n", d);
            return 0;
        }
        if (nowS.k == 4) {
            for (int i = 0; i < 4; ++i) {
                int nx = nowS.x + dx[i], ny = nowS.y + dy[i];
                if (check(nx, ny)) update({ nx, ny, 4 }, d + C);
                update({ nowS.x, nowS.y, i }, d + B);
            }
        } else {
            update({ nowS.x, nowS.y, 4 }, minDis[nowS.x][nowS.y] + d);
            int nx = nowS.x + dx[nowS.k], ny = nowS.y + dy[nowS.k];
            if (check(nx, ny)) update({ nx, ny, nowS.k }, d + A);
        }
    }
    return 0;
}
2020/8/7 15:06
加载中...