Codeforces #584 F. Koala and Notebook

これは思いつけて良かった。
https://codeforces.com/contest/1209/problem/F

問題

N頂点の連結グラフが与えられる。
M本の各辺には1～Mの番号が振られている。
頂点1から各頂点に移動する経路のうち、経由した辺の番号をスペースなく並べた数値が最小となるようにしたい。
それぞれの点に到達したときの数値をmod 10^9+7で答えよ。

解法

各辺の数値が1桁なら、BFSを行っていけば条件を満たす到達経路がわかる。
なので、辺を分割しよう。例えば1234番の辺が頂点UとVを結んでいたら、間に3つの頂点を追加し、1,2,3,4の番号を持つ4つの辺にしてしまえばよい。

int N,M;
int C[101010];
vector<int> E[1001010][10];
int D[1001010];
ll R[1001010];
ll mo=1000000007;
int nex;
ll p10[10];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	p10[0]=1;
	FOR(i,9) p10[i+1]=p10[i]*10;
	
	cin>>N>>M;
	nex=N+1;
	for(i=1;i<=M;i++) {
		cin>>x>>y;
		
		int step=1;
		while(p10[step]<=i) step++;
		vector<int> V;
		V.push_back(x);
		FOR(j,step-1) V.push_back(nex++);
		V.push_back(y);
		FOR(j,step) {
			E[V[j]][i/p10[step-1-j]%10].push_back(V[j+1]);
			E[V[step-j]][i/p10[step-1-j]%10].push_back(V[step-j-1]);
		}
	}
	
	FOR(i,nex+1) D[i]=1<<30;
	D[1]=0;
	queue<vector<int>> Q;
	Q.push({1});
	while(Q.size()) {
		queue<vector<int>> NQ;
		while(Q.size()) {
			vector<int> V=Q.front();
			Q.pop();
			
			FOR(i,10) {
				vector<int> nex;
				FORR(v,V) {
					FORR(e,E[v][i]) if(D[e]>D[v]+1) {
						D[e]=D[v]+1;
						R[e]=(R[v]*10+i)%mo;
						nex.push_back(e);
					}
				}
				if(nex.size()) NQ.push(nex);
			}
			
		}
		
		swap(NQ,Q);
	}
	
	for(i=2;i<=N;i++) cout<<R[i]<<endl;
	
	
}

まとめ

これなぜか本番systestで落としてた。