有 \(n\)​ 个点，\(m\)​ 条边的无向图，每条边有一个颜色 \(c_i\)​ ，每条边的代价为 \(1\)​ .

如果连续经过多条颜色相同的边，代价会减少，总代价为 \(1\)​ .

问从 \(1\) 号点到 \(n\) 号点，最少代价是多少？

\(1\leq n\leq 10^5,0\leq m\leq 2\cdot 10^5,1\leq c_i\leq 10^6\)

大概 2019 年 12 月份第一次见到这个题目. 知道了建虚拟节点.

首先，因为经过多条颜色相同的边代价为 \(1\)​​ ，那么，可以把颜色相同的边连成的点看成一个连通块. 但这和普通的联通块也有些区别，因为两个点中可能有多条颜色相同的边，所以，一个点会包含在多个联通块中.

那么，同一个联通块中的点两两之间到达的代价是 \(1\)​​ ，如果直接连边肯定不优，考虑新建一个点 \(x\)​​ ，让联通块中的所有点连向 \(x\)​​ ，代价为 \(1\)​，接着，让 \(x\)​ 连向联通块中的所有点，代价为 \(0\)​. 这样，把 \(O(n^2)\)​ 的点变成了 \(O(n)\)​ 的.

建出新图中的边权是 \(0\) 或 \(1\) ，求最短路，可以用 01bfs 实现 .

在处理联通块的时候也要小心，要避免写成 \(O(nm)\) 的，对于同一个颜色统一处理，然后用 dsu 判断联通块.

还需要注意的就是这题数组要开到的范围，如果是上面的思路，图中的点就有可能达到 \(3\cdot 10^5\) ，而且颜色是 \(10^6\) 个的.

统计被同种颜色连接的点时需要去重之后再用dsu判断，否则，显出新图的时候会重复连边，导致空间爆炸. 这个问题非常隐蔽，但是我感觉挺重要的.

时间复杂度 : \(O(n+m)\)

空间复杂度 : \(O(n+m)\)

第一次提交 : AC

code

#include<bits/stdc++.h>
using namespace std;
const int inf=1e9+10;
int n,m;
int fa[100010];
vector<int>v[1000010],cmp[100010];
vector<pair<int,int> >g[300010],e[1000010];
int dist[300010];
deque<int>que;
inline int get_fa(int x){
	return fa[x]==x?x:fa[x]=get_fa(fa[x]);
}
inline void merge(int a,int b){
	a=get_fa(a);b=get_fa(b);
	if(a==b)return;
	fa[a]=b;
}
inline void ae(int u,int v,int cost){
	g[u].push_back(make_pair(v,cost));
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=0;i<m;i++){
		int a,b,c;
		cin>>a>>b>>c;
		a--;b--;c--;
		e[c].push_back(make_pair(a,b));
		v[c].push_back(a);
		v[c].push_back(b);
	}
	int cnt=n;
	for(int i=0;i<n;i++)fa[i]=i;
	for(int i=0;i<1000000;i++){
		if((int)v[i].size()==0)continue;
		sort(v[i].begin(),v[i].end());
		v[i].erase(unique(v[i].begin(),v[i].end()),v[i].end());
		for(int j=0;j<(int)e[i].size();j++){
			int a=e[i][j].first,b=e[i][j].second;
			merge(a,b);
		}
		for(int j=0;j<(int)v[i].size();j++){
			int x=v[i][j];
			cmp[get_fa(x)].push_back(x);
		}
		for(int j=0;j<(int)v[i].size();j++){
			int x=v[i][j];
			if((int)cmp[x].size()==0)continue;
			for(int k=0;k<(int)cmp[x].size();k++){
				ae(cmp[x][k],cnt,1);
				ae(cnt,cmp[x][k],0);
			}
			cnt++;
		}
		for(int j=0;j<(int)v[i].size();j++){
			int x=v[i][j];
			fa[x]=x;
			cmp[x].clear();
		}
	}
	for(int i=0;i<cnt;i++)dist[i]=inf;
	dist[0]=0;
	que.push_front(0);
	while(!que.empty()){
		int x=que.front();que.pop_front();
		for(int i=0;i<(int)g[x].size();i++){
			int to=g[x][i].first,cost=g[x][i].second;
			if(dist[to]==inf){
				dist[to]=dist[x]+cost;
				if(cost==0)que.push_front(to);
				else que.push_back(to);
			}
		}
	}
	if(dist[n-1]==inf)dist[n-1]=-1;
	cout<<dist[n-1]<<endl;
	return 0;
}
/*inline? ll or int? size? min max?*/

w4yneb0t

还是考虑联通块中的点能花费代价为 \(1\) 互相到达，是否可以不建出新图的情况下，bfs 得到.

用 \(dis(i)\)​ 表示第 \(0\) 个点到第 \(i\) 个点的最短距离.

bfs 队列的第一个元素 \(x\)​ ，它可以花费为 \(1\)​ 的代价到达的点有哪些. 考虑连接 \(x\) 的一个边为 \(i\) ，那么，包含 \(x\) ，以颜色为 \(c_i\) 的边连接的连通块中的点都可以花费 \(1\) 的代价到达 . 那么，可以 dfs 跟新这些点.

但是，这就存在一个问题，转移的时候时间复杂度是 \(O(n)\)​ 的 .

但是，其实有些转移是不需要的，一个连通块中只要有一个点从 bfs 序列的队首弹出跟新，整个连通块解会被跟新一遍 . 对于在 bfs 序列后的此联通块中的点，就不会是最优转移的来源了 . 此时，需要一个 set 数组记录每个点被跟新过的颜色集合. 并且，还需要一个用 set 或 map 存储的连接表，能单独取出与 \(x\) 相连，颜色为 \(c\) 的点.

这个思路的有点在于出去了上面求连通块的，非常容易犯错的部分. 但是，在时间复杂度上面就没有上面的优秀.

时间复杂度 : \(O(n+m+m\log m+n\log m)\)​

空间复杂度 : \(O(n+m)\)

tourist

还是考虑对于每个联通块新建一个点，建出上面的图，在处理联通块的时候，还可以考虑 bfs 一个联通块中的点. 问题在于，连接表中无法表示颜色，所以有可能遍历是 \(O(n(n+m))\) 的 .

因为颜色分类，求出联通块，所以，如果将邻接表按照颜色 sort 一遍之后，能通过的点，就是一段区间，所以，可以考虑对每个节点的邻接表维护一个指针，用双指针的方法做到 \(O(n+m)\) 的遍历. 因此，就可以 bfs 求出一个联通块的点.

那么，其实可以不用 01 bfs，因为上面新建出的图是个有向图，其中原图中的点的出边都是 \(1\) ，入边都是 \(0\) .

图其实非常有规律，路径必定都是 图中的点 \(\rightarrow\) 新建的点 \(\rightarrow\) 图中的点 \(\rightarrow\) 新建的点 \(\rightarrow\) 图中的点 \(\cdots\)​ 这样下去 .

其实可以令所有的边为代价 \(1\)​ ，相当于每个联通块的代价是 \(2\) . 在 bfs 之后，只要将总代价 / 2 就可以了.

时间复杂度 : \(O(n+m+m\log m)\)

空间复杂度 : \(O(n+m)\)