题解

怎么题解区都在写假算。现在 SPFA 已经被卡爆了。

Difficulty：4.1 / Easy

Tag：缩点

缩点版题。

显然一个 SCC 的能互相到达。然后缩点后就成了一个 DAG，记录一个 SCC 内价格最小值最大值，跑拓扑排序即可。

然后实现的话要考虑一堆细节，比如说不要让 $1$ 到不了的点更新答案。

namespace cjdst{
    const int N = 100000;
	
	int a[N + 5];
	std::vector <int> v[N + 5];
	int n, m;
	
	std::vector <int> stack;
	int scc[N + 5], vis[N + 5], low[N + 5], dfn[N + 5];
	int curscc, curdfn;
	
	int mn[N + 5], mx[N + 5], ans[N + 5];
	std::vector <int> v2[N + 5];
	int in[N + 5];
	
	void dfs(int cur){
		stack.push_back(cur);
		low[cur] = dfn[cur] = (++curdfn);
		for(int i:v[cur]){
			if(scc[i] != -1) continue;
			if(dfn[i] == -1) dfs(i);
			low[cur] = std::min(low[cur], low[i]);
		}
		if(low[cur] == dfn[cur]){
			curscc++;
			int tmp = stack.back();
			do{
				tmp = stack.back();
				scc[tmp] = curscc;
				stack.pop_back();
			}while(tmp != cur);
		}
	}
	
	void dfs2(int cur){
		vis[cur] = 1;
		for(int i:v2[cur]){
			if(vis[i]) continue;
			dfs2(i);
		}
	}
    
    void solve(){
		std::cin >> n >> m;
		for(int i = 1; i <= n; i++){
			std::cin >> a[i];
		}
		for(int i = 1; i <= m; i++){
			int x, y, z;
			std::cin >> x >> y >> z;
			if(z == 1) v[x].push_back(y);
			else v[x].push_back(y), v[y].push_back(x);
		}
		memset(scc, -1, sizeof(scc));
		memset(dfn, -1, sizeof(dfn));
		for(int i = 1; i <= n; i++){
			if(scc[i] == -1) dfs(i);
		}
		memset(mn, 63, sizeof(mn));
		for(int i = 1; i <= n; i++){
			mn[scc[i]] = std::min(mn[scc[i]], a[i]);
			mx[scc[i]] = std::max(mx[scc[i]], a[i]);
			for(int j:v[i]){
				if(scc[i] == scc[j]) continue;
				v2[scc[i]].push_back(scc[j]);
			}
		}
		
		memset(vis, 0, sizeof(vis));
		dfs2(scc[1]);
		for(int i = 1; i <= curscc; i++){
			if(!vis[i]) continue;
			for(int j:v2[i]){
				if(!vis[j]) continue;
				in[j]++;
			}
		}
		
		std::queue <int> q;
		for(int i = 1; i <= curscc; i++){
			if(vis[i] && !in[i]) q.push(i);
		}
		
		while(!q.empty()){
			int head = q.front();
			q.pop();
			ans[head] = std::max(ans[head], mx[head] - mn[head]);
			for(int i:v2[head]){
				if(!vis[i]) continue;
				mn[i] = std::min(mn[i], mn[head]);
				ans[i] = std::max(ans[i], ans[head]);
				if(!(--in[i])) q.push(i);
			}
		}
		std::cout << ans[scc[n]] << '\n';
	}
}

时间复杂度：$O(n+m)$。