\(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)\)
这题做了好久...网上其他题解似乎根本没搞充要性
原文：https://www.cnblogs.com/Grice/p/12629158.html