72分（WA #4 #5 #11）

#include<bits/stdc++.h>
using namespace std;
int ans;
const int N = 1600;
const int maxm=3e6; 
const int inf = 0x3f3f3f3f;
struct node {
    int v, w;
    node(int vv, int ww) {
        v = vv;
        w = ww;
    }
};
struct edge{
	int v,w,next;
	bool x;
}E[maxm]; 
int p[N];
int cnt;
void init(){
	for(int i=1;i<N;i++) p[i]=-1;
}
void addedged(int u,int v,int w,bool x){
	E[cnt].v=v;
	E[cnt].w=w;
	E[cnt].next=p[u];
	E[cnt].x=x;
	p[u]=cnt++;
}
vector<node> g[N];
int d[6][N];
bool in_queue[N];
queue<int> q;
int n,m,x11,y11,x22,y22;
void SPFA(int s,int i){
	memset(in_queue,0,sizeof(in_queue));
	memset(d[i],inf,sizeof(d[i]));
	for(int j=1;j<=n;j++){
		d[i][j]=inf;
	}
    d[i][s] = 0;
    in_queue[s]=true;
    q.push(s);
    while(!q.empty()){
        int v=q.front();
        q.pop();
        in_queue[v]=false;
        for(int j=0;j<g[v].size();j++){
            int x=g[v][j].v;
            if(d[i][x]>d[i][v]+g[v][j].w){
                d[i][x]=d[i][v]+g[v][j].w;
                if(!in_queue[x]){
                    q.push(x);
                    in_queue[x]=true;
                }
            }
        }
    }
}
int dp[N];
void ad(){
	for(int i=1;i<=n;i++){
		for(int j=0;j<g[i].size();j++){
			int v=g[i][j].v;
			int w=g[i][j].w;
			if(d[1][i]+w+d[2][v]==d[1][y11]){
				bool id;
				if(d[3][i]+w+d[4][v]==d[3][y22]||d[3][v]+w+d[4][i]==d[3][y22]){
					addedged(i,v,w,1);
					id=true;
				}
				if(!id) addedged(i,v,w,0);
			}
		}
	}
} 
int dfs(int x){
	if(dp[x]) return dp[x];
	for(int i=p[x];i!=-1;i=E[i].next){
		int vv=E[i].v;
		int ww=E[i].w;
		dp[x]=max(dp[x],dfs(vv)+E[i].x*ww);
	}
}
bool readed[N];
int main(){

	init();
	cin>>n>>m>>x11>>y11>>x22>>y22;
	for(int i=1;i<=m;i++){
		int x,y,z;
		cin>>x>>y>>z;
		g[x].push_back(node(y,z));
		g[y].push_back(node(x,z));
	}
	SPFA(x11,1);
	SPFA(y11,2);
	SPFA(x22,3);
	SPFA(y22,4);
	cnt++;
	ad();
	memset(dp,0,sizeof(dp));
	for(int i=1;i<=n;i++){
		if(!dp[i]){
			int useless=dfs(i);
		}
	}
	for(int i=1;i<=n;i++){
		ans=max(dp[i],ans);
	}
	ans+=1; 
	cout<<ans;
	return 0;
}

求求了