J 蚂蚁聚会

思路

听说这题是原题？

虽然效率更低但还是介绍一个现场口胡 bitset+最短路 做法：

看到题意容易想到和 2020 EC-Final D 题类似的思路：

• 令 $d(i,j)d(i,j)$ 为从 $ii$ 到 $jj$ 的最短路，一个方案 $(x_1,i,j,y_1)(x\_1,i,j,y\_1)$ 合法，当且仅当其满足 $d(x_1,y_1)=d(x_1,i)+d(i,j)+d(j,y_1)d(x\_1,y\_1)=d(x\_1,i)+d(i,j)+d(j,y\_1)$。

• 接下来预处理出以每个点为起点的最短路，接下来对于每对最短公共路径 $(i,j)(i,j)$，判断 $(x_1,i,j,y_1)(x\_1,i,j,y\_1)$ 与 $(x_2,i,j,y_2)(x\_2,i,j,y\_2)$ 或 $(x_1,i,j,y_1)(x\_1,i,j,y\_1)$ 与 $(x_2,j,i,y_2)(x\_2,j,i,y\_2)$ 是否合法，如果合法则把路径 $d(i,j)d(i,j)$ 更新为答案。

然而这题的 $m=300000m=300000$，直接这么做会 T 到飞起。

于是考虑另一个思路：对于方案 $(x_1,i,j,y_1)(x\_1,i,j,y\_1)$，我们先判断 $(i,j,y_1)(i,j,y\_1)$ 是否合法，再判断 $(x_1,i,y_1)(x\_1,i,y\_1)$ 是否合法。后者只需要四次最短路就能预处理，关键是如何处理前者：

我们令状态 $f[x][y][z]f[x][y][z]$ 为以 $xx$ 为起点，到 $zz$ 的最短路中是否可以含有 $yy$ 点，不难发现这部分可以与最短路同时处理，并且从 $ii$ 转移向 $jj$ 时有 $f[x][j]\mathrm{\mid }=f[x][i]f[x][j]|=f[x][i]$。如果直接暴力实现则时间复杂度为 $O(n^3)O(n^3)$，用 bitset 优化则可降为 $O(n^3\mathrm{/}64)O(n^3/64)$。

总时间复杂度 $O(mlogm+n^3\mathrm{/}64)O(mlogm+n^3/64)$。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int i,j,k,n,m,t,f[5][1505],res,id[1505],id2[1505],it;
vector<pair<int,int> >v[1505];
bitset<1505> b[5][1505];
bool vis[1505],vis2[1505];
vector<int> v1[1505];

void fuk(int i){
	id[i]=++it;
	id2[it]=i;
	
	priority_queue<pair<int,int> >q;
	memset(vis,0,sizeof(vis));
	for(j=1;j<=n;j++)v1[j].clear();
	
	q.push({0,i});
	f[id[i]][i]=0;
	
	i=it;
	while(!q.empty()){
		auto [w,id]=q.top();q.pop();
		if(vis[id])continue;
		b[i][id][id]=1;vis[id]=1;
		memset(vis2,0,sizeof(vis2));
		for(auto j:v1[id]){
			if(vis2[j])continue;
			vis2[j]=1;
			if(i==2||i==4)b[i][id]|=b[i][j];
		}
		w=-w;
		f[i][id]=w;
		for(auto [j,k]:v[id]){
			if(vis[j])continue;
			if((k+w)>f[i][j])continue;
			if((k+w)==f[i][j]){
				if(i==2||i==4)v1[j].push_back(id);
			}
			else{
				if(i==2||i==4)v1[j]={id};
				f[i][j]=k+w;
			}
			q.push({-(k+w),j});
		}
	}
}

bool fuk2(int a,int b1,int c,int d){
	if(!b[id[d]][b1][c])return 0;
	if(f[id[a]][b1]+f[id[d]][b1]!=f[id[a]][d])return 0;
	return 1;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m;
	int x1,y1,x2,y2;
	cin>>x1>>y1>>x2>>y2;
	for(i=1;i<=m;i++){
		cin>>j>>k>>t;
		v[j].push_back({k,t});
		v[k].push_back({j,t});
	}
	memset(f,31,sizeof(f));
	fuk(x1); fuk(y1); fuk(x2); fuk(y2);
	
	for(i=1;i<=n;i++){
		for(j=1;j<=n;j++){
			if(i==j)continue;
			if(fuk2(x1,i,j,y1)&&fuk2(x2,i,j,y2)){
				res=max(res,f[id[x1]][y1]-f[id[x1]][i]-f[id[y1]][j]);
			}
			else if(fuk2(x1,i,j,y1)&&fuk2(x2,j,i,y2)){
				res=max(res,f[id[x1]][y1]-f[id[x1]][i]-f[id[y1]][j]);
			}
		}
	}
	
	cout<<res;
}