Code : Rudolf and Subway

#include <bits/stdc++.h>
using namespace std;

const int inf = 1e6;

class Graph {
  public:
    int n;
    vector<vector<pair<int, int>>> adj;
    Graph(int n) {
        this->n = n;
        adj.resize(n);
    }

    int dijkstra(int src, int target) {
        map<pair<int, int>, int> d;
        set<pair<int, pair<int, int>>> heap;
        d[{src, -1}] = 0;
        heap.insert({0, {src, -1}});

        while (!heap.empty()) {
            auto u = heap.begin()->second;
            heap.erase(heap.begin());

            for (auto &v : adj[u.first]) {
                if (d.find(v) == d.end()) {
                    d[v] = inf;
                    heap.insert({d[v], v});
                }

                int nxt = d[u] + (u.second != v.second);
                if (d[v] > nxt) {
                    heap.erase({d[v], v});
                    d[v] = nxt;
                    heap.insert({d[v], v});
                }
            }
        }

        int ans = inf;
        for (auto &kv : d) {
            if (kv.first.first == target) {
                ans = min(ans, kv.second);
            }
        }
        return ans;
    }
};

void solve() {
    int n, m;
    cin >> n >> m;
    Graph g(n);

    for (int i = 0; i < m; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        u--;
        v--;
        g.adj[u].push_back({v, c});
        g.adj[v].push_back({u, c});
    }
    int src, target;
    cin >> src >> target;
    src--;
    target--;
    cout << g.dijkstra(src, target) << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        solve();
    }
}