记录编号	291594	评测结果	AAAAAAAAAA
题目名称	Elaxia的路线	最终得分	100
用户昵称	LOSER	是否通过	通过
代码语言	C++	运行时间	0.856 s
提交时间	2016-08-07 19:08:20	内存使用	12.52 MiB

#include<cstdio>
#include<queue>
#include<cstring>
#define maxm 700010
#define maxn 1510
using namespace std;
int n,m;
struct Edge{int from,to,dis,next;}e[maxm],r[maxm];
int len,head[maxm];
void Insert(int x,int y,int z){
	e[++len].to=y;
	e[len].from=x;
	e[len].dis=z;
	e[len].next=head[x];
	head[x]=len;
}
struct Node{
	int num,dis;
	Node(int a,int b){num=a;dis=b;}
	bool operator < (const Node & a)
	const {
		return dis>a.dis;
	}
};
int lenth[5][maxn],Time;
void Dijkstra(int x){
	priority_queue<Node> q;
	int dis[maxn]; memset(dis,127/2,sizeof(dis));
	bool flag[maxn]={0};
	dis[x]=0; flag[x]=1;
	q.push(Node(x,dis[x]));
	while(!q.empty()){
		Node temp=q.top(); q.pop();
		int u=temp.num; flag[u]=1;
		for(int i=head[u];i;i=e[i].next){
			int v=e[i].to;
			if(!flag[v]&&dis[v]>dis[u]+e[i].dis){
				dis[v]=dis[u]+e[i].dis;
				q.push(Node(v,dis[v]));
			}
		}
	}
	++Time;
	for(int i=1;i<=n;i++)lenth[Time][i]=dis[i];
}
int s1,s2,t1,t2;
bool Judge(int x){
	int s=e[x].from, t=e[x].to;
	if(e[x].dis+lenth[1][t]+lenth[3][s]==lenth[1][t1]){
		if(e[x].dis+lenth[2][t]+lenth[4][s]==lenth[2][t2])return true;
		if(e[x].dis+lenth[4][t]+lenth[2][s]==lenth[2][t2])return true;
	}	
	return false;
}
int cnt;
void Addedge(int x,int y,int z){
	r[++cnt].to=y;
	r[cnt].from=x;
	r[cnt].dis=z;
	r[cnt].next=head[x];
	head[x]=cnt;
}
#define MAX(a,b) (a>b?a:b)
int num[maxn];
int Dfs(int x){
	//puts("OK");
	if(num[x])return num[x];
	for(int i=head[x];i;i=r[i].next){
		int y=r[i].to;
		num[x]=MAX(Dfs(y)+r[i].dis,num[x]);
	}
	return num[x];
}
bool f[maxm];
int d[maxn];
int MY(){
	freopen("travel!.in","r",stdin); freopen("travel!.out","w",stdout);
	scanf("%d%d",&n,&m);
	scanf("%d%d%d%d",&s1,&t1,&s2,&t2);
	int x,y,z;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&x,&y,&z);
		Insert(x,y,z); Insert(y,x,z);
	}
	Dijkstra(s1); Dijkstra(s2); Dijkstra(t1); Dijkstra(t2);
	memset(head,0,sizeof(head));
	for(int i=1;i<=len;i++)	if(Judge(i)){
		if(lenth[1][e[i].from]<lenth[1][e[i].to]){
			Addedge(e[i].from,e[i].to,e[i].dis);
			d[e[i].to]+=1; 
		}
		else {
			Addedge(e[i].to,e[i].from,e[i].dis);
			d[e[i].from]+=1; 
		}
		f[e[i].from]=1; f[e[i].to]=1;
	}/*建公共有向（近到远）图（图上所有边都为公共边）*/
	/*for(int i=1;i<=cnt;i++){
		printf("%d %d\n",r[i].from,r[i].to);
	}*/
	int ans=0;
	for(int i=1;i<=n;i++){
		if(!f[i])continue;
		if(!d[i]){
			ans=MAX(Dfs(i),ans); 
		}	
	}
	printf("%d\n",ans);
	return 0;
}
int YOU=MY();
int main(){;}