题意：

有n个点，有m条边，每条边上有一个权值。当你从u到v时，如果这条边和上一条边的权值不同，代价就加1。问从结点1到结点n的最小代价。

思路：

有两种做法。

做法一（拆点）：

原来的图是左边这样的，可以拆成右边这样，可以知道这样任意两点之间的代价就是走过的权值和加上1。

为了方便存图，可以这样拆点：

这样子的代价也是相同的。

跑一下最短路/2就可以了。

做法二（并查集）：

把权值相同的边拿出来，如果在同一个连通块内的话，互相到达肯定是不要代价的，但是如果不在同一个连通块内，互相到达仍然是要钱的，所以把每个点和它的父结点连边，把这个父节点当成一个新的结点。然后bfs一下就可以了。

如数据：

6 7

5 4 7

4 2 5

4 3 4

6 3 7

3 1 1

2 6 5

5 2 5

建图是这样的：

代码：

做法一：

int cnt;
typedef pair<int,int>p;
map<p,int>mp;
struct edge
{
    int to,cost;
};
vector<edge>v[100010*10];
int getid(int x,int y)
{
    p pp=make_pair(x,y);
    if(mp.count(pp))return mp[pp];
    mp[pp]=++cnt;
    return cnt;
}
int dis[100010*10];
void dijkstra()
{
    fill(dis+1,dis+cnt+1,INF);
    dis[1]=0;
    priority_queue<p,vector<p>,greater<p> >q;
    q.push(p(0,1));
    while(!q.empty())
    {
        p temp=q.top();
        q.pop();
        int w=temp.first;int id=temp.second;
        if(w>dis[id])continue;
        for(int i=0;i<v[id].size();i++)
        {
            edge &e=v[id][i];
            if(w+e.cost<dis[e.to])
            {
                dis[e.to]=w+e.cost;
                q.push(p(dis[e.to],e.to));
            }
        }
    }
}
int main()
{
    int n,m,x,y,z;
    scanf("%d%d",&n,&m);
    cnt=n;
    while(m--)
    {
        scanf("%d%d%d",&x,&y,&z);
        int temp1,temp2;
        temp1=getid(x,z);temp2=getid(y,z);
        v[x].push_back(edge{temp1,1});
        v[temp1].push_back(edge{x,1});
        v[temp1].push_back(edge{temp2,0});
        v[temp2].push_back(edge{temp1,0});
        v[temp2].push_back(edge{y,1});
        v[y].push_back(edge{temp2,1});
    }
    dijkstra();
    if(dis[n]==INF)printf("-1\n");
    else printf("%d\n",dis[n]/2);
    return 0;
}

做法二（需update）：

typedef pair<int,int> p;
int n;
int tot;
int par[MAXN];
int id[MAXN];
bool used[MAXN];
vector<p>c[MAXN];
vector<int>v[MAXN];
struct node
{
    int idd,step;
};
int Find(int x)
{
    if(par[x]==x)return x;
    return par[x]=Find(par[x]);
}
void unite(int x,int y)
{
    x=Find(x);y=Find(y);
    par[x]=y;
}
int main()
{
    int m,x,y,z;
    int MAX=0;
    scanf("%d%d",&n,&m);
    while(m--)
    {
        scanf("%d%d%d",&x,&y,&z);
        c[z].push_back(make_pair(x,y));
        MAX=max(MAX,z);
    }
    tot=n;
    for(int i=1;i<=MAX;i++)
    {
        int len=c[i].size();
        for(int j=0;j<len;j++)
        {
            x=c[i][j].first,y=c[i][j].second;
            par[x]=x;par[y]=y;
            id[x]=id[y]=0;used[x]=used[y]=false;
        }
        for(int j=0;j<len;j++)
            unite(c[i][j].first,c[i][j].second);
        for(int j=0;j<len;j++)
        {
            x=c[i][j].first,y=c[i][j].second;
            int fx=Find(x),fy=Find(y);
            if(id[fx]==0)id[fx]=++tot;
            if(id[fy]==0)id[fy]=++tot;
            if(!used[x])
            {
                used[x]=true;
                v[x].push_back(id[fx]);
                v[id[fx]].push_back(x);
            }
            if(!used[y])
            {
                used[y]=true;
                v[y].push_back(id[fy]);
                v[id[fy]].push_back(y);
            }
        }
    }
    memset(used,0,sizeof(used));
    int ans=-2;
    queue<node>q;
    q.push(node{1,0});
    used[1]=true;
    int sign=0;
    while(!q.empty()&&sign==0)
    {
        node temp=q.front();
        q.pop();
        x=temp.idd;y=temp.step;
        int len=v[x].size();
        for(int i=0;i<len&&sign==0;i++)
        {
            if(!used[v[x][i]])
            {
                if(v[x][i]==n)
                {
                    ans=y+1;
                    sign++;
                }
                used[v[x][i]]=true;
                q.push(node{v[x][i],y+1});
            }
        }
    }
    printf("%d\n",ans/2);
    return 0;
}