G. Rudolf and Subway

 原题的无向图等价于上图所示的联通图，此时我们要求的就是起始位置到终止位置最少要经过几个有颜色的结点。

code

#include<bits/stdc++.h>
using namespace std;
const int N=4e5+5;
int vis[N];
int main(){
//    freopen("input.txt","r",stdin);
    int t;
    cin>>t;
    while (t--){
        int n,m;
        cin>>n>>m;
        map<int,vector<int> > G;
        for (int i=1;i<=m;i++){
            int u,v,c;
            cin>>u>>v>>c;
            c+=n;
            vis[u]=-1;
            vis[v]=-1;
            vis[c]=-1;
            G[u].push_back(c);
            G[v].push_back(c);
            G[c].push_back(u);
            G[c].push_back(v);
        }
        queue<int> que;
        int b,e;
        cin>>b>>e;
        if (b==e) {
            cout<<0<<endl;
            continue;
        }
        vis[b]=0;
        que.push(b);
        while (!que.empty()){
            int x=que.front();
            que.pop();
            if (x==e) break;
            for (auto Next : G[x]){
                if (vis[Next]==-1){
                    vis[Next]=vis[x]+1;
                    que.push(Next);
                }
            }
        }
        cout<<vis[e]/2<<endl;
    }
    return 0;
}