Codeforces #905 : Div1 B. Time Travel

Dまで解いたのにレート減か…と思ったけど今回Dまで簡単目だったのね。
https://codeforces.com/contest/1887/problem/B

問題

N点M辺の無向グラフを考える。
このグラフの辺はT種に分類される。

点1に置かれた駒を、辺に沿って動かし、点Nに動かしたい。
その際、時刻iに通過できる辺がどの種かが与えられる。
辺に沿った移動には時間が1かかる。
駒が点Nに至る最短時間を求めよ。

解法

各種類別に、無効な辺と有効な辺のグループを持って置く。
時間経過毎に、有効な辺に沿った移動を列挙し、有効な辺を削除する。
無効な辺が有効化されるのは、その端点に駒が初めて到達したとき、とすると、各辺が有効になるのは1回となり、その辺に沿った駒の移動は1回だけ考えればよくなる。

int N,T,K;
int M[202020];
set<pair<int,int>> G[202020];

vector<pair<int,int>> C[202020];

void open(int v) {
	FORR2(k,t,C[v]) G[k].insert({v,t});
	C[v].clear();
}
int dp[202020];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>T;
	FOR(i,T) {
		cin>>M[i];
		FOR(x,M[i]) {
			cin>>k>>l;
			k--,l--;
			C[k].push_back({i,l});
			C[l].push_back({i,k});
		}
	}
	FOR(i,N) dp[i]=1<<20;
	dp[0]=0;
	open(0);
	cin>>K;
	FOR(i,K) {
		int v;
		cin>>v;
		v--;
		vector<int> add;
		FORR2(a,b,G[v]) {
			if(dp[a]<1<<20&&dp[b]==1<<20) {
				dp[b]=i+1;
				add.push_back(b);
			}
			if(dp[b]<1<<20&&dp[a]==1<<20) {
				dp[a]=i+1;
				add.push_back(a);
			}
		}
		G[v].clear();
		FORR(a,add) open(a);
		if(dp[N-1]<1<<20) {
			cout<<i+1<<endl;
			return;
		}
	}
	cout<<-1<<endl;
}

まとめ

これはいろいろ解法ありそうね。