[BZOJ5109]大吉大利，晚上吃鸡！

题目大意：

一张\(n(n\le5\times10^4)\)个点\(m(m\le5\times10^4)\)条边的无向图，节点编号为\(1\)到\(n\)，边权为正整数。给定\(S\)和\(T\)，显然从\(S\)到\(T\)的最短路有一种或多种方案。

选择\(A,B\)两个点，约定\(A\)点和\(B\)点必须满足：

求满足上面两个条件的\(A,B\)点对有多少个，交换\(A,B\)的顺序算相同的方案。

思路：

首先用Dijkstra求出最短路网络，显然这是一个DAG。

在DAG上DP求出一个点到\(S/T\)的方案数，将它们相乘即为经过这个点的路径数，记作\(F(i)\)。我们同样也可以用bitset求出经过这个点的路径上可能经过的点，记作\(S(i)\)。

而题目所求的\(A\)和\(B\)相当于需要满足以下两个条件：

显然枚举\(A\)和\(B\)会超时，由于\(F(A)+F(B)=F(T)\)。我们可以开一个map<int,bitset>保存\(F(B)=F(T)-F(A)\)的可能的\(B\)。

此时我们只需要枚举\(A\)，然后在map上查找对应的\(B\)即可。

源代码：

#include<cstdio>

#include<cctype>

#include<vector>

#include<bitset>

#include<climits>

#include<functional>

#include<tr1/unordered_map>

#include<ext/pb_ds/priority_queue.hpp>

inline int getint() {

	register char ch;

	while(!isdigit(ch=getchar()));

	register int x=ch^'0';

	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');

	return x;

}

typedef long long int64;

const int N=5e4+1,M=5e4;

struct Edge2 {

	int u,v,w;

};

Edge2 edge[M];

struct Edge3 {

	int to,w;

};

std::vector<Edge3> e3[N];

inline void add_edge(const int &u,const int &v,const int &w) {

	e3[u].push_back((Edge3){v,w});

	e3[v].push_back((Edge3){u,w});

}

bool vis[N];

int n,m,s,t,ind[N],ind2[N],outd[N];

int64 diss[N],dist[N],f[N],g[N],ans;

struct Vertex {

	int id;

	int64 d;

	bool operator > (const Vertex &rhs) const {

		return d>rhs.d;

	}

};

inline void dijkstra(const int &s,int64 dis[]) {

	static __gnu_pbds::priority_queue<Vertex,std::greater<Vertex> > q;

	static __gnu_pbds::priority_queue<Vertex,std::greater<Vertex> >::point_iterator p[N];

	for(register int i=1;i<=n;i++) {

		p[i]=q.push((Vertex){i,dis[i]=i==s?0:LLONG_MAX});

	}

	while(!q.empty()&&q.top().d!=LLONG_MAX) {

		const int x=q.top().id;

		q.pop();

		for(register unsigned i=0;i<e3[x].size();i++) {

			const int &y=e3[x][i].to,&w=e3[x][i].w;

			if(dis[x]+w<dis[y]) {

				q.modify(p[y],(Vertex){y,dis[y]=dis[x]+w});

			}

		}

	}

	q.clear();

}

std::vector<int> e[N],e4[N];

inline void add_edge(const int &u,const int &v) {

	e[u].push_back(v);

	e4[v].push_back(u);

	ind[v]++;

	ind2[v]++;

	outd[u]++;

}

std::queue<int> q;

std::bitset<N> b[N];

inline void kahn2() {

	q.push(t);

	g[t]=1;

	while(!q.empty()) {

		const int &x=q.front();

		for(register unsigned i=0;i<e4[x].size();i++) {

			const int &y=e4[x][i];

			g[y]+=g[x];

			if(!--outd[y]) q.push(y);

		}

		q.pop();

	}

}

inline void kahn() {

	q.push(s);

	f[s]=1;

	while(!q.empty()) {

		const int &x=q.front();

		b[x][x]=true;

		for(register unsigned i=0;i<e[x].size();i++) {

			const int &y=e[x][i];

			b[y]|=b[x];

			f[y]+=f[x];

			if(!--ind[y]) q.push(y);

		}

		q.pop();

	}

}

inline void kahn3() {

	q.push(s);

	while(!q.empty()) {

		const int &x=q.front();

		b[0][x]=true;

		b[x]=b[0]^b[x];

		for(register unsigned i=0;i<e[x].size();i++) {

			const int &y=e[x][i];

			if(!--ind2[y]) q.push(y);

		}

		q.pop();

	}

}

std::tr1::unordered_map<int64,std::bitset<N> > map;

int main() {

	n=getint(),m=getint(),s=getint(),t=getint();

	for(register int i=0;i<m;i++) {

		const int u=getint(),v=getint(),w=getint();

		edge[i]=(Edge2){u,v,w};

		add_edge(u,v,w);

	}

	dijkstra(s,diss);

	if(diss[t]==LLONG_MAX) {

		printf("%lld\n",(int64)n*(n-1)/2);

		return 0;

	}

	dijkstra(t,dist);

	for(register int i=1;i<=n;i++) e3[i].clear();

	for(register int i=0;i<m;i++) {

		int u=edge[i].u,v=edge[i].v,w=edge[i].w;

		if(diss[u]>diss[v]) std::swap(u,v);

		if(diss[u]+w+dist[v]==diss[t]) {

			add_edge(u,v);

			vis[u]=vis[v]=true;

		}

	}

	int cnt=0;

	for(register int i=1;i<=n;i++) cnt+=!vis[i];

	kahn2();

	kahn();

	kahn3();

	for(register int i=1;i<=n;i++) {

		if(vis[i]) map[f[i]*g[i]][i]=true;

	}

	for(register int i=1;i<=n;i++) {

		if(!vis[i]) continue;

		if(map.count(f[t]-f[i]*g[i])) ans+=(map[f[t]-f[i]*g[i]]&b[i]).count();

		if(f[i]*g[i]==f[t]) ans+=cnt;

	}

	printf("%lld\n",ans);

	return 0;

}