0-1BFS可以在O(E+V)求出边权只有0/1的最短路。

维护一个双端队列，如当前可以进行松弛那么就进行更新，更新完后判断一下，若边权为1，则在队尾加入下一个点，否则在队首加入下一个点。松弛操作有点类似于dijkstra…

由于松弛操作的存在，0-1BFS可以去掉vis数组，而且速度会更快。

SPOJ - KATHTHI

题意：

给出一个n×m的网格，每个位置有一个小写字母，初始在(1,1)，每次可以向上下左右走，问走到(n,m)的最小花费。若当前位置与下一位置的字符相同，则移动花费为0，否则为1。

代码：

int m,n;
struct node
{
    int x,y,c;
};
char mp[1010][1010];
int dis[1010][1010];
int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};
void onezerobfs()
{
    deque<node>q;
    dis[0][0]=0;
    q.push_back(node{0,0,0});
    while(!q.empty())
    {
        node temp=q.front();
        q.pop_front();
        for(int i=0;i<4;i++)
        {
            int xx=temp.x+dx[i],yy=temp.y+dy[i];
            if(xx>=0&&xx<m&&yy>=0&&yy<n)
            {
                int cost=mp[temp.x][temp.y]==mp[xx][yy]?0:1;
                if(dis[temp.x][temp.y]+cost<dis[xx][yy])
                {
                    dis[xx][yy]=dis[temp.x][temp.y]+cost;
                    if(cost==1)q.push_back(node{xx,yy,dis[xx][yy]});
                    else q.push_front(node{xx,yy,dis[xx][yy]});
                }
            }
        }
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        memset(dis,0x7f,sizeof(dis));
        scanf("%d%d",&m,&n);
        for(int i=0;i<m;i++)
            scanf("%s",mp[i]);
        onezerobfs();
        printf("%d\n",dis[m-1][n-1]);
    }
    return 0;
}