洛谷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
#include
#include
#include
#include
#include
#include
#include
#include
#include
#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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193