关于本题或许正确的做法

RT。

注意：仅是讨论而不是讨论区题解。

借用 CF1163F Indecisive Taxi Fee 的做法，由于本题转化为无向图，从 $n$ 向 $1$ 求 $suf$ 时使用原图的反图（即 $u \rightarrow v$ 的边转化为 $v \rightarrow u$ 的边。

在线段树维护 $\min$ 时由于边是单向边，只能加入 $u\rightarrow v$ 的贡献，即对原链上 $(L_u \sim R_u]$ 的点与 $\text{dis}(1,u)+w+\text{dis}(v,n)$ 取 $\min$。

统计答案时特判无解即可。

然而这样做无法通过下面的数据：

4 7 2
1 2 1
2 4 1
2 3 1
3 1 1
4 2 1
1 3 100
3 4 100
1 2

答案为

200
102

而输出为

-1
102

考虑为什么会判为无解。

尝试去掉边 $3 \ 1 \ 1$，发现答案正确。

通过遍历中间值发现在求解 $R_3$ 时出错，原因在于在反图上跑 $\text{dijkstra}$ 时 $n$ 更新了 $1$ 后，$1$ 通过边 $1\ 3\ 1$ 更新了 $3$，导致 $3$ 的 $R$ 计算错误。

而这就直接导致在更新 $1\ 3\ 100$ 的贡献时什么都没有更新。考虑在原图上产生了什么影响。

事实上，我们更新 $R$ 的意义是在不经过某些边的情况下辅助求解最短路，然而在更新 $R_3$ 的时候 $n$ 却提前到达了 $1$。

在下面我的代码中，在 $\text{dijkstra}$ 中从 $\text{dis}_x$ 更新到 $\text{dis}_v$ 后若 $v$ 已经到达终点，强制 $v$ 不能进行下一步的转移。

欢迎 hack。