Language: C++

#include<iostream>
#include<iomanip>
#include<map>
#include<unordered_set>
#include<set>
#include<vector>
#include<array>
#include<string>
#include<stack>
#include<queue>
#include<algorithm>
#include<cassert>
#include<functional>
#include<random>
#define int int32_t
#define REP(i, a, b) for (int32_t i = (int32_t)(a); i < (int32_t)(b); i++)
#define rep(i, a) REP(i, 0, a)
#define EACH(i, a) for (auto i: a)
#define ITR(x, a) for (auto x = a.begin(); x != a.end(); x++)
#define ALL(a) (a.begin()), (a.end())
#define HAS(a, x) (a.find(x) != a.end())
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
using namespace std;


signed main(void) {
	cin.tie(0);
	ios::sync_with_stdio(false);

	int N,M;
	cin >> N >> M;
	vector<vector<array<int, 2>>>subway(N);
	rep(i, M) {
		int p, q, c;
		cin >> p >> q >> c;
		p--; q--; c--;
		subway[p].push_back({ q,c });
		subway[q].push_back({ p,c });
	}
	//subway[i]:={町iから行ける駅、その鉄道会社}の集合
	
	typedef array<int, 3> arr;//移動コスト、現在地、現在の鉄道会社
	priority_queue<arr, vector<arr>, greater<arr>>D;
	vector<unordered_set<int, int>>cost(N);
	vector<int>min_cost(N, 99999999);
	D.push({ 0,0,1111111 });
	while (!D.empty()) {
		const auto a = D.top(); D.pop();
		const int now_cost = a[0];
		const int pos = a[1];
		const int kaisha = a[2];
		if (min_cost[pos] + 1 <= now_cost)continue;
		min_cost[pos] = min(min_cost[pos], now_cost);
		if (pos == N - 1)break;
		auto itr = cost[pos].find(kaisha);
		if (itr != cost[pos].end())continue;
		cost[pos].insert(kaisha);
		rep(i, subway[pos].size()) {
			auto next = subway[pos][i];
			const int next_kaisha = next[1];
			const int next_cost = now_cost + (next_kaisha == kaisha ? 0 : 1);
			const int next_pos = next[0];

			if (min_cost[next_pos] + 1 <= next_cost)continue;
			auto nitr = cost[next_pos].find(next_kaisha);
			if (nitr != cost[next_pos].end())continue;

			D.push({ next_cost,next_pos,next_kaisha });
		}
	}
	if (min_cost[N - 1] == 99999999)cout << -1 << endl;
	else cout << min_cost[N - 1] << endl;
}

Compiler output:
In file included from /usr/include/c++/14/bits/hashtable.h:35,
                 from /usr/include/c++/14/bits/unordered_set.h:33,
                 from /usr/include/c++/14/unordered_set:41,
                 from a.cc:4:
/usr/include/c++/14/bits/hashtable_policy.h: In instantiation of 'std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Hash, _RangeHash, _Unused, __cache_hash_code>::__hash_code std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Hash, _RangeHash, _Unused, __cache_hash_code>::_M_hash_code(const _Key&) const [with _Key = int; _Value = int; _ExtractKey = std::__detail::_Identity; _Hash = int; _RangeHash = std::__detail::_Mod_range_hashing; _Unused = std::__detail::_Default_ranged_hash; bool __cache_hash_code = true; __hash_code = long unsigned int]':
/usr/include/c++/14/bits/hashtable.h:1740:46:   required from 'std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::iterator std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::find(const key_type&) [with _Key = int; _Value = int; _Alloc = std::allocator<int>; _ExtractKey = std::__detail::_Identity; _Equal = std::equal_to<int>; _Hash = int; _RangeHash = std::__detail::_Mod_range_hashing; _Unused = std::__detail::_Default_ranged_hash; _RehashPolicy = std::__detail::_Prime_rehash_policy; _Traits = std::__detail::_Hashtable_traits<true, true, true>; iterator = std::__detail::_Insert_base<int, int, std::allocator<int>, std::__detail::_Identity, std::equal_to<int>, int, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<true, true, true> >::iterator; key_type = int]'
 1740 |       __hash_code __code = this->_M_hash_code(__k);
      |                            ~~~~~~~~~~~~~~~~~~^~~~~
/usr/include/c++/14/bits/unordered_set.h:658:25:   required from 'std::unordered_set<_Value, _Hash, _Pred, _Alloc>::iterator std::unordered_set<_Value, _Hash, _Pred, _Alloc>::find(const key_type&) [with _Value = int; _Hash = int; _Pred = std::equal_to<int>; _Alloc = std::allocator<int>; iterator = std::__detail::_Insert_base<int, int, std::allocator<int>, std::__detail::_Identity, std::equal_to<int>, int, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<true, true, true> >::iterator; key_type = int]'
  658 |       { return _M_h.find(__x); }
      |                ~~~~~~~~~^~~~~
a.cc:56:28:   required from here
   56 |                 auto itr = cost[pos].find(kaisha);
      |                            ~~~~~~~~~~~~~~^~~~~~~~
