这道题有这么多人发题解啊，我也来凑一凑热闹。

很明显，一个普通的BFS

    int x,y,z;
    scanf("%d%d",&n,&ge);
    for(int i=1;i<=ge;++i){
        scanf("%d%d%d",&x,&y,&z);
        a[x][y]=z+1;
    }

这一段是输入，储存他们的颜色，在这里，我将两种颜色分别用1、2表示（为了方便将没图色的用0来表示），所以颜色的地方+1。a数组存的是地图上哪里的颜色是什么样的。

    struct edge{
        int xx,yy,money,color;
        bool use;
        friend bool operator <(const edge &xxx,const edge &yyy){
            return xxx.money>yyy.money;
        }
    };

对于我这种蒟蒻来说，BFS就离不开结构体。xx、yy：表示位置，money：在这一个点用了多少钱，color：所在点颜色，use这个点的有没有放过魔法（0及没有，1及有）

结构体中最重要的就是operator重载运算符了,需注意它的用法（实测无误）

void BFS(){
    priority_queue<edge> Q;//优先队列 
    edge e;
    //第一个点初始化 
    e.xx=e.yy=1,e.money=e.use=0;
    e.color=a[1][1];
    Q.push(e);
    b[1][1]=1;
    while(!Q.empty()){
        edge t;
        t=Q.top();Q.pop();
        for(int i=0;i<4;++i){//四个方向 
            edge news;
            news.xx=t.xx+wx[i],news.yy=t.yy+wy[i];
            if(news.xx<1||news.yy<1||news.xx>n||news.yy>n||b[news.xx][news.yy])
                continue;
            news.use=!t.use;//上一格没用则这一格用，上一格用魔法则这一格不用 
            if(a[news.xx][news.yy]==0){//看一下这一个是不是没有颜色 
                //如果没有颜色 
                if(news.use)//如果这一格用魔法      
                    news.money=t.money+2,news.color=t.color,news.use=1;
                else continue;//不能用魔法，跳过。 
            }
            else{
                //有颜色 
                if(news.use)
                    news.use=0;//如果这一格要用魔法，则没必要用（反正有颜色了） 
                if(a[news.xx][news.yy]==t.color)//颜色相同不要钱 
                    news.money=t.money,news.color=a[news.xx][news.yy];
                else//不相同要钱 
                    news.money=t.money+1,news.color=a[news.xx][news.yy];
            }
            b[news.xx][news.yy]=1;//走过了不能走 
            if(news.xx==n&&news.yy==n){//到达 
                printf("%d\n",news.money);
                return;
            }
            Q.push(news);//入队 
        }
    }   
    printf("-1\n");
}

这一段代码就是核心部分，四个方向分别走，b数组存有没有到过。（其它我已p了注释，请诸位dalao自行审阅）

CODE

#include<bits/stdc++.h>
using namespace std;
#define N 105
int a[N][N],n,ge;
const int wx[5]={0,0,1,-1};
const int wy[5]={1,-1,0,0};
bool b[N][N];
struct edge{
    int xx,yy,money,color;
    bool use;
    friend bool operator <(const edge &xxx,const edge &yyy){
        return xxx.money>yyy.money;
    }
};
void BFS(){
    priority_queue<edge> Q;
    edge e;
    e.xx=e.yy=1,e.money=e.use=0;
    e.color=a[1][1];
    Q.push(e);
    b[1][1]=1;
    while(!Q.empty()){
        edge t;
        t=Q.top();Q.pop();
        for(int i=0;i<4;++i){
            edge news;
            news.xx=t.xx+wx[i],news.yy=t.yy+wy[i];
            if(news.xx<1||news.yy<1||news.xx>n||news.yy>n||b[news.xx][news.yy])
                continue;
            news.use=!t.use;
            if(a[news.xx][news.yy]==0){
                if(news.use)        
                    news.money=t.money+2,news.color=t.color,news.use=1;
                else continue;
            }
            else{
                if(news.use)
                    news.use=0;
                if(a[news.xx][news.yy]==t.color)
                    news.money=t.money,news.color=a[news.xx][news.yy];
                else
                    news.money=t.money+1,news.color=a[news.xx][news.yy];
            }
            b[news.xx][news.yy]=1;
            if(news.xx==n&&news.yy==n){
                printf("%d\n",news.money);
                return;
            }
            Q.push(news);
        }
    }   
    printf("-1\n");
}
int main(){
    int x,y,z;
    scanf("%d%d",&n,&ge);
    for(int i=1;i<=ge;++i){
        scanf("%d%d%d",&x,&y,&z);
        a[x][y]=z+1;
    }
    BFS();
    return 0;
} 

但是这样就真的可以了吗？如果你和上面的程序几乎一样，你就只有95分。

为什么？因为漏了起点是重点的情况，所以要加上一段：

    if(n==1){
        printf("0\n");
        return 0;
    }

谢谢