Codeforces Round 933 (Div. 3)——G. Rudolf and Subway · znzryb
## 思路讲解
[https://acm.hdu.edu.cn/contest/problem?cid=1172&pid=1005](https://acm.hdu.edu.cn/contest/problem?cid=1172&pid=1005)
这个题目的思路还是比较简单的，建虚拟点，
传送门
```cpp
while (!pq.empty()) {
auto [node,dis]=pq.front();
pq.pop_front();
if(dis>Dis[node]) continue;
Dis[node]=dis;
for(auto&v:g[node]){
if(node<=N){
if(dis+1>=Dis[v]) continue;
Dis[v]=dis+1;
pq.PB({v,dis+1});
}else{
if(dis>=Dis[v]) continue;
Dis[v]=dis;
pq.PF({v,dis});
}
}
}
```
## AC代码
[https://codeforces.com/contest/1941/submission/336750153](https://codeforces.com/contest/1941/submission/336750153)
::: 源代码
```cpp
// by Gospel_rock
// https://codeforces.com/problemset/problem/1941/G
#include <algorithm>
#include <bits/stdc++.h>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>
#define all(vec) vec.begin(),vec.end()
#define PB push_back
#define EB emplace_back
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define SZ(a) ((long long) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
#define minn(vec) *min_element(vec.begin(),vec.end())
#define maxx(vec) *max_element(vec.begin(),vec.end())
using namespace std;
#ifdef LOCAL
template<typename T> void _print(T x) { cerr << x; }
// 可以打印多层数组，但是格式不是很好
template<typename T> void _print(vector<T> v) { cerr << "[ "; for (T i : v) _print(i), cerr << " "; cerr << "]"; }
template<typename T> void _print(set<T> s) { cerr << "{ "; for (T i : s) _print(i), cerr << " "; cerr << "}"; }
template<typename T, typename U> void _print(pair<T, U> p) { cerr << "{"; _print(p.first); cerr << ", "; _print(p.second); cerr << "}"; }
template<typename T, typename U> void _print(map<T, U> m) { cerr << "{ "; for (auto &p : m) _print(p), cerr << " "; cerr << "}"; }
// 打印两层数组，格式好一些
template<typename T> void _print(vector<vector<T>> v){cerr<<"{\n";for (auto i : v) _print(i), cerr << "\n";cerr<<" }";}
#endif
using ll = long long;using ull = unsigned long long;
using ld=double;using LD=long double;
using i128 = __int128;
using pdd = pair<ld,ld>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;using vll=vector<ll>;using vb=vector<bool>;
using tll = tuple<ll,ll,ll>;using vii=vector<int>;
using vpll = vector<pll>;using vtll = vector<tll>;
using vdb = vector<ld>;using vc=vector<char>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
using CD=complex<double>;
static constexpr ll MAXN=(ll)1e6+10,INF=(ll)1e17+3; // 1e17+3是素数 1e18+9是素数
static constexpr ll mod=(ll)1e9+7; // 998244353;
static constexpr double eps=1e-8;const double pi=acos(-1.0);
ll N,M,Q,X,K,T,lT;
inline void __();
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>lT;
while(lT--)
__();
return 0;
}
/*
*/
struct odis{
ll o,dis;
// odis(ll o,ll dis):o(o),dis(dis) {}
// odis(){}
bool operator<(const odis& other)const{
return dis>other.dis;
}
};
inline void __(){
cin>>N>>M;
vector<pair<ll,ll>> li;
vector<tll> edge;
FOR(i,1,M){
ll u,v,c;
cin>>u>>v>>c;
li.EB(u,c);
li.EB(v,c);
edge.EB(u,v,c);
}
priority_queue<odis> pq;
ll st=1,ed=N;
cin>>st>>ed;
// li.EB(st,0);
sort(all(li));
li.resize(unique(all(li))-li.begin());
auto get=[&](pll a){
return lower_bound(all(li),a)-li.begin();
};
vector<vector<int> > g(SZ(li)+N+5);
for(auto&[u,v,c]:edge){
int idx=get({u,c})+N+1,idx2=get({v,c})+N+1;
g[idx].EB(idx2);
g[idx2].EB(idx);
// g[v].EB(idx);
g[u].EB(idx);
g[idx].EB(v);
// g[u].EB(idx2);
g[v].EB(idx2);
g[idx2].EB(u);
}
vll Dis(SZ(li)+N+5,INF);
// vb vis(SZ(li)+N+5);
pq.push({st,0});
while (!pq.empty()) {
auto [node,dis]=pq.top();
pq.pop();
if(Dis[node]!=INF) continue;
Dis[node]=dis;
for(auto&v:g[node]){
if(node<=N){
pq.push({v,dis+1});
}else{
pq.push({v,dis});
}
// if(v>=N+1){
// ll col=li[v-N-1].SE;
// if(col==c){
// pq.push({v,dis});
// }else{
// }
// }else{
// pq.push({v,dis});
// }
}
}
cout<<Dis[ed]<<"\n";
}
/*
AC
https://codeforces.com/contest/1941/submission/336750153
AC 不保证联通
https://vjudge.net/solution/63392276
1
4 3
1 2 1
1 3 1
4 1 1
2 3
5
6 6
1 2 1
2 3 1
5 2 2
2 4 2
4 6 2
3 6 3
1 3
6 6
1 2 1
2 3 1
5 2 2
2 4 2
4 6 2
3 6 3
1 6
6 6
1 2 1
2 3 1
5 2 2
2 4 2
4 6 2
3 6 3
6 6
4 3
1 2 1
1 3 1
4 1 1
2 3
6 7
1 2 43
1 3 34
4 6 43
6 3 43
2 3 43
5 3 43
4 5 43
1 6
1
2
0
1
1
*/
```
:::
## 心路历程（WA，TLE，MLE……）