以下、部屋を頂点、通路を無向辺とみなしたグラフの上で考えます。 頂点は \(1\) から \(N\) まで番号づけられており、頂点 \(i\) は部屋 \(i\) に対応しているとします。

まず、\(D=1\) の場合について考えます。この場合は例えば仮想頂点を付け加えた上で、Dijkstra 法等を用いることによって、解く事ができます。 具体的には、頂点 \(0\) を新たに付け加え、初日に感染した人の部屋との間に距離 \(0\) の辺を張ることを考えます。この時、\(1\) 日目に(新しく)感染する人は、頂点 \(0\) から距離 \(X_1\) 以内の頂点に対応する部屋に住んでいる人(のうち \(0\) 日目の夜の時点では感染していない人) となります。頂点 \(0\) から距離が \(X_1\) 以内の頂点の列挙はDijkstra 法によって行う事ができます。ここで、優先度付きキューなどで、頂点と、始点から頂点までの暫定的な最短距離の組を管理する際、暫定的な最短距離が \(X_1\) より長いならばキューに追加する必要がない事に注意してください。また、逆に、この時優先度付きキューに追加された頂点は、 \(1\) 日目の夜までに 感染している人の部屋に対応する頂点であるという事になります。

次に、\(D\) が\(2\) 以上の場合について考えます。この場合、\(i\) 日目の夜に新しく感染した人の部屋を調べた後に、\(i\) 日目に新しく感染した人の部屋と対応する頂点を頂点 \(0\) と距離 \(0\) の辺で結べば良いです。\(D=1\) の場合と比較すれば、これを用いて \((i+1)\) 日目に新しく感染した人を列挙する事ができる事がわかると思います。
しかし、これは最悪の場合計算量が \(\Theta (D(N+M)\log N)\) (あるいは \(O(D(N\log N+M))\) 等)かかってしまい、間に合いません。

ここで、各 \(i\) 日目に感染した人の部屋を求める時に用いるDijkstra 法において、最初の方で同じことを繰り返していることに注目します。すなわち、頂点 \(0\) から距離 \(0\) の頂点について、その長さを \(0\) で確定する事を毎回行っていますが、この部分には必要なく、距離 \(0\) の頂点(すなわち前の日の夜の時点ですでに感染している) への最短距離が確定した後の優先度付きキューの中身が分かれば良いです。これを持っておいて、更新していく事を考えます。これは、それぞれの日について、その日に新しく感染した人がいなければ変化はなく、いた場合はその頂点と直接辺で繋がっている頂点(のうち(始点から)距離 \(0\) でない頂点)について調べ、キューに追加すれば良いです。

この後について、このキューの中に頂点 \(0\) からの暫定的な最短距離が \(X_i\) 以下の(かつ \(0\) でない)頂点が存在しなければ、新しく感染する人はいないため変化はありません。もしあったならば、暫定距離が \(X_i\) 以下の組を元のキューから削除し、別の優先度付きキューに移す事を考えます。この優先度付きキューから初めて Dijkstra 法を始めても \(i\) 日目に新しく感染した人の住んでいる部屋に対応する頂点について得られる結果は同じです。

さて、このように行った時の計算量について考えます。 まず、\(D\) 日間にわたって更新し続ける方の優先度付きキューに要素を追加する回数を考えると、各頂点はその頂点に対応する部屋の人が感染した時についてちょうど一度だけ調べられ、さらに辺のもう一端がまだ感染していない必要がある事から高々 \(M\) 回(最初に頂点 \(0\) からの辺も追加する場合は \((K+M)\) 回)以下となります。
次に、それぞれの日についてその続きを調べるための優先度付きキューへの追加回数について考えると、\(i\) 日目の感染者について調べている時、\(D=1\) の場合に述べた事から、「優先度付きキューに追加された頂点」は、 \(i\) 日目の夜までに 感染している人の部屋に対応する頂点であり、各辺は、その辺が結んでいる頂点のうち遅い方の頂点が感染した日の夜について調べている時に全体で \(1\) 回だけ調べられます。よって、こちらのキューへの追加は \(D\) 日の間で合計 \(M\) 回となります。また、削除を伴わない参照は各日において定数回しか行われない事から、よって、全体での計算量は \(O((D+M)\log N+N)\) (\(N\) は出力時の計算量)となり、十分高速にこの問題を解く事ができました。

c++による実装例:

#include <bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define rep(i, n) for(int i = 0; i < n; ++i)

int main(void) {
	priority_queue<pii,vector<pii>,greater<pii> >pq,pq2;
	int n,m,k,d,x,y,z,sz;
	pii p;

	cin>>n>>m;
	vector<vector<pii> >e(n);
	vector<int>ans(n,-1);

	rep(i,m){
		cin>>x>>y>>z;
		e[x-1].push_back({z,y-1});
		e[y-1].push_back({z,x-1});
	}
	cin>>k;
	rep(i,k){
		cin>>x;
		x--;
		ans[x]=0;
		sz=e[x].size();
		rep(j,sz)if(ans[e[x][j].second]<0)pq.push({e[x][j].first,e[x][j].second});
	}

	cin>>d;
	rep(i,d){
		cin>>x;
		while(!pq.empty()){
			p=pq.top();
			if(p.first>x)break;
			pq.pop();
			if(ans[p.second]>=0)continue;		
            pq2.push(p);
		}

		while(!pq2.empty()){
			p=pq2.top();
			pq2.pop();
			if(ans[p.second]>=0)continue;
			y=p.second;
			ans[y]=i+1;
			sz=e[y].size();
			rep(j,sz){
				if(ans[e[y][j].second]<0){
					if((p.first+e[y][j].first)<=x)pq2.push({p.first+e[y][j].first,e[y][j].second});
					else pq.push({e[y][j].first,e[y][j].second});
				}
			}
		}
	}
	rep(i,n)cout<<ans[i]<<endl;


	return 0;
}