求助,2分,除一个点 AC 外其余的全 RE
查看原帖
求助,2分,除一个点 AC 外其余的全 RE
112917
Eason_AC楼主2020/11/6 11:38

Rt,实在是调不出来了/kk

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#define ll long long
#define F(i, a, b) for(int (i) = (a); (i) <= (b); ++(i))
#define R(i, a, b) for(int (i) = (a); (i) >= (b); --(i))
using namespace std;

inline int getint() {
	int f = 1, x = 0; char c = getchar();
	while(!isdigit(c)) {if(c == '-') f = -1; c = getchar();}
	while(isdigit(c)) {x = x * 10 + c - '0'; c = getchar();}
	return x * f;
}
inline ll getll() {
	ll f = 1, x = 0; char c = getchar();
	while(!isdigit(c)) {if(c == '-') f = -1; c = getchar();}
	while(isdigit(c)) {x = x * 10 + c - '0'; c = getchar();}
	return x * f;
}
inline void writeint(int& x) {
	if(!x) {putchar('0'); return;}
	if(x < 0) putchar('-');
	int tmp = x < 0 ? -x : x, digit[17] = {0};
	while(tmp) {digit[++digit[0]] = tmp % 10; tmp /= 10;}
	R(i, digit[0], 1) putchar(digit[i] + '0');
}
inline void writell(ll& x) {
	if(!x) {putchar('0'); return;}
	if(x < 0) putchar('-');
	ll tmp = x < 0 ? -x : x; int digit[27] = {0};
	while(tmp) {digit[++digit[0]] = tmp % 10; tmp /= 10;}
	R(i, digit[0], 1) putchar(digit[i] + '0');
}
#define Rint getint()
#define Rll getll()

const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, 1, -1};
int h, w, a, b, c, n, cnt, H[8000007], s[100007], t[100007], vis[507][507], vis_dj[8000007];
ll dis[8000007], minx[507][507];
struct edge {
	ll v;
	int to, nxt;
}e[8000007];
struct node {
	int x, y;
};
#define num(x, y) ((x) * (w + 1) + y)

inline void a_e(int u, int v, ll w) {e[++cnt] = (edge){w, v, H[u]}; H[u] = cnt;}
inline int inrange(int x, int y) {return x >= 0 && x <= h && y >= 0 && y <= w;}
inline void bfs() {
	queue<node> q;
	memset(minx, 0x3f3f, sizeof(minx));
	F(i, 1, n) {minx[s[i]][t[i]] = 0; q.push((node){s[i], t[i]});}
	while(q.size()) {
		node dd = q.front(); q.pop();
		vis[dd.x][dd.y] = 0;
		F(i, 0, 3) {
			int xx = dd.x + dx[i], yy = dd.y + dy[i];
			if(!inrange(xx, yy)) continue;
			if(minx[xx][yy] > minx[dd.x][dd.y] + 1) {
				minx[xx][yy] = minx[dd.x][dd.y] + 1;
				if(!vis[xx][yy]) {
					q.push((node){xx, yy});
					vis[xx][yy] = 1;
				}
			}
		}
	}
}
inline void buildGraph() {
	int sq = (h + 1) * (w + 1);
	F(i, 0, h) F(j, 0, w) {
		int id = num(i, j);
		F(k, 0, 3) {
			a_e(id + sq * k, id + sq * 4, 0);
			a_e(id + sq * 4, id + sq * 5, 1ll * c * minx[i][j]);
			a_e(id + sq * 5, id * sq * k, b);
			int xx = i + dx[k], yy = j + dy[k];
			if(!inrange(xx, yy)) continue;
			int id2 = num(xx, yy);
			a_e(id + sq * k, id2 + sq * k, a);
			a_e(id + sq * 5, id2 + sq * 5, c);
		}
	}
}
inline void dj() {
	priority_queue<pair<ll, int> > q;
	memset(dis, 0x3f3f, sizeof(dis));
	int sq = (h + 1) * (w + 1);
	dis[num(s[1], t[1]) + 4 * sq] = 0; q.push(make_pair(0, num(s[1], t[1]) + 4 * sq));
	while(q.size()) {
		int x = q.top().second; q.pop();
		if(vis_dj[x]) continue;
		vis_dj[x] = 1;
		for(int i = H[x]; i; i = e[i].nxt) {
			int y = e[i].to;
			ll z = e[i].v;
			if(dis[y] > dis[x] + z) {
				dis[y] = dis[x] + z;
				q.push(make_pair(-dis[y], y));
			}
		}
	}
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("soccer.in", "r", stdin);
	freopen("soccer.out", "w", stdout);
#endif
	h = Rint, w = Rint, a = Rint, b = Rint, c = Rint, n = Rint;
	F(i, 1, n) s[i] = Rint, t[i] = Rint;
	bfs(), buildGraph(), dj();
	ll ans = 0x3f3f3f3f3f3f3ff;
	F(i, 0, 5) ans = min(ans, dis[num(s[n], t[n]) + i * (h + 1) * (w + 1)]);
	writell(ans);
	return 0;
}

2020/11/6 11:38
加载中...