この問題は俗に頂点倍化と呼ばれるテクニックを用いて解くことができます。

与えられたグラフを \(G\) とし、次のグラフ \(G'\) を考えます。

• \(G'\) は \((1,0),(1,1),\dots,(1,1023), (2,0),(2,1),\ldots,(N,1023)\) を頂点とする\(1024N\) 頂点のグラフ
• \(G\) において頂点 \(x\) から頂点 \(y\) への重み \(w\) の有向辺があるときかつそのときに限り、\(G'\) において頂点 \((x,s)\) から頂点 \((y,s\ \mathrm{XOR}\ w)\) への有向辺がある。

\(G'\) において頂点 \((1,0)\) から始めて頂点 \((x,s)\) に到達できることは、\(G\) において頂点 \(1\) から頂点 \(x\) への重み \(s\) の walk があることと同値です。

よってグラフ \(G'\) において頂点 \((1,0)\) から各頂点 \((N,0),(N,1),\ldots,(N,1023)\) へ到達可能であるかどうかを判定すればよく、グラフ \(G'\) は \(1024N\) 頂点 \(1024M\) 辺であることから、実際にグラフを構築してBFSやDFSなどを行うことで \(O((N+M)\max W_i)\) 時間でこの問題が解けます。