洛谷P4061 大吉大利，晚上吃鸡

传送门

题目背景

最近《绝地求生：大逃杀》风靡全球，皮皮和毛毛也迷上了这款游戏，他们经常组队玩这款游戏。

在游戏中，皮皮和毛毛最喜欢做的事情就是堵桥，每每有一个好时机都能收到不少的快递。

当然，有些时候并不能堵桥，皮皮和毛毛会选择在其他的必经之路上蹲点。

K博士作为一个老年人，外加有心脏病，自然是不能玩这款游戏的，但是这并不能妨碍他对这款游戏进行一些理论分析，比如最近他就对皮皮和毛毛的战术很感兴趣。

题目描述

游戏的地图可以抽象为一张 nn 个点 mm 条无向边的图，节点编号为 11 到 nn ，每条边具有一个正整数的长度。

**假定大魔王都会从 SS 点出发到达 TT 点（ SS 和 TT 已知），并且只会走最短路，**皮皮和毛毛会在 AA 点和 BB 点埋伏大魔王。

为了保证一定能埋伏到大魔王，同时又想留大魔王一条生路，皮皮和毛毛约定 AA 点和 BB 点必须满足：

大魔王所有可能路径中，必定会经过 AA 点和 BB 点中的任意一点

大魔王所有可能路径中，不存在一条路径同时经过 AA 点和 BB 点

K博士想知道，满足上面两个条件的 A,BA,B 点对有多少个，交换 A,BA,B 的顺序算相同的方案。

输入格式
第一行输入四个整数 n,m,S,T(1 \le n \le 5 \times 10^{4}, 1 \le m \le 5 \times 10^{4}, 1 \le S,T \le n)n,m,S,T(1≤n≤5×10
4
,1≤m≤5×10
4
,1≤S,T≤n) ，含义见题目描述。

接下来输入 mm 行，每行输入三个整数 u,v,w(1 \le u,v \le n, 1 \le w \le 10^{9})u,v,w(1≤u,v≤n,1≤w≤10
9
) 表示存在一条长度为 ww 的边链接 uu 和 vv 。

输出格式

输出一行表示答案。

输入输出样例

输入 #1复制
7 7 1 7
1 2 2
2 4 2
4 6 2
6 7 2
1 3 2
3 5 4
5 7 2
输出 #1复制
6
输入 #2复制
5 5 1 4
1 2 1
1 3 1
2 4 1
3 4 1
4 5 1
输出 #2复制
3
输入 #3复制
6 7 1 4
1 2 1
1 3 1
2 4 1
3 4 1
4 5 1
1 6 2
6 4 2
输出 #3复制
5

说明/提示

样例1解释
合法的方案为<2,3>,<2,4>,<4,3>,<4,5>,<6,3>,<6,5><2,3>,<2,4>,<4,3>,<4,5>,<6,3>,<6,5> 。

来自 CodePlus 2017 11 月赛，清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。

Credit：idea/陈宇 命题/陈宇 验题/邢健开

Git Repo：https://git.thusaac.org/publish/CodePlus201711

感谢腾讯公司对此次比赛的支持。

上代码：

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<iterator>
#include<cstdlib>
#include<queue>
#include<vector>
#include<map>
#define ll long long
using namespace std;

int n,m,ss,tt;
struct ed
{
    
	int pre,to;
	ll w;
}edge[200010];
int at=1,ptr[100010];

ll ans; const ll mod=1e9+7;

template<typename int_t>
void readx(int_t& x)
{
    
	x=0; int_t k=1; char ch=0;
	while (ch<'0' || ch>'9') {
     ch=getchar(); if (ch=='-') k=-1; }
	while (ch>='0' && ch<='9') {
     x=x*10+ch-'0'; ch=getchar(); }
	x*=k;
}

void Is(int fx,int tx,ll wx)
{
    
	edge[++at].pre=ptr[fx];
	edge[at].to=tx;
	edge[at].w=wx;
	ptr[fx]=at;
	edge[++at].pre=ptr[tx];
	edge[at].to=fx;
	edge[at].w=wx;
	ptr[tx]=at;
}

// Dijkstra
struct _Node
{
    
