BZOJ 2346 Lamp

题目大意

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

某天TZ大神路过他家，发现了这一情况，于是TZ开始行侠仗义了。

TZ发现是电路板的问题，他打开了电路板，发现线路根本没有连上！！

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

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

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

这道题经过思考之后发现就是各种更改方向，所以可以将不更改的状态连一次边长度=0，将更改之后的状态连边长度=1，跑一遍最短路就可以出解了。

注意这里二维点转化为一维可以使用一个通用的公式，往里推之后就可以保证唯一性了，使用一个函数解决。

第一次使用堆优化Dijkstra.

#include <queue>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxN=300010;
int cnt,n,m,dis[maxN],to[maxN<<2],head[maxN<<2],len[maxN<<2],nex[maxN<<2];
char ins[510];
bool vis[maxN];
int pos(int tx,int ty)
{
    return tx*(m+1)+ty+1;
}
void addedge(int tx,int ty,int tz)
{
    to[++cnt]=ty,len[cnt]=tz,nex[cnt]=head[tx],head[tx]=cnt;
    to[++cnt]=tx,len[cnt]=tz,nex[cnt]=head[ty],head[ty]=cnt;
}
void dijkstra()
{
    priority_queue<pair<int,int> >q;
    memset(dis,0x3f,sizeof dis);
    dis[1]=0;
    q.push(make_pair(0,1));
    while(!q.empty())
    {
        int tmp=q.top().second;
        q.pop();
        if(vis[tmp]) continue;
        vis[tmp]=true;
        for(int i=head[tmp];i;i=nex[i])
            if(dis[to[i]]>dis[tmp]+len[i])
            {
                dis[to[i]]=dis[tmp]+len[i];
                q.push(make_pair(-dis[to[i]],to[i]));
            }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
    {
        scanf("%s",ins+1);
        for(int j=1;j<=m;++j) addedge(pos(i,j),pos(i-1,j-1),ins[j]!='\\'),addedge(pos(i,j-1),pos(i-1,j),ins[j]!='/');
    }
    dijkstra();
    //for(int i=1;i<=20;++i) printf("%d\n",dis[i]);
    if(dis[pos(n,m)]==0x3f3f3f3f) printf("NO SOLUTION");
    else printf("%d",dis[pos(n,m)]);
    return 0;
}