/usr/include/c++/14/bits/hashtable_policy.h:1335:23: error: static assertion failed: hash function must be invocable with an argument of key type
 1335 |         static_assert(__is_invocable<const _Hash&, const _Key&>{},
      |                       ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/hashtable_policy.h:1335:23: note: 'std::__is_invocable<const int&, const int&>()' evaluates to false
/usr/include/c++/14/bits/hashtable_policy.h:1337:25: error: expression cannot be used as a function
 1337 |         return _M_hash()(__k);
      |                ~~~~~~~~~^~~~~
/usr/include/c++/14/bits/hashtable_policy.h: In instantiation of 'std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Hash, _RangeHash, _Unused, __cache_hash_code>::__hash_code std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Hash, _RangeHash, _Unused, __cache_hash_code>::_M_hash_code_tr(const _Kt&) const [with _Kt = int; _Key = int; _Value = int; _ExtractKey = std::__detail::_Identity; _Hash = int; _RangeHash = std::__detail::_Mod_range_hashing; _Unused = std::__detail::_Default_ranged_hash; bool __cache_hash_code = true; __hash_code = long unsigned int]':
/usr/include/c++/14/bits/hashtable.h:2329:44:   required from 'std::pair<typename std::__detail::_Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::iterator, bool> std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::_M_insert_unique(_Kt&&, _Arg&&, const _NodeGenerator&) [with _Kt = const int&; _Arg = const int&; _NodeGenerator = std::__detail::_AllocNode<std::allocator<std::__detail::_Hash_node<int, true> > >; _Key = int; _Value = int; _Alloc = std::allocator<int>; _ExtractKey = std::__detail::_Identity; _Equal = std::equal_to<int>; _Hash = int; _RangeHash = std::__detail::_Mod_range_hashing; _Unused = std::__detail::_Default_ranged_hash; _RehashPolicy = std::__detail::_Prime_rehash_policy; _Traits = std::__detail::_Hashtable_traits<true, true, true>; typename std::__detail::_Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::iterator = std::__detail::_Insert_base<int, int, std::allocator<int>, std::__detail::_Identity, std::equal_to<int>, int, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<true, true, true> >::iterator; typename _Traits::__constant_iterators = std::__detail::_Hashtable_traits<true, true, true>::__constant_iterators]'
 2329 |         __hash_code __code = this->_M_hash_code_tr(__k);
      |                              ~~~~~~~~~~~~~~~~~~~~~^~~~~
/usr/include/c++/14/bits/hashtable.h:947:27:   required from 'std::pair<typename std::__detail::_Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::iterator, bool> std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::_M_insert_unique_aux(_Arg&&, const _NodeGenerator&) [with _Arg = const int&; _NodeGenerator = std::__detail::_AllocNode<std::allocator<std::__detail::_Hash_node<int, true> > >; _Key = int; _Value = int; _Alloc = std::allocator<int>; _ExtractKey = std::__detail::_Identity; _Equal = std::equal_to<int>; _Hash = int; _RangeHash = std::__detail::_Mod_range_hashing; _Unused = std::__detail::_Default_ranged_hash; _RehashPolicy = std::__detail::_Prime_rehash_policy; _Traits = std::__detail::_Hashtable_traits<true, true, true>; typename std::__detail::_Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::iterator = std::__detail::_Insert_base<int, int, std::allocator<int>, std::__detail::_Identity, std::equal_to<int>, int, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<true, true, true> >::iterator; typename _Traits::__constant_iterators = std::__detail::_Hashtable_traits<true, true, true>::__constant_iterators]'
  947 |           return _M_insert_unique(
      |                  ~~~~~~~~~~~~~~~~^
  948 |             _S_forward_key(_ExtractKey{}(std::forward<_Arg>(__arg))),
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  949 |             std::forward<_Arg>(__arg), __node_gen);
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/hashtable.h:959:31:   required from 'std::pair<typename std::__detail::_Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::iterator, bool> std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::_M_insert(_Arg&&, const _NodeGenerator&, std::true_type) [with _Arg = const int&; _NodeGenerator = std::__detail::_AllocNode<std::allocator<std::__detail::_Hash_node<int, true> > >; _Key = int; _Value = int; _Alloc = std::allocator<int>; _ExtractKey = std::__detail::_Identity; _Equal = std::equal_to<int>; _Hash = int; _RangeHash = std::__detail::_Mod_range_hashing; _Unused = std::__detail::_Default_ranged_hash; _RehashPolicy = std::__detail::_Prime_rehash_policy; _Traits = std::__detail::_Hashtable_traits<true, true, true>; typename std::__detail::_Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::iterator = std::__detail::_Insert_base<int, int, std::allocator<int>, std::__detail::_Identity, std::equal_to<int>, int, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<true, true, true> >::iterator; typename _Traits::__constant_iterators = std::__detail::_Hashtable_traits<true, true, true>::__constant_iterators; std::true_type = std::true_type]'
  959 |           return _M_insert_unique_aux(
      |                  ~~~~~~~~~~~~~~~~~~~~^
  960 |             __to_value{}(std::forward<_Arg>(__arg)), __node_gen);
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/hashtable_policy.h:958:22:   required from 'std::__detail::_Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::__ireturn_type std::__detail::_Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::insert(const value_type&) [with _Key = int; _Value = int; _Alloc = std::allocator<int>; _ExtractKey = std::__detail::_Identity; _Equal = std::equal_to<int>; _Hash = int; _RangeHash = std::__detail::_Mod_range_hashing; _Unused = std::__detail::_Default_ranged_hash; _RehashPolicy = std::__detail::_Prime_rehash_policy; _Traits = std::__detail::_Hashtable_traits<true, true, true>; __ireturn_type = std::__detail::_Insert_base<int, int, std::allocator<int>, std::__detail::_Identity, std::equal_to<int>, int, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<true, true, true> >::__ireturn_type; value_type = int]'
  958 |         return __h._M_insert(__v, __node_gen, __unique_keys{});
      |                ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/unordered_set.h:429:27:   required from 'std::pair<typename std::_Hashtable<_Value, _Value, _Alloc, std::__detail::_Identity, _Pred, _Hash, std::__detail::_Mod_range_hashing,