	ll dis;int cod;
	bool operator < (const _Node& B) const {
     return dis>B.dis; }
};
priority_queue<_Node> que;
ll dis[100010],dist[100010];
int pren[100010];
bool vis[100010];
void Dijkstra()
{
    
	_Node cac1,cac2;
	memset(dis,0x3f,sizeof dis); memset(dist,0x3f,sizeof dist); memset(vis,0,sizeof vis);
	cac1.dis=dis[ss]=0; cac1.cod=ss; que.push(cac1);
	while (!que.empty())
	{
    
		cac1=que.top(); que.pop();
		if (vis[cac1.cod]) continue;
		vis[cac1.cod]=1;
		for (int e=ptr[cac1.cod];e;e=edge[e].pre) 
		{
    
			register int v=edge[e].to;
			if (dis[v]>dis[cac1.cod]+edge[e].w)
			{
    
				dis[v]=dis[cac1.cod]+edge[e].w;
				cac2.cod=v; cac2.dis=dis[v];
				que.push(cac2);
			}
		}
	}
	memset(vis,0,sizeof vis);
	cac1.dis=dist[tt]=0; cac1.cod=tt; que.push(cac1);
	while (!que.empty())
	{
    
		cac1=que.top(); que.pop();
		if (vis[cac1.cod]) continue;
		vis[cac1.cod]=1;
		for (int e=ptr[cac1.cod];e;e=edge[e].pre) 
		{
    
			register int v=edge[e].to;
			if (dist[v]>dist[cac1.cod]+edge[e].w)
			{
    
				dist[v]=dist[cac1.cod]+edge[e].w;
				pren[v]=cac1.cod;
				cac2.cod=v; cac2.dis=dist[v];
				que.push(cac2);
			}
		}
	}
}

void NoSol() {
     if (dis[tt]>=0x3f3f3f3f3f3f3f3fLL) {
     ans=1LL*n*(n-1)/2LL; printf("%lld\n",ans); exit(0); } }

// SSSP Graph
int outv[100010];
ll f1[100010],f2[100010],f[100010];

// get path
int path[100010],lm[100010],rm[100010],len;
void Init()
{
    
	for (int i=ss;i;i=pren[i])
	{
    
		path[++len]=i;
		lm[i]=len+1; // illegal
		rm[i]=len-1; // illegal
	}
	
	// mapping the node to its range [lm,rm]
	for (int i=1;i<=n;i++) if (!lm[i]) {
     lm[i]=1; rm[i]=len; } 

	for (int i=1;i<=n;i++) 
		for (int e=ptr[i];e;e=edge[e].pre) if (edge[e].w>0 && dis[i]+dist[edge[e].to]+edge[e].w==dis[tt])
		{
    
			edge[e].w=-1; edge[e^1].w=-2;
			outv[edge[e].to]++;
		}
}

queue<int> tque;
void TopoSort() // To get the SSP number of every node.
{
    
	f1[ss]=1; f2[tt]=1;
	int cac;
	for (int i=1;i<=n;i++) if (!outv[i]) tque.push(i);
	while (!tque.empty())
	{
    
		cac=tque.front(); tque.pop();
		for (int e=ptr[cac];e;e=edge[e].pre) if (edge[e].w==-1)
		{
    
			int v=edge[e].to;
			outv[v]--; f1[v]+=f1[cac]; lm[v]=max(lm[v],lm[cac]); // update range
			if (!outv[v]) tque.push(v);
		}
	}
	
	for (int i=1;i<=n;i++)
		for (int e=ptr[i];e;e=edge[e].pre) if (edge[e].w==-2) outv[edge[e].to]++;
	for (int i=1;i<=n;i++) if (!outv[i]) tque.push(i);
	while (!tque.empty())
	{
    
		cac=tque.front(); tque.pop();
		for (int e=ptr[cac];e;e=edge[e].pre) if (edge[e].w==-2)
		{
    
			int v=edge[e].to;
			outv[v]--; f2[v]+=f2[cac]; rm[v]=min(rm[v],rm[cac]); // update range
			if (!outv[v]) tque.push(v);
		}
	}
}

// bucket
vector<int> p1[100010],p2[100010];
vector<int>::iterator itr;
// mapper
map<ll,int> maps;

void Getans()
{
    
	for (int i=1;i<=n;i++)
	{
    
		f[i]=f1[i]*f2[i];
		if (lm[i]<=rm[i]) {
     p1[lm[i]].push_back(f[i]); p2[rm[i]].push_back(f[i]); }
	}
	
	for (int i=1;i<=len;i++)
	{
    
		for (itr=p1[i].begin();itr!=p1[i].end();itr++) maps[*itr]++;
		ans+=1LL*maps[f[tt]-f[path[i]]];
		for (itr=p2[i].begin();itr!=p2[i].end();itr++) maps[*itr]--;
	}
}

int main()
{
    
	readx(n); readx(m); readx(ss); readx(tt); int fx,tx; ll wx;
	for (int i=1;i<=m;i++)
	{
    
		readx(fx); readx(tx); readx(wx);
		Is(fx,tx,wx);
	}
	Dijkstra(); NoSol();
	
	Init(); TopoSort(); 
	Getans();
	printf("%lld\n",ans);
	return 0;
}