思路

旅游景点之间的链接是无向图，先通过邻接矩阵存储地图，然后检查给出的各个路径是否连通，如果连通则计算代价并更新最小代价。 两点直接拿可能会存在重边情况，因此两点直接应当取较小的边。

图论小知识

（搬的之前的笔记 233）

图 (Graph)

由顶点集合 $V(G)$ 和顶点之间边的集合 $E(G)$ 构成的数据结构，表示为 $G=(V,E)$ 可以用 $\left|V\right|$ 表示图 G 中顶点的个数，称为图 G 的阶，$\left|E\right|$ 则为图 G 中边的条数

无向图

E 为无向边的集合，则为无向图。两个顶点 $v,w$ 之间的边为无序对 $(v,w)$，称边 $(v,w)$ 依附于顶点 $v,w$。

权、网： 在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值。这种边上带有权值的图称为带权图，也称网。

邻接矩阵

稠密图：边 $E$ 接近于顶点 $V$ 邻接矩阵通常用于稠密图及快速判断两个节点之间是否有边相连的情况。 对于上面的带权图，可以用邻接矩阵表示为

$$\left[\begin{array}{cccccc}M& 6& 1& 5& M& M\\ 6& M& 5& M& 3& M\\ 1& 5& M& 5& 6& 4\\ 5& M& 5& M& M& 2\\ M& 3& 6& M& M& 6\\ M& M& 4& 2& 6& M\end{array}\right]$$

矩阵每一行描述一个节点与周围的联通关系及对应边的权重，如果不联通或者是它本身用 M 表示。在例题中令 $M=32768$，或者是另外一个很大的数，反正只要保证带 M 路径全被剪枝函数剪掉就行了。

路径合法性判断

注意之前存路径我们开的是一个定长的 vector 容器，长度为多开 2，这么搞不是为了防越界，而是将首末元素存成 0（即家的位置）。

1. 判断路径总长度-2 是否是网红点的个数，以确认有可能走过全部网红点
2. 将路径数据读入一个 set 容器，排除掉重复项后再次检查长度，以确认是否能够走过全部网红点

set<int> s(path.begin() + 1,path.end() - 1);

这里能用 path.end() - 1 是因为 set 支持双向迭代器，之前有的容器不能用懵了好久，如果有的容器不能用双向迭代获取 end() 前面的一个迭代器可以使用 prev(s.end()) 来获取，或者用常量反向迭代器获取那个位置 crbegin()。 4. 遍历整条路径，如果不连通直接退出，并且计算代价之和 5. 结束遍历后筛选出来的路径必然是合法的路径，此时将这些路径保存下来即可。

结果处理

按照题意写个 sort 函数排个序输出首元素即可。

sort(fuck.begin(),fuck.end(),[](pair<int,int> a,pair<int,int> b){
		return a.second < b.second;
	});
cout << fuck[0].first << " " << fuck[0].second << endl;