yukicoder : No.2431 Viral Hotel

いまいち問題設定が理解できなかったな。
https://yukicoder.me/problems/no/2431

問題

ホテルにN個の部屋があり、M個の通路でそれらがつながっている。
各部屋には客が泊っている。
ある日、うちいくつかの部屋の客がウイルスに感染した。
以後、以下のイベントが発生する。

• i番の部屋に泊まる客は、感染後S[i]日後に、隣の部屋の客にウイルスをうつす。
• 感染後P日経った客は、免疫を得て、以後ウイルスにかからない。
• 感染後P日経つ前に再度感染した客は、退場させられる。

最終的に退場させられるのは何人か。

解法

時間経過に合わせ、愚直にシミュレートしていけばよい。

int N,K,M,P;
vector<int> E[101010];
int S[101010];
int D[101010];
int fix[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K>>M>>P;
	FOR(i,M) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	FOR(i,N) cin>>S[i];
	FOR(i,N) D[i]=1<<30;
	priority_queue<pair<int,int>> Q;
	FOR(i,K) {
		cin>>x;
		x--;
		D[x]=0;
		Q.push({-S[x],x});
	}
	MINUS(fix);
	int ret=0;
	while(Q.size()) {
		int cd=-Q.top().first;
		int cur=Q.top().second;
		Q.pop();
		if(fix[cur]!=-1&&fix[cur]<cd) continue;
		FORR(e,E[cur]) {
			if(D[e]==1<<30) {
				D[e]=cd;
				Q.push({-(cd+S[e]),e});
			}
			else if(cd<D[e]+P&&fix[e]==-1) {
				ret++;
				D[e]=-1;
				fix[e]=cd;
			}
		}
		
	}
	cout<<ret<<endl;
	
		
}

まとめ

2回感染で検疫、っていう設定が直感的にしっくりこず問題文の理解に手間取った。