こちらもECRのボス問にしてはコードが短い。
https://codeforces.com/contest/2112/problem/F
問題
N要素の整数列Aがあったとする。
ここで、M通りの処理が行える。
各処理は整数(X[i],Y[i],Z[i])で表現され、A[X[i]]=min(A[X[i]],A[Y[i]]+Z[i])とすることを意味する。
その際、処理の順番は任意に変更できるが、各処理は1回ずつしかできないものとする。
以下のクエリに答えよ。
Aの初期値と整数Kが与えられる。
Aの要素を、合計K回までデクリメントできるとする。
その後、どんな順で処理を行っても、A[i]が同じ値のままとなるようにできるか判定せよ。
解法
N点のグラフを考え、点Y[i]→X[i]にコストZ[i]の辺を張る。また、各点vのコストの初期値をA[v]とする。
するとこのグラフにおいて、点x→yに致るパスにおいて、最短ではない経路を、最短経路にするために必要なコストのデクリメント回数がK回以下であれば条件を満たせる。
int N,M; ll E[555][555]; ll D[555][555]; ll K; int Q; ll A[555],ME[555],MD[555],op[555]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>M; FOR(x,N) FOR(y,N) E[x][y]=(x==y)?0:1LL<<40; FOR(i,M) { cin>>x>>y>>k; E[y-1][x-1]=min(E[y-1][x-1],(ll)k); } FOR(x,N) FOR(y,N) D[x][y]=E[x][y]; FOR(k,N) FOR(x,N) FOR(y,N) D[x][y]=min(D[x][y],D[x][k]+D[k][y]); cin>>Q; while(Q--) { cin>>K; FOR(i,N) { cin>>A[i]; ME[i]=MD[i]=A[i]; op[i]=1LL<<40; } FOR(x,N) FOR(y,N) { //最短路 MD[y]=min(MD[y],A[x]+D[x][y]); //最短ではないかも ME[y]=min(ME[y],A[x]+E[x][y]); } // 最短路にするために必要な操作回数 FOR(x,N) FOR(y,N) if(D[x][y]<E[x][y]) op[y]=min(op[y],A[x]+D[x][y]-(ME[y]-1)); FOR(x,N) cout<<(op[x]<=K); cout<<endl; } }
まとめ
コードは短いんだけど、この考え方は思いつかない。