We consider a graph whose vertices are the rooms and edges are the corridors. The vertices are numbered from \(1\) through \(N\), and vertex \(i\) corresponds to room \(i\).

First, we consider \(D=1\). This case can be solved by for instance adding a virtual vertex and using Dijkstra’s algorithm. Specifically, add a vertex \(0\) and connect it and each of the room of the people infected initially with an edge of length \(0\). Then, the people (newly) infected on day \(1\) are those who are living in the rooms corresponding to the vertices with distance no greater than \(X_1\) from vertex \(0\) (except for those not infected in the night of day \(0\)). One can enumerate the vertices with distance no greater than \(X_1\) from vertex \(0\) with Dijkstra’s algorithm. Here, when managing the preliminary shortest distance from the starting vertex to each vertex in a priority queue etc., note that you do not need to insert those with preliminary shortest distance greater than \(X_1\) to the queue. Conversely, those inserted to the priority queue correspond to the room of the people infected no later than the night of day \(1\).

Next, we consider the case where \(D\) is \(2\) or greater. In this case, after inspecting the rooms infected in the night of day \(i\), we can connect each of the vertices corresponding to the rooms of people newly infected in the night of day \(i\) and vertex \(0\) with an edge of length \(0\). Comparing with the case with \(D=1\), you can see that we can use them to enumerate people newly infected on day \((i+1)\).
However, the worst time complexity of this solution is \(\Theta (D(N+M)\log N)\) (or about \(O(D(N\log N+M))\)), which does not fit in the time limit.

Here, notice that during Dijkstra’s algorithm for day \(i\), the same process is repeated at the beginning. That is, the algorithm always starts with determining the shortest distance of the vertices connected to vertex \(0\) with a length-\(0\) edge to be \(0\), but this is waste of time; all that we want is the contents of the priority queue when the vertices with distance \(0\) (i.e. those already infected in the night of the last day). Consider maintaining and updating this queue. This can be achieved by, for each day, if there are any newly-infected people, inspect the vertices adjacent to those vertices (with non-zero distance (from the starting vertex)) and inserting them to the queue.

After this, if there is no vertex with preliminary shortest distance from vertex \(X_i\) no greater than \(X_i\), then no update is needed, as no one is newly infected. If there are such vertices, remove the vertices with preliminary distance \(X_i\) or less from the original queue and manage them in another queue. Even if start Dijkstra’s algorithm from this priority queue, the results obtained for the vertices corresponding to the room with people newly infected on day \(i\) remain the same.

Now, we consider the complexity of this algorithm. First we consider how many times elements are inserted to the priority queue maintained over the \(D\) days. Since each vertex is inspected exactly once when the person in the corresponding room is infected, where the other end of the edge must not be infected yet, so at most \(M\) elements are inserted (or \((K+M)\) elements if the edges from vertex \(0\) are also inserted at first).
Then we consider how many elements are inserted to the priority queue used for handovers to next days. When inspecting the infected people on the \(i\)-th day, the vertices that were inserted to the priority queue are those corresponding to the rooms of people infected no later than day \(i\); so each edge is inspected exactly once throughout the whole process, on the night when one of the vertices that it connects is infected, whichever is later. Also, the reference without infection occurs a constant number of times, so the overall complexity is \(O((D+M)\log N+N)\) (where \(N\) is required for the output), which is fast enough to solve the problem.

Sample code in 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;
}