まずは頂点 $1$ から頂点 $i$ への歩道であって $\mathrm{median}(p)\leq x$ が成り立つようなものが存在するか、という判定問題を考えます。

これは重みが $x$ 以下の辺のコストを $-1$ 、重みが $x$ より大きい辺のコストを $1$ としたグラフにおいて最短経路問題を解き、頂点 $i$ への最短経路長が $0$ 以下かで判定できます。

なので重みが小さいものからコストを $-1$ に変更していき、頂点 $i$ までの最短経路長がはじめて $0$ 以下になったタイミングを求めることで $\mathrm{median}(p)$ の最小値がわかります。

ここまでの考え方に基づき、最短経路問題をベルマンフォード法などで解くようにすると $O(NM^2)$ で答えが得られます。

これだと間に合わないので、最短経路長の変化に着目して計算量を小さくできないか考えましょう。

各頂点への最短経路長としてありうる値としては以下の $3$ 種類に分類できます。

• パスが存在しない（$\infty$）
• 最短経路長が存在し、最短経路は単純パス（$-N$ ~ $N$）
• 負閉路を含むパスが存在する（$-\infty$）

また、コストを変更していく中での最短経路長は明らかに単調減少します。

よって各頂点 $v$ について、頂点 $1$ から頂点 $v$ への最短経路長が変化するのは全体を通して $O(N)$ 回なので、「ある頂点 $v$ で最短経路長が更新された場合、次の頂点で最短経路長が更新されるか確認する。更新される場合のみ遷移する。」 という dfs を行うことで、最短経路長は全体を通して $O(NM+N^2)$ で更新できます。

最短経路長を更新する際は、$-N$ 以下になった場合に $-\infty$ に更新するようにすると dfs 終了後に最短経路長は正しく更新されています。

以上よりこの問題は $O(NM+N^2)$ で解けました。