bzoj2346[Baltic 2011]Lamp

Description

2255是一个傻X，他连自己家灯不亮了都不知道。

某天TZ大神路过他家，发现了这一情况，

于是TZ开始行侠仗义了。

TZ发现是电路板的问题，

他打开了电路板，发现线路根本没有连上！！

于是他强大的脑力可以使某个格子上的线路从\变为/，

或者从/变为\。

2255不会电路（因为他什么都不会），但是他想知道TZ最少要用多少次脑力才能使他家的灯变亮。

如果无法变亮，输出“NO SOLUTION”。

n,m<=500

Input

Output

Sample Input

3 5

\\/\\

\\///

/\\\\

Sample Output

……我是弱渣……原来以为是各种流乱搞，结果ksy学长告诉我是最短路

如果符号是“/”左下方的点向右上方的点连边权为0的边，左上方向右下方连边权为1的边

如果符号是“\”左上方的点向右下方的点连边权为0的边，左下方向右上方连边权为1的边

然后上最短路……别忘了加双向边

25w的点Dj+堆可以秒过，但是SPFA呵呵呵……不过我有特殊的优化SPFA的方法

要用SLF优化，就是更新的时候如果当前更新的dist比正在做的dist小，就把它放在队头。具体看代码，还不会的自行百度

#include<iostream>

#include<cstdio>

#include<cstring>

#define inf 127/3

#define mod 1000007

using namespace std;

struct edge{

	int next,to,v;

}e[3000010];

int cnt;

int head[260000];

inline void ins(int u,int v,int w)

{

	e[++cnt].to=v;

	e[cnt].v=w;

	e[cnt].next=head[u];

	head[u]=cnt;

}

inline void insert(int u,int v,int w)

{

	ins(u,v,w);

	ins(v,u,w);

}

int n,m,t,w=1;

char ch;

int dist[260000];

bool flag[260000];

int q[mod];

inline void spfa()

{

	memset(dist,inf,sizeof(dist));

	int now;q[1]=1;dist[1]=0;flag[1]=1;

	while (t!=w)

	{

		t=(t+1)%mod;

		now=q[t];

		for (int i=head[now];i;i=e[i].next)

		  if (dist[now]+e[i].v<dist[e[i].to])

			{

			  dist[e[i].to]=dist[now]+e[i].v;

			  if (!flag[e[i].to])

			  {

			  	if(dist[now]>=dist[e[i].to])

			  	{

				    q[t]=e[i].to;

			  		flag[e[i].to]=1;

			  		t=(t-1+mod)%mod;

			  	}else

			  	{

			  	  w=(w+1)%mod;

			  	  q[w]=e[i].to;

			  	  flag[e[i].to]=1;

			  	}

			  }

			}

		flag[now]=0;

	}

}

int main()

{

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

	if ((n+m)&1)

	{

		printf("NO SOLUTION");

		return 0;

	}

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

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

	  {

	  	ch=' ';

	  	while (ch!='/' && ch!='\\' ) scanf("%c",&ch);

	  	if (ch=='\\')

		  {

		    insert((i-1)*(m+1)+j+1,i*(m+1)+j,1);

		    insert((i-1)*(m+1)+j,i*(m+1)+j+1,0);

		  }

	  	else if (ch=='/')

		  {

		    insert((i-1)*(m+1)+j,i*(m+1)+j+1,1);

		    insert((i-1)*(m+1)+j+1,i*(m+1)+j,0);

		  }

	  }

	spfa();

	printf("%d\n",dist[(n+1)*(m+1)]);

}

巴特西