いろはちゃんコンテスト Day1 : I - リスのお仕事

全完はできたけど大部手間取った。
https://atcoder.jp/contests/iroha2019-day1/tasks/iroha2019_day1_i

問題

N頂点M辺がある。
各辺vは色C[v]を持つものとする。

辺を辿り移動することになるが、1回の移動で、同色の辺であれば何頂点分も移動できるものとする。
1番の頂点からN番に移動する最小コストはいくつか。

解法

最初にUnion-Findで同じ色の辺でつながる頂点の集合を求めたのち、それをベースにダイクストラ法で処理した。
ちょっとオーバースペックというかもう少し簡単に書いてもよかったかな。

int N,M,K;
int A[101010],B[101010],C[101010];
vector<int> Cs[101010];

template<int um> class UF_pop {
	public:
	vector<int> par,rank; vector<vector<int>> hist;
	UF_pop() {par=rank=vector<int>(um,0); for(int i=0;i<um;i++) par[i]=i;}
	void reinit() {int i; FOR(i,um) rank[i]=0,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):operator[](par[x]);}
	void pop() {
		if(hist.size()) {
			auto a=hist.back();
			hist.pop_back();
			par[a[0]]=a[1]; rank[a[0]]=a[2];
			par[a[3]]=a[4]; rank[a[3]]=a[5];
		}
	}
	void operator()(int x,int y) {
		x=operator[](x); y=operator[](y);
		hist.push_back({x,par[x],rank[x],y,par[y],rank[y]});
		if(x==y) return;
		if(rank[x]<rank[y]) par[x]=y;
		else rank[x]+=(rank[x]==rank[y]), par[y]=x;
	}
};
UF_pop<101010> uf;
int dist[101010];

set<int> cand[101010];

vector<int> V[202020];

vector<int> D[202020];
int did[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>K;
	FOR(i,M) {
		cin>>A[i]>>B[i]>>C[i];
		A[i]--;
		B[i]--;
		C[i]--;
		Cs[C[i]].push_back(i);
	}
	int id=0;
	FOR(i,101010) if(Cs[i].size()) {
		FORR(c,Cs[i]) {
			uf(A[c],B[c]);
		}
		FORR(c,Cs[i]) {
			if(did[A[c]]==0) {
				did[A[c]]=1;
				D[uf[A[c]]].push_back(A[c]);
			}
			if(did[B[c]]==0) {
				did[B[c]]=1;
				D[uf[B[c]]].push_back(B[c]);
			}
		}
		FORR(c,Cs[i]) {
			did[A[c]]=did[B[c]]=0;
			if(D[A[c]].size()) {
				swap(V[id],D[A[c]]);
				FORR(v,V[id]) cand[v].insert(id);
				id++;
			}
			if(D[B[c]].size()) {
				swap(V[id],D[B[c]]);
				FORR(v,V[id]) cand[v].insert(id);
				id++;
			}
			uf.pop();
		}
	}
	
	
	queue<int> Q;
	FOR(i,N) dist[i]=202020;
	dist[0]=0;
	Q.push(0);
	while(Q.size()) {
		int cur=Q.front();
		Q.pop();
		FORR(c,cand[cur]) {
			FORR(v,V[c]) if(v!=cur) {
				if(dist[v]>dist[cur]+1) {
					dist[v]=dist[cur]+1;
					Q.push(v);
				}
				cand[v].erase(c);
			}
		}
		cand[cur].clear();
	}
	
	if(dist[N-1]==202020) cout<<-1<<endl;
	else cout<<dist[N-1]*K<<endl;
}

まとめ

今回ポイントは概ね普段のARCと同じぐらいの基準だったみたいね。