莫名其妙的RE，数组开大到MLE还是没用

我先对于x1，y1求出所有最短路，记录每个点的pre（在最短路上的入边），通过bfs倒推出最短路的DAG，上面的每个边打上标记

再对于x2，y2同样推出最短路的DAG，从正反两个方向分别判断每个边是否在公共路径上

新建一个公共路径边的图，再拓扑dp最深链

自认为正确性和复杂度没有问题，是不是写假了啊qwq

#include <queue>
#include <cstdio>
#include <cctype>
#include <vector>
#include <cstring>

using namespace std;

namespace RenaMoe {

template<typename T>
inline void read(T &x) {
	x = 0; bool f = false; char in = getchar();
	while (!isdigit(in)) { if (in == '-') f = true; in = getchar(); }
	while (isdigit(in)) x = x * 10 + in - '0', in = getchar();
	x = f ? -x : x;
}

const int N = 3e3 + 9;
const int M = 6e6 + 9;
const int INF = 0x3f3f3f3f;

struct Edge {
	int nxt, to, val;
};

int n, m, x1, y1, x2, y2, cnte, ans;
int head[N], head2[N], disx1[N], disx2[N], out[N], deep[N];
// out点的度数，deep最长链的长度
Edge e[M], e_[M];// 旧、新图
bool inq[N], in1[M];// inq是否在队列里，in1边是否在x1到y1最短路上
queue<int> q;
vector<int> pre[N];

inline void add_edge(int u, int v, int w) {
	e[++cnte] = (Edge){head[u], v, w}, head[u] = cnte;
}
inline void add_edge2(int u, int v, int w) {
	e_[++cnte] = (Edge){head2[u], v, w}, head2[u] = cnte;
}

inline void SPFA(int s, int *dis) {
	for (int i = 1; i <= n; ++i) dis[i] = INF, pre[i].clear();
	dis[s] = 0;
	q.push(s), inq[s] = true;
	while (!q.empty()) {
		int u = q.front();
		q.pop(), inq[u] = false;
		for (int i = head[u], v; i; i = e[i].nxt) {
			v = e[i].to;
			if (dis[v] > dis[u] + e[i].val) {
				dis[v] = dis[u] + e[i].val;
				if (!inq[v]) q.push(v), inq[v] = true;
				pre[v].clear(), pre[v].push_back(i);
			}
			else if (dis[v] == dis[u] + e[i].val)
				pre[v].push_back(i);
		}
	}
}

inline void calc_deep() {
	memset(deep, 0, sizeof deep);
	for (int i = 1; i <= n; ++i)
		if (!out[i]) q.push(i);
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		for (int i = head2[u], v; i; i = e_[i].nxt) {
			v = e_[i].to, out[v]--;
			if (!out[v]) q.push(v);
			deep[v] = max(deep[v], deep[u] + e_[i].val);
		}
	}
	for (int i = 1; i <= n; ++i)
		ans = max(ans, deep[i]);
}

inline void main() {
	cnte = 1;
	read(n), read(m), read(x1), read(y1), read(x2), read(y2);
	for (int i = 1, u, v, w; i <= m; ++i)
		read(u), read(v), read(w), add_edge(u, v, w), add_edge(v, u, w);

	SPFA(x1, disx1);
	q.push(y1);
	while (!q.empty()) {
		int u = q.front();
		q.pop(), inq[u] = false;
		for (int i = 0, s = pre[u].size(); i < s; ++i) {
			int j = pre[u][i], v = e[j^1].to;
			in1[j^1] = true;
			if (!inq[v]) q.push(v), inq[v] = true;
		}
	}

	cnte = 0;
	SPFA(x2, disx2);
	q.push(y2);
	while (!q.empty()) {
		int u = q.front();
		inq[u] = false;
		q.pop();
		for (int i = 0, s = pre[u].size(); i < s; ++i) {
			int j = pre[u][i], v = e[j^1].to;
			if (in1[j])
				add_edge2(u, v, e[j].val), out[v]++;
			if (!inq[v]) q.push(v), inq[v] = true;
		}
	}
	calc_deep();

	memset(head2, 0, sizeof head2);
	cnte = 0;
	q.push(y2);
	while (!q.empty()) {
		int u = q.front();
		q.pop(), inq[u] = false;
		for (int i = 0, s = pre[u].size(); i < s; ++i) {
			int j = pre[u][i], v = e[j^1].to;
			if (in1[j^1])
				add_edge2(v, u, e[j].val), out[u]++;
			if (!inq[v]) q.push(v), inq[v] = true;
		}
	}
	calc_deep();
	printf("%d\n", ans);
}
}

int main() {
	RenaMoe::main();
	return 0;
}