E - すぬけ君の地下鉄旅行 / Snuke's Subway Trip AtCoder Regular Contest 061

E: すぬけ君の地下鉄旅行 / Snuke's Subway Trip - AtCoder Regular Contest 061 | AtCoder

解法
路線別にvectorへもたせ、dfsで繋がっているもの同士を超頂点に接続する
毎回、すでに見た頂点をusedしたいが、fillするとTLEするので最後に見たtypeをもたせればいい

kmjpさんの実装を参考に
AtCoder ARC #061 : E - すぬけ君の地下鉄旅行 / Snuke's Subway Trip - kmjp's blog

Submission #3716339 - AtCoder Regular Contest 061 | AtCoder

int cur;
undigraph<> g(k6);
undigraph<> cg(k6);
vector

cedge[k6];
int did[k6];
void dfs(int v, int ty) {
if (did[v] is ty)return;
did[v] = ty;
g.add(v, cur, 1);
for (auto &&e : cg.g[v]) {
if (did[e.to] is ty)con;
dfs(e.to, ty);
}

}
signed main() {
cin >> N >> M;
cur = N + 2;
for (int i = 0; i < M; ++i) {
int f, t, c;
cin >> f >> t >> c;
cedge[c].eb(f, t);
}
fill(did, -1);
for (int c = 0; c < k6; ++c) {
if (!cedge[c].size()) con;
for (auto &&e : cedge[c]) {
cg.add(e.F, e.S, 1, c);
}
for (auto &&e : cedge[c]) {
if (did[e.F] != c) {
cur++;
dfs(e.F, c);
}
}
for (auto &&e : cedge[c]) {
cg.g[e.F].clear();
cg.g[e.S].clear();
}

}
int res = dijkstra(g, 1)[N];
if (res == -1)cout << -1 << endl;
else cout << res / 2 << endl;
return 0;
}