92分求助

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3e5+5;
int n,m;
struct Edge{
	int to,next,w;
}edge1[N*2],edge2[N*2];
int head1[N],cnt1(0),head2[N],cnt2(0);
void add1(int u,int v,int w){
	edge1[++cnt1].to=v;
	edge1[cnt1].next=head1[u];
	edge1[cnt1].w=w;
	head1[u]=cnt1;
} 
int in[N];
void add2(int u,int v,int w){
	in[v]++;
	edge2[++cnt2].to=v;
	edge2[cnt2].next=head2[u];
	edge2[cnt2].w=w;
	head2[u]=cnt2;
}
int d[5][N];
bool vis[N];
struct node{
	int u,dis;
	bool operator<(const node &x) const{ return x.dis<dis; } 
};
void dij(int id,int st){
	memset(vis,0,sizeof(vis));
	priority_queue<node> q;
	q.push((node){st,0});
	memset(d[id],0x3f,sizeof(d[id]));
	d[id][st]=0;
	while(!q.empty()){
		int u=q.top().u;
		int dd=q.top().dis;
		q.pop();
		if (vis[u]) continue;
		vis[u]=1;
		for (int i=head1[u];i;i=edge1[i].next){
			int v=edge1[i].to;
			if (vis[v]) continue;
			if (d[id][v]>dd+edge1[i].w){
				d[id][v]=edge1[i].w+dd;
				q.push((node){v,d[id][v]});
			}
		}
	}
}
int len[N];
void topu(){
	queue<int> q;
	for (int i=1;i<=n;i++)
		if (!in[i]) q.push(i);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for (int i=head2[u];i;i=edge2[i].next){
			int v=edge2[i].to;
			len[v]=max(len[v],len[u]+edge2[i].w);
			if (!in[i]){
				in[i]--;
				q.push(v);
			}
		}
	}
}
signed main(){
	memset(head1,-1,sizeof(head1));
	memset(head2,-1,sizeof(head2));
	int x1,y1,x2,y2;
	cin >> n >> m;
	cin >> x1 >> y1 >> x2 >> y2;
	for (int i=1,x,y,z;i<=m;i++){
		cin >> x >> y >> z;
		add1(x,y,z);
		add1(y,x,z);
	}
	dij(1,x1);
	dij(2,y1);
	dij(3,x2);
	dij(4,y2);
	for (int u=1;u<=n;u++)
		for (int i=head1[u];i+1;i=edge1[i].next){
			int v=edge1[i].to,w=edge1[i].w;
			if (d[1][u]+w+d[2][v]==d[1][y1] && d[3][u]+w+d[4][v]==d[3][y2]){
				add2(u,v,w);
			}
		}
	topu();
	int ans(0);
	for (int i=1;i<=n;i++)
		ans = max(ans,len[i]);
	memset(head2,-1,sizeof(head2));
	cnt2=0;
	memset(in,0,sizeof(in));
	memset(len,0,sizeof(len));
	for (int u=1;u<=n;u++)
		for (int i=head1[u];i+1;i=edge1[i].next){
			int v=edge1[i].to,w=edge1[i].w;
			if (d[1][u]+w+d[2][v]==d[1][y1] && d[4][u]+w+d[3][v]==d[3][y2]){
				add2(u,v,w);
			}
		}
	topu();
	for (int i=1;i<=n;i++)
		ans = max(ans,len[i]);
	cout << ans;
	return 0;
}