题意

\(n\)点\(m\)带边权图，每条边有两种权值，分别为两个不同方向的，求最短的从\(1\)开始的不经过重复边的路径长度。两点之间最多有一条边

关于两点之间最多有一条边，题目并不是这样的说的，然而较优的做法过不了可重边的情况，然后实际数据也没重，就当是没重边吧

做法一

暴力做法：钦定开始边\((1,u)\)，然后强制无法从其返回，\(O(n^2logn)\)

建虚点\(T\)，重构一下图
令\(p_u\)为\(1\)到\(u\)的最短路径第二个点的编号，\(dis_u\)为\(1\)到\(u\)的最短路径长度

边\((1,u,w)\)

对新图无影响

边\((u,1,w)\)

\(p_u\neq u\)，加入\((1,T,dis_u+w)\)
\(p_u=u\)，加入\((1,u,w)\)

边\((u,v,w)(u\neq 1,v\neq 1)\)

\(p_u=p_v\)，加入\((u,v,w)\)
\(p_u\neq p_v\)，加入\((1,v,dis_u+w)\)

正确性：
我们实际做的事就是将与\(1\)相邻的点的影响且等价到新图的最短路
一条路径若\(p_i\)均相等，其会通过\((1,T,dis_u+w)\)之间实现对答案的贡献，否则一定会通过\((1,v,dis_u+w)\)从不同点传导起到来回不一样的效果

做法二

这个做法比较普通，但在没思路的时候还是很有用的
将与\(1\)相邻的点集分成两个集合，一个集合保留出边，一个集合保留入边，然后跑最短路
但有些解是在集合内部的，然后把每个集合再分成两个集合，一直重复

每次分组的时候是所有的集合一起分完然后一起跑的
\(O(nlog^2n)\)

题外话

这题做了好久...网上其他题解似乎根本没搞充要性