洛谷 P6573 [BalticOI 2017] Toll 题解

#include <bits/stdc++.h>

#define N 50010

#define M 1000010

#define pii pair<int,int>

#define mkp make_pair

#define pb push_back

#define fi first

#define se second

//#define int long long

//#define MOD

#define INF 1000000000

#define int_edge int to[M],nxt[M],head[N],cnt=0;

using namespace std;

int k,n,m,q,fa[N][16],f[N],dep[N],eid=0,vis[N];

int_edge;void add_edge(int x,int y ){to[++cnt]=y;nxt[cnt]=head[x];head[x]=cnt;}

map<pii,int>mp;

struct Y{int x,y,t;};vector<Y>E[N];

int id(int x){return x/k+1;}

//int_edge;int val[M];void add_edge(int x,int y,int z){to[++cnt]=y;val[cnt]=z;nxt[cnt]=head[x];head[x]=cnt;}

struct Matrix{

	int a[5][5];

	Matrix(){memset(a,0x3f,sizeof(a));}

	Matrix operator * (const Matrix &y){

		Matrix sum;

		for(int i=0;i<5;i++)

			for(int j=0;j<5;j++)

				for(int k=0;k<5;k++)

					sum.a[i][j]=min(sum.a[i][j],a[i][k]+y.a[k][j]);

		return sum;

	}

}dn[N][16];

Matrix init(){

	Matrix x;for(int i=0;i<k;i++)x.a[i][i]=0;return x;

}

int find(int x){return x==f[x]?x:f[x]=find(f[x]);}

void dfs(int nw,int lst){

	vis[nw]=1;

	fa[nw][0]=lst;dep[nw]=dep[lst]+1;

	if(lst!=0){

		for(auto e:E[mp[mkp(lst,nw)]]){

			dn[nw][0].a[e.x%k][e.y%k]=e.t;

		}

	}

	for(int i=1;i<=15;i++){

		fa[nw][i]=fa[fa[nw][i-1]][i-1];

		dn[nw][i]=dn[fa[nw][i-1]][i-1]*dn[nw][i-1];

	}

	for(int i=head[nw];i;i=nxt[i])

		if(to[i]!=lst)dfs(to[i],nw);

}

signed main()

{

	scanf("%d %d %d %d",&k,&n,&m,&q);

	for(int i=0;i<n;i++)f[i]=i;

	for(int i=1,x,y,t;i<=m;i++){

		scanf("%d %d %d",&x,&y,&t);

		f[find(x)]=find(y);

		if(mp.find(mkp(id(x),id(y)))==mp.end()){

			mp[mkp(id(x),id(y))]=++eid;

			add_edge(id(x),id(y));

		}

		E[mp[mkp(id(x),id(y))]].pb(Y{x,y,t});

	}

	for(int i=1;i<=id(n);i++)if(!vis[i])dfs(i,0);

	while(q--){

		int x,y;scanf("%d %d",&x,&y);

		if(find(x)!=find(y)){puts("-1");continue;}

		int id1=id(x),id2=id(y);

		Matrix ans=init();

		for(int i=15;i>=0;i--)

			if(dep[fa[id2][i]]>=dep[id1])

				ans=dn[id2][i]*ans,id2=fa[id2][i];

		if(ans.a[x%k][y%k]==1061109567)puts("-1");

			else printf("%d\n",ans.a[x%k][y%k]);

	}

	return 0;

}