【bzoj2346】[Baltic 2011]Lamp 堆优化Dijkstra

题目描述

2255是一个傻X，他连自己家灯不亮了都不知道。
某天TZ大神路过他家，发现了这一情况，
于是TZ开始行侠仗义了。
TZ发现是电路板的问题，
他打开了电路板，发现线路根本没有连上！！
于是他强大的脑力可以使某个格子上的线路从\变为/，
或者从/变为\。
2255不会电路（因为他什么都不会），但是他想知道TZ最少要用多少次脑力才能使他家的灯变亮。
如果无法变亮，输出“NO SOLUTION”。

n,m<=500

样例输入

3 5
\\/\\
\\///
/\\\\

样例输出

1

---

题解

堆优化Dijkstra，刷水有益于健康

如果有解，那么若经过某条线，它的方向一定是确定的。也就是说一条线的“/”方向和“\”方向互不影响。

所以我们可以分别加这两种边，边权为是否需要改变方向，然后跑堆优化Dijkstra即可。

数组大小已实测。

#include <cstdio>

#include <cstring>

#include <queue>

#include <utility>

#define N 300010

#define pos(i , j) ((i) * (m + 1) + j + 1)

using namespace std;

typedef pair<int , int> pr;

priority_queue<pr> q;

int head[N] , to[N << 2] , len[N << 2] , next[N << 2] , cnt , dis[N] , vis[N];

char str[510];

void add(int x , int y , int z)

{

	to[++cnt] = y , len[cnt] = z , next[cnt] = head[x] , head[x] = cnt;

	to[++cnt] = x , len[cnt] = z , next[cnt] = head[y] , head[y] = cnt;

}

int main()

{

	int n , m , i , j , x;

	scanf("%d%d" , &n , &m);

	for(i = 1 ; i <= n ; i ++ )

	{

		scanf("%s" , str + 1);

		for(j = 1 ; j <= m ; j ++ )

			add(pos(i - 1 , j - 1) , pos(i , j) , str[j] == '/') , add(pos(i , j - 1) , pos(i - 1 , j) , str[j] == '\\');

	}

	memset(dis , 0x3f , sizeof(dis)) , dis[1] = 0 , q.push(pr(0 , 1));

	while(!q.empty())

	{

		x = q.top().second , q.pop();

		if(vis[x]) continue;

		vis[x] = 1;

		for(i = head[x] ; i ; i = next[i])

			if(dis[to[i]] > dis[x] + len[i])

				dis[to[i]] = dis[x] + len[i] , q.push(pr(-dis[to[i]] , to[i]));

	}

	if(dis[pos(n , m)] == 0x3f3f3f3f) puts("NO SOLUTION");

	else printf("%d\n" , dis[pos(n , m)]);

	return 0;

}