乘坐地铁
考虑利用拆点的思维。
对于每个点，拆成若干个点 \((v,i)\)，\(i\) 为与其有关的边的地铁公司的编号。
然后对于每个点建立超级点，从普通点到超级点连 \(0\)，反过来连 \(1\)，（编号相同）这样就是相当于切换一次线路，然后原来的边保留下来，由于已经切换过线路，所以边权为 \(0\)。
然后从起点对应的超级点开始，到达终点对应的超级点。
乘坐地铁
发布时间 2023-08-30 20:14:04作者: wscqwq
考虑利用拆点的思维。
对于每个点，拆成若干个点 \((v,i)\)，\(i\) 为与其有关的边的地铁公司的编号。
然后对于每个点建立超级点，从普通点到超级点连 \(0\)，反过来连 \(1\)，（编号相同）这样就是相当于切换一次线路，然后原来的边保留下来，由于已经切换过线路，所以边权为 \(0\)。
然后从起点对应的超级点开始，到达终点对应的超级点。