dijkstra+堆求调
查看原帖
dijkstra+堆求调
578966
zpqzpq楼主2022/11/13 16:27
#include <cstdio>
#include <queue>

using namespace std;

const int K= 505;
const int N = K * K;
const int M = N * 10;
const int INF = 1e9 + 7;

int n;
int m;
int idx;
int elast[N];
int dis[N];

bool flag[N];

struct node
{
	int x;
	int y;
	int z;
	int next;
};
node e[M];

struct p
{
	int k;
	int dis;
};

bool operator < (p x, p y)
{
	return x.dis > y.dis;
}

int f (int x, int y)
{
	return (x - 1) * m + y;
}

void add (int u, int v, int w)
{
	idx ++;
	e[idx].x = u;
	e[idx].y = v;
	e[idx].z = w;
	e[idx].next = elast[u];
	elast[u] = idx;
}

void dijkstra (int s)
{
	for (int i = 1; i < N; i ++)
		dis[i] = INF;
	dis[s] = 0;
	
	priority_queue <p> q;
	q.push ({s, 0});
	
	while (q.size ())
	{
		int u = q.top ().k;
		q.pop ();
		
		if (flag[u] == 1)
			continue;
		flag[u] = 1;
		
		for (int i = elast[u]; i; i = e[i].next)
		{
			int v = e[i].y, w = e[i].z;
			if (dis[v] > dis[u] + w)
			{
				dis[v] = dis[u] + w;
				q.push ({v, dis[v]});
			}
		}
	}
}

int main ()
{
	scanf ("%d %d", &n, &m);
	
	if ((n + m) % 2 == 1)
	{
		puts ("NO SOLUTION");
		return 0;
	}
	
	for (int i = 1; i <= n; i ++)
	{
		scanf ("\n");
		for (int j = 1; j <= m; j ++)
		{
			char a;
			scanf ("%c", &a);
			if (a == '/')
			{
				add (f (i + 1, j), f (i, j + 1), 0);
				add (f (i, j + 1), f (i + 1, j), 0);
				add (f (i, j), f (i + 1, j + 1), 1);
				add (f (i + 1, j + 1), f (i, j), 1);
			}
			else
			{
				add (f (i + 1, j), f (i, j + 1), 1);
				add (f (i, j + 1), f (i + 1, j), 1);
				add (f (i, j), f (i + 1, j + 1), 0);
				add (f (i + 1, j + 1), f (i, j), 0);
			}
		}
	}
	
	dijkstra (1);
	
	printf ("%d\n", dis[f (n + 1, m + 1)]);
	
	return 0;
}

2022/11/13 16:27
加载中...