记录编号	320282	评测结果	AAAAAAAAAA
题目名称	Elaxia的路线	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.638 s
提交时间	2016-10-11 20:31:24	内存使用	46.13 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define INF ((~((1)<<(31)))>>(1))
using namespace std;
const int maxn=1510;
struct edge{int from,to,dis,prev;}e[3000010];
struct node{
	int x,dis;
	node(int x,int dis):x(x),dis(dis){}
	bool operator<(const node &a)const{return dis>a.dis;}
};
void addedge(int,int,int,int*);
void Dijkstra(int,int*);
void SPFA();
int dis[maxn],disu[maxn],disv[maxn],disz[maxn],disw[maxn];
int n,m,u,v,z,w,x,y,l,last[maxn]={0},DAGlast[maxn]={0},len=0,ans=0;
bool vis[maxn],inq[maxn];
int main(){
#define MINE
#ifdef MINE
	freopen("travel!.in","r",stdin);
	freopen("travel!.out","w",stdout);
#endif
	scanf("%d%d%d%d%d%d",&n,&m,&u,&v,&z,&w);
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&x,&y,&l);
		addedge(x,y,l,last);
		addedge(y,x,l,last);
	}
	Dijkstra(u,disu);
	Dijkstra(v,disv);
	Dijkstra(z,disz);
	Dijkstra(w,disw);
	//for(int i=1;i<=n;i++)printf("i=%d disu=%d disv=%d disz=%d disw=%d\n",i,disu[i],disv[i],disz[i],disw[i]);
	memset(DAGlast,0,sizeof(DAGlast));
	for(int i=1;i<=(m<<1);i++){
		//printf("checking (%d,%d) dis1=%d dis2=%d dis=%d\n",e[i].from,e[i].to,disu[e[i].from],disv[e[i].to],e[i].dis);
		//printf("another (%d,%d) dis1=%d dis2=%d dis=%d\n",e[i].from,e[i].to,disz[e[i].from],disw[e[i].to],e[i].dis);
		if(disu[e[i].from]+e[i].dis+disv[e[i].to]==disu[v]&&disz[e[i].from]+e[i].dis+disw[e[i].to]==disz[w])addedge(e[i].from,e[i].to,e[i].dis,DAGlast);
	}
	SPFA();
	//ans=max(ans,dis[w]);
	for(int i=1;i<=n;i++)ans=max(ans,dis[i]);
	memset(DAGlast,0,sizeof(DAGlast));
	for(int i=1;i<=(m<<1);i++){
		//printf("checking (%d,%d) dis1=%d dis2=%d dis=%d\n",e[i].from,e[i].to,disu[e[i].from],disv[e[i].to],e[i].dis);
		//printf("another (%d,%d) dis1=%d dis2=%d dis=%d\n",e[i].from,e[i].to,disw[e[i].from],disz[e[i].to],e[i].dis);
		if(disu[e[i].from]+e[i].dis+disv[e[i].to]==disu[v]&&disw[e[i].from]+e[i].dis+disz[e[i].to]==disw[z])addedge(e[i].from,e[i].to,e[i].dis,DAGlast);
	}
	SPFA();
	for(int i=1;i<=n;i++)ans=max(ans,dis[i]);
	printf("%d",ans);
#ifndef MINE
	printf("\n--------------------DONE--------------------\n");
	for(;;);
#endif
	return 0;
}
void addedge(int x,int y,int z,int *last){
	///*if(last==DAGlast)*/printf("addedge(%d,%d,%d)\n",x,y,z);
	e[++len].from=x;
	e[len].to=y;
	e[len].dis=z;
	e[len].prev=last[x];
	last[x]=len;
}
void Dijkstra(int x,int *dis){
	memset(dis,63,sizeof(int)*maxn);
	dis[x]=0;
	memset(vis,0,sizeof(vis));
	priority_queue<node>q;
	q.push(node(x,0));
	while(!q.empty()){
		x=q.top().x;
		q.pop();
		if(vis[x])continue;
		vis[x]=true;
		//printf("dis[%d]=%d\n",x,dis[x]);
		for(int i=last[x];i;i=e[i].prev)if(!vis[e[i].to]&&dis[e[i].to]>dis[x]+e[i].dis){
			dis[e[i].to]=dis[x]+e[i].dis;
			q.push(node(e[i].to,dis[e[i].to]));
		}
	}
}
void SPFA(){
	int x;
	queue<int>q;
	memset(dis,0,sizeof(dis));
	for(int i=1;i<=n;i++){
		q.push(i);
		inq[i]=true;
	}
	while(!q.empty()){
		x=q.front();
		q.pop();
		inq[x]=false;
		//printf("%d ",x);
		for(int i=DAGlast[x];i;i=e[i].prev)if(dis[e[i].to]<dis[x]+e[i].dis){
			dis[e[i].to]=dis[x]+e[i].dis;
			if(!inq[e[i].to]){
				inq[e[i].to]=true;
				q.push(e[i].to);
			}
		}
	}//printf("\n");
}