[SDOI2009]Elaxia's route

Title Description

Recently, Elaxia and w * * have a very good relationship. They really want to be together all day, but their study in college is too tight. They must reasonably arrange their time together.

Elaxia and w * * have to travel between the dormitory and the laboratory every day. They hope to walk together as long as possible on the premise of saving time.

Now known are the numbers of the dormitories and laboratories where Elaxia and w * * are located and the map of the school:
There are n intersections and m roads on the map. It takes a certain time to pass each road. Specifically, it requires the shortest and longest common path between two pairs of points in an undirected graph.

Input format

Two positive integers n,m in the first line represent the number of points and edges.

The four positive integers x1, y1, x2 and y2 in the second line represent the labels of Elaxia's dormitory and laboratory and w * *'s dormitory and laboratory respectively.

In the next m lines, there are three integers u,v and W in each line, indicating that there is an edge between u and V, and it takes w to pass.

Output format

An integer on a line represents the answer. (i.e. the length of the longest common path)

Input and output samples

input

9 10
1 6 7 8
1 2 1
2 5 2
2 3 3
3 4 2
3 9 5
4 5 3
4 6 4
4 7 2
5 8 1
7 9 1

output

3

Description / tips

[data range]
For 30% data, 1 ≤ n ≤ 100;
For 60% of data, 1 ≤ n ≤ 1000;
For 100% of the data, 1 ≤ n ≤ 1500, 1 ≤ w ≤ 1e4, the input data shall ensure that there is no double edge and self ring.

Problem solving ideas

First, ensure the shortest circuit, so build the common part of the two shortest circuit diagrams. The specific steps are as follows:
Firstly, start the single source shortest circuit from two starting points and end points respectively, and get the distance from each point to these four points
Respectively recorded as d i s [ x ] [ 1 ] , d i s [ x ] [ 2 ] , d i s [ x ] [ 3 ] , d i s [ x ] [ 4 ] dis[x][1],dis[x][2],dis[x][3],dis[x][4] dis[x][1],dis[x][2],dis[x][3],dis[x][4], and then for an edge ( U , V , W ) (U,V,W) (U,V,W),
If
d i s [ u ] [ 1 ] + d i s [ v ] [ 2 ] + w = d i s [ y 1 ] [ 1 ]   a n s   d i s [ u ] [ 3 ] + d i s [ v ] [ 4 ] + w = d i s [ y 2 ] [ 3 ] dis[u][1]+dis[v][2]+w=dis[y1][1] \:ans \:dis[u][3]+dis[v][4]+w=dis[y2][3] dis[u][1]+dis[v][2]+w=dis[y1][1]ansdis[u][3]+dis[v][4]+w=dis[y2][3]
Then this edge is on the shortest path graph, but because the shortest path direction may be inconsistent
Therefore, judgment is also needed
d i s [ u ] [ 1 ] + d i s [ v ] [ 2 ] + w = d i s [ y 1 ] [ 1 ]   a n s   d i s [ u ] [ 4 ] + d i s [ v ] [ 3 ] + w = d i s [ y 2 ] [ 3 ] dis[u][1]+dis[v][2]+w=dis[y1][1] \:ans \:dis[u][4]+dis[v][3]+w=dis[y2][3] dis[u][1]+dis[v][2]+w=dis[y1][1]ansdis[u][4]+dis[v][3]+w=dis[y2][3]
As long as one of the two is satisfied, this edge is added to the shortest path graph of the common part
Because the shortest path diagram is a D A G DAG DAG, so just run through the topology to find this D A G DAG The longest chain of DAG is OK

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF = 1e9+7;
const int N = 1505;
struct edge
{
	int y,next;
	LL v;
}e[N*N];
struct T
{
	int x,y,v;
}S[N*N];
struct node
{
	int id,v;
};
bool operator <(const node &x,const node &y)
{
	return x.v>y.v;
}
int n,m,X1,X2,Y1,Y2;
priority_queue<node> q;
int link[N],t=0;
void add(int x,int y,int v)
{
	t++;
	e[t].y=y;
	e[t].v=v;
	e[t].next=link[x];
	link[x]=t;
}
LL dis[N][5];
bool vis[N];
node change(int x,LL v)
{
	node T;
	T.id=x;
	T.v=v;
	return T;
}
void Dij(int st,int opt)
{
	for(int i=1;i<=n;i++)
	{
		dis[i][opt]=INF;
		vis[i]=0;
	}
	dis[st][opt]=0;

	q.push(change(st,0));
	while(!q.empty())
	{
		node tmp=q.top();
		q.pop();
		int x=tmp.id;
		if(vis[x]) continue;
		vis[x]=1;
		for(int i=link[x];i;i=e[i].next)
		{
			int y=e[i].y;

			if(dis[x][opt]+e[i].v<dis[y][opt])	
			{
				dis[y][opt]=dis[x][opt]+e[i].v;			
				q.push(change(y,dis[y][opt]));
			}
		}
	}
}
int deg[N],judge[N];
LL Len[N],ans;
void Scan()
{
	for(int i=1;i<=2*m;i++)
	{
		int x=S[i].x,y=S[i].y,v=S[i].v;
		if(dis[x][1]+v+dis[y][2]==dis[Y1][1]&&(dis[x][3]+v+dis[y][4]==dis[Y2][3]||dis[x][4]+v+dis[y][3]==dis[Y2][3]))
		{
			add(x,y,v);	
			judge[x]=judge[y]=1;
			deg[y]++;			
		}
	}
}
queue<int> Q;
void Topsort()
{
	for(int i=1;i<=n;i++)
	{
		if(!deg[i]&&judge[i])
		{
			Q.push(i);
		}
	} 
	while(!Q.empty())
	{
		int x=Q.front();
		Q.pop();
		for(int i=link[x];i;i=e[i].next)
		{
			int y=e[i].y;
			if(deg[y]<=0) continue;
			Len[y]=max(Len[x]+e[i].v,Len[x]);
			deg[y]--;
			if(deg[y]==0)
			{
				ans=max(ans,Len[y]);
				Q.push(y);
			}
		}
	}
}
inline int read()
{
	int X=0; bool flag=1; char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') flag=0; ch=getchar();}
	while(ch>='0'&&ch<='9') {X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();}
	if(flag) return X;
	return ~(X-1);
}
int main()
{
	n=read();
	m=read();
	X1=read();
	Y1=read();
	X2=read();
	Y2=read();
	for(int i=1;i<=m;i++)
	{
		int x,y,v;
		x=read();
		y=read();
		v=read();
		add(x,y,v);
		add(y,x,v);
		S[i].x=x;
		S[i].y=y;
		S[i].v=v;
		S[i+m].x=y;
		S[i+m].y=x;
		S[i+m].v=v;
	}
	Dij(X1,1);
	Dij(Y1,2);
	Dij(X2,3);
	Dij(Y2,4);
	t=0;
	memset(link,0,sizeof(link));
	Scan();
	Topsort();
	cout<<ans;
	return 0;
}