略解です。

この問題には、各辺を \(1\) 度だけ更新に使う解法と \(2\) 度更新に使う解法があります。

辺を 1 度だけ更新に使う解法

「両端の頂点のうち一方の頂点のみが昨日までにウイルスに感染している辺」を長さの昇順に取り出せるような優先度付きキュー \(Q\) を用意しておきます。これにより、それぞれの日に「昨日までにウイルスに感染している頂点から、今日直接感染する頂点」を列挙することができます。こうして列挙した頂点からダイクストラ法の要領で、「今日ウイルスに感染した頂点からさらに感染する頂点」を順に求めることができます。この過程で、「今日はウイルスが伝わらなかった辺」を \(Q\) に追加します。

各辺は全体で、新規感染者の列挙とダイクストラ法の過程で合わせて高々 \(2\) 度チェックされ、\(1\) 度だけ更新に使われるため、計算量は全体で \(O(D+N+M\log N)\) となります。

実装例(C++)

辺を 2 度更新に使う解法

この問題を「各頂点 \(v\) に対し、昨日までの感染者からの最短距離 \(\mathrm{dist}[v]\) を求める」という問題だと思います。ナイーブな(多点スタート)ダイクストラを \(D\) 回行うのでは間に合わないので高速化を考えます。この \(D\) 回のダイクストラは「昨日の時点での \(\mathrm{dist}[v]\) が確定したあと、今日はいくつかの頂点の \(\mathrm{dist}[v]\) を \(0\) に変更して再度ダイクストラを行う」となっていることに注目します。

ここで、「その日はもう感染しない」ことがわかった頂点たちについては、そこから先はdistを確定させず、優先度付きキューの中に保留させておくことにすると、「確定済みの頂点の距離を変更する」という操作は各頂点に対して高々 \(1\) 度しか行われません。よって、各辺は全体で高々 \(2\) 度更新に使われるため、計算量は全体で \(O(D+N+M\log N)\) となります。

実装例(C++)