首先，查看答案里的大多数AC代码和几篇题解的思路是有问题的，我也是看了好久才发现这个思路是有问题的，比如数据：

3
3
1 2 100
1 3 40
2 3 50
1 2 2

路线应该是1->3->2，花费的最少时间为90，而他们那种方法的路线是直接1->2，花费了100的时间，显然是不正确的，但是也AC了，不过现在数据已加强，应该是通过不了了。

那么我们现在利用其他思路来解决一下，有两种办法。

在此之前，先分析一下题目的意思：

目标是从城市1走到城市2，城市1和2周围是有很多城市的，给你每个城市之间的距离，且这些城市隶属两个阵营，有1和2，走不同阵营的情况只可以出现一次（意思是如果你一开始走了1->2，那之后必须全部在2的阵营走。），让你求从城市1到城市2的最短距离。

不过有一点需要注意，虽然题目中说了“两个城市之间最多有一条道路”，但是不知为啥数据里还是存在重复边的，不知道是不是我理解错题意了，所以需要的时候要对重复边进行处理。

首先是第一种思路：分别求出求出城市1和城市2到其阵营中其它城市的最短路径，然后对阵营间存在的路径 i 到 j ，求dist(0, i)+D(i, j)+dist(1, j)的最小值，代码如下：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;

#define INF 0x3f3f3f3f
const int maxn = 605;
int N, M;

struct Edge {
	int a, b, t;
	Edge(int a, int b, int t):a(a), b(b), t(t) {}
};

vector<Edge> edges;  // 存储每条边
vector<int> G[maxn];  // 存储每个顶点相邻的边在edges的索引
// dist[1]存储城市1到其阵营中其他城市的最短距离，dist[2]存储城...