元の問題はグラフに帰着して解くことができます。以後、グラフ理論の言葉を使います。

辺数ができる限り少なくなるように構築した後、 \(M\) に足りない分の辺は \(10^9\) のコストにすることで条件を満たせます。

次のように場合分けをします。

\(M < N-1\) または \(\cfrac{N(N-1)}{2} < M\) である場合

単純で連結なグラフにすることはできないため、答えは No です。

\(D_1 = D_N = \min(D)\) でない場合

頂点 \(1, N\) は必ず通るため、 \(1\) 日目と \(N\) 日目は共にこのグラフの \(1\) から \(N\) への最短路を通る必要があり、答えは No です。

\(D\) の全ての要素の偶奇が等しい場合

次のように構築することで辺数 \(N-1\) を達成できます。

• 頂点 \(1\) と頂点 \(N\) の間にコスト \(D_1\) の辺をはる
• \(2 \leq i \leq N-1\) のそれぞれについて、頂点 \(1\) と頂点 \(i\) の間にコスト \(\cfrac{D_i-D_1}2\) の辺をはる

\(D_1\) と偶奇が異なる要素が \(D\) にある場合

\(D_1 = 0\) の場合

\(v\) は \(D_1 \not\equiv D_v \pmod 2\) を満たすものの \(1\) つとします。 \(D_1=0\) より、 \(D_v\) は奇数です。頂点 \(1\) から頂点 \(v\) へ移動する最小コストが \(c\) である時、頂点 \(1\) から頂点 \(v\) を通り頂点 \(N\) に移動する最小コストは \(2c\) であることが分かります。しかしこれは、 \(D_v\) が奇数であることと矛盾しています。よって、答えは No です。

\(D_1 \neq 0 \) の場合

辺数 \(N-1\) が達成不可能なことは明らかです。 また、次のように構築することで辺数 \(N\) を達成できます。

• \(v\) を \(D_1 \not\equiv D_v \pmod 2\) を満たすもののうち \(D_v\) が最小のものとする

• 頂点 \(1\) と頂点 \(N\) の間にコスト \(D_1\) の辺をはる

• 頂点 \(1\) と頂点 \(v\) の間にコスト \(\left \lfloor \cfrac{D_v}{2} \right \rfloor\) の辺をはる

• 頂点 \(v\) と頂点 \(N\) の間にコスト \(\left \lceil \cfrac{D_v}{2} \right \rceil\) の辺をはる

• \(2 \leq i \leq N-1, i \neq v\) を満たす \(i\) それぞれについて、

  \(D_1 \equiv D_i \pmod 2\) の場合

  頂点 \(1\) と頂点 \(i\) の間にコスト \(\cfrac{D_i - D_1}{2}\) の辺をはる

  \(D_1 \not \equiv D_i \pmod 2\) の場合

  頂点 \(v\) と頂点 \(i\) の間にコスト \(\cfrac{D_i - D_v}{2}\) の辺をはる

これらの構築方法が正しいことの証明は容易です。

実装例 (C++, 221ms)