两次dijkstra+pre(vector数组)记录最短路+找最长重合

#include <bits/stdc++.h> 
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define res register int 
const int maxn=1505;
vector<int> v[maxn],pre[2][maxn];
//v是邻接矩阵   pre[1]是第一个人从实验室到宿舍的最短路上的记录，记录每一个最短路上的点前一个节点。因为可能有多个，所以用的是vector
//pre[2]表示的就是第二个人实验室到宿舍最短路的记录 
int N,M,b1,e1,b2,e2,dis[maxn][maxn];//dis是邻接矩阵，方便直接获取两个点之间的距离 
int flag[maxn];
int Max=0;
struct Node{
	int num,sum;
};
bool operator<(const Node a,const Node b){
	return b.sum>a.sum;
}

void dijkstra(int s,int cnt)
{
	int len[maxn],vis[maxn];
	memset(len,inf,sizeof(int)*(N+2)); 
	memset(vis,0,sizeof(int)*(N+2));
	len[s]=0;
	priority_queue<Node> q;
	q.push((Node){s,0});
	int size;
	while(!q.empty()){
		Node now=q.top();
		q.pop();
		if(vis[now.num]) continue;
		vis[now.num]=1;
		int size=v[now.num].size();
		for(res i=0;i<size;i++){
			int y=v[now.num][i];
			if(len[y]>len[now.num]+dis[now.num][y]){
				len[y]=len[now.num]+dis[now.num][y];
				pre[cnt][y].clear();
				pre[cnt][y].push_back(now.num);
				if(!vis[y]) q.push((Node){y,len[y]});
			}else if(len[y]==len[now.num]+dis[now.num][y]){
				pre[cnt][y].push_back(now.num);
			}
		}
	}
}
void dfs1(int x){//对第一个实验室和宿舍，从终点开始dfs，玲所有最短路上的点i，都有flag【i】 =1 
	if(b1==x){
		flag[x]=1;
		return;
	}else{
		flag[x]=1;
		for(res i=0;i<pre[0][x].size();i++){
			int fa=pre[0][x][i];
			dfs1(fa);
		}		
	}
}

void dfs2(int x,int sum){//对二个实验室和宿舍反着利用pre[1]进行遍历
//如果flag[x]==flag[fa] && flag[fa]==1 说明当前路是第一个宿舍到实验室之间的最短路，就把这个边加到sum上
//最后我们比较取sum较大的  
	if(b2==x){
		Max=max(Max,sum);
		return;
	}else{
		int size=pre[1][x].size();
		for(res i=0;i<pre[1][x].size();i++){
			int fa=pre[1][x][i];
			if(1==flag[x]&&1==flag[fa])
				sum+=dis[x][fa];
			dfs2(fa,sum);
			if(1==flag[x]&&1==flag[fa])
				sum-=dis[x][fa];
		}		
	}
}

int main()
{
	cin>>N>>M;
	cin>>b1>>e1>>b2>>e2;
	int from,to,val;
	for(res i=0;i<M;i++){
		scanf("%d%d%d",&from,&to,&val);
		v[from].push_back(to);
		v[to].push_back(from);
		dis[from][to]=dis[to][from]=val;
	}	
	dijkstra(b1,0);
	dijkstra(b2,1);
//	for(res i=1;i<=N;i++){
//		for(res j=0;j<pre[0][i].size();j++){
//			printf("%d ",pre[0][i][j]);
//		} 
//		printf("\n"); 
//	}
	dfs1(e1);
	dfs2(e2,0);
	printf("%d",Max);
	return 0;	
}