首页 > 代码库 > NSOJ 鬼泣

NSOJ 鬼泣

2024-07-18 02:11:33   218人阅读

今天组队赛的一道最短路的题，给你一个矩阵，矩阵上有L,R,G,A，分别表示当你到达这个点的时候你要向左，向右，向前，向后走，如果要向别的方向走需要花费1点的魔力，正常情况下走需要花费1点的时间。问花费最小魔力的时候的最少时间是多少。 一个机智的处理方法是向别的方向走的时候的花费1*100000000，然后构图跑最短路出来的结果/100000000就是最小的魔力，％100000000就是最小的时间。

但是比赛的时候WA了好久，赛后RE了好久。终于发现一个严重的问题－－－－队列开小了。

平时最短路都是STL里的队列，这次用了手写的队列，然后手写的队列又没有弄成循环的队列，所以就跪了。写下来警醒自己：

手写队列要小心！！！！！

手写队列要小心！！！！！

手写队列要小心！！！！！

#pragma warning(disable:4996)#include <iostream>#include <cstring>#include <string>#include <vector>#include <cstdio>#include <algorithm>#include <cmath>#include <queue>#include <map>#include <ctime>using namespace std;#define maxn 120#define ll long longint n, m;int dx[4] = { 0, 1, 0, -1 };int dy[4] = { 1, 0, -1, 0 };const ll hcost = 100000000;int cd(int k, char cmd){	if (cmd == ‘G‘) return k;	else if (cmd == ‘L‘) return (k + 3) % 4;	else if (cmd == ‘R‘) return (k + 1) % 4;	else return (k + 2) % 4;}char b[maxn][maxn];struct Edge{	int v; ll w;	Edge(int vi, ll wi) :v(vi), w(wi){}	Edge(){}};vector<Edge> G[maxn*maxn * 8];int getid(int i, int j, int k){	return 4 * (i*m + j) + k;}bool in[maxn*maxn * 8];ll d[maxn*maxn * 8];bool vis[maxn*maxn * 8];void spfa(){	memset(in, 0, sizeof(in));	memset(d, 0x3f, sizeof(d));	memset(vis, 0, sizeof(vis));	in[0] = true; d[0] = 0;	queue<int> que;	que.push(0);	while (!que.empty()){		int u = que.front(); in[u] = false; que.pop();		for (int i = 0; i < G[u].size(); ++i){			int v = G[u][i].v;			ll w = G[u][i].w;			if (d[u] + w < d[v]){				d[v] = d[u] + w;				if (!in[v]) {					que.push(v);					in[v] = true;				}			}		}	}}int main(){	//freopen("C.in", "r", stdin);	//freopen("out.txt", "w", stdout);	//double t1 = clock();	while (cin >> n >> m){		for (int i = 0; i < n; ++i){			scanf("%s", b[i]);		}		for (int i = 0; i <= n*m * 6; ++i){			G[i].clear();		}		for (int i = 0; i < n; ++i){			for (int j = 0; j < m; ++j){				for (int k = 0; k < 4; ++k){					int id = getid(i, j, k);					char cmd = b[i][j];					int cord = cd(k, cmd);					int xx, yy;					for (int kk = 0; kk < 4; ++kk){						xx = i + dx[kk]; yy = j + dy[kk];						if (!(xx >= 0 && xx < n&&yy >= 0 && yy < m)) continue;						if (kk == cord) {							G[id].push_back(Edge(getid(xx, yy, kk), 1LL));						}						else{							G[id].push_back(Edge(getid(xx, yy, kk), hcost + 1));						}					}				}			}		}				spfa();		ll ans = 1e15;		for (int i = 0; i < 4; ++i){			int idd = getid(n - 1, m - 1, i);			ans = min(ans, d[idd]);		}		printf("%lld %lld\n", ans / hcost, ans%hcost);	}	//double t2 = clock();	//cout << t2 - t1 << endl;	return 0;}

 


联系
我们