Description

最近,Elaxia和w**的关系特别好,他们很想整天在一起,但是大学的学习太紧张了,他们 必须合理地安排两个人在一起的时间。Elaxia和w**每天都要奔波于宿舍和实验室之间,他们 希望在节约时间的前提下,一起走的时间尽可能的长。 现在已知的是Elaxia和w**所在的宿舍和实验室的编号以及学校的地图:地图上有N个路 口,M条路,经过每条路都需要一定的时间。 具体地说,就是要求无向图中,两对点间最短路的最长公共路径。

Input

第一行:两个整数N和M(含义如题目描述)。 第二行:四个整数x1、y1、x2、y2(1 ≤ x1 ≤ N,1 ≤ y1 ≤ N,1 ≤ x2 ≤ N,1 ≤ ≤ N),分别表示Elaxia的宿舍和实验室及w**的宿舍和实验室的标号(两对点分别 x1,y1和x2,y2)。 接下来M行:每行三个整数,u、v、l(1 ≤ u ≤ N,1 ≤ v ≤ N,1 ≤ l ≤ 10000),表 u和v之间有一条路,经过这条路所需要的时间为l。 出出出格格格式式式::: 一行,一个整数,表示每天两人在一起的时间(即最长公共路径的长度)。

Output

一行,一个整数,表示每天两人在一起的时间(即最长公共路径的长度)

如果你没有意识到两个人即使对头走也算的话(既一个从x1到y1,一个从y2到x2)那你可以和我一样吐槽出题人的语文功底了。

(如果不反过来做的话建了两条边,就出环了)

先跑四次最短路

然后我们枚举所有满足条件的边Ei,j,使

dis[x1][i]+dis[j][y1]+Ei,j等于dis[x1][y1]且dis[x2][i]+dis[j][y2]+Ei,j等于dis[x2][y2]

翻译成人话也就是枚举一条公共边,使这条公共边在x1到y1的最短路上且在x2到y2的最短路上。

然后建一个新图,把这条边换成有向边加到图上去。

最后就是拓扑排序跑最长路。

注意还要反过来再做一遍(dis[x1][i]+dis[j][x2]+Ei,j = dis[y2][i]+dis[j][x2]+Ei,j)

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<iterator>
#include<queue>
#include<utility>
using namespace std;

int g[1510][1510]={0};
int edgenum,nodenum,l1,l2,h1,h2,fx,tx,wx,ans=0;
int dis[5][1510]={0};
bool pub[1510]={false};
//toposort
struct ed
{
	int pre,to,w;
}edge[100010]={0};
int inw[1510]={0},pointer[1510]={0},at=0,nodev[1510]={0};
queue<int> quet;

inline void Insert()
{
	at++;
	edge[at].pre=pointer[fx];
	edge[at].to=tx;
	edge[at].w=wx;
	pointer[fx]=at;
}

inline void SPFA(int source,int p)
{
	queue<int> que; int cache1; bool vis[1510]={0};
	
	dis[p][source]=0; que.push(source);
	while (!que.empty())
	{
		cache1=que.front(); que.pop();
		vis[cache1]=false;
		for (int i=1;i<=nodenum;i++) if (g[cache1][i])
		{
			if (dis[p][i]>dis[p][cache1]+g[cache1][i])
			{
				dis[p][i]=dis[p][cache1]+g[cache1][i];
				if (!vis[i])
				{
					vis[i]=true;
					que.push(i);
				}
			}
		}
	}
}

inline int toposort()
{
	int res=0;
	memset(nodev,0,sizeof(nodev));
	int cache1,prex;
	for (int i=1;i<=nodenum;i++) if (inw[i]==0 && pointer[i]!=0) quet.push(i);
	while (!quet.empty())
	{
		cache1=quet.front(); quet.pop();
		prex=pointer[cache1];
		res=max(res,nodev[cache1]);
		while (prex)
		{
			inw[edge[prex].to]--;
			if (!inw[edge[prex].to])
			{
				nodev[edge[prex].to]=nodev[cache1]+edge[prex].w;
				quet.push(edge[prex].to);
			}
			prex=edge[prex].pre;
		}
	}
	return res;
}

int main()
{
	memset(dis,0x3f,sizeof(dis));
	scanf("%d%d",&nodenum,&edgenum);
	scanf("%d%d%d%d",&h1,&l1,&h2,&l2);
	for (int i=1;i<=edgenum;i++)
	{
		scanf("%d%d%d",&fx,&tx,&wx);
		g[fx][tx]=g[tx][fx]=wx;
	}
	
	SPFA(h1,1); SPFA(l1,2); SPFA(h2,3); SPFA(l2,4);
	
	for (int i=1;i<=nodenum;i++)
	{
		for (int j=1;j<=nodenum;j++) if (g[i][j])
		{
			if (dis[1][i]+dis[2][j]+g[i][j]==dis[1][l1] && dis[3][i]+dis[4][j]+g[i][j]==dis[3][l2])
			{
				fx=i; tx=j; wx=g[i][j];
				Insert();
				inw[j]++;
			}
		}
	}
	ans=toposort();
	memset(edge,0,sizeof(edge));
	memset(inw,0,sizeof(inw));
	at=0;
	for (int i=1;i<=nodenum;i++)
	{
		for (int j=1;j<=nodenum;j++) if (g[j][i])
		{
			if (dis[1][j]+dis[2][i]+g[j][i]==dis[1][l1] && dis[3][i]+dis[4][j]+g[i][j]==dis[3][l2])
			{
				fx=i; tx=j; wx=g[i][j];
				Insert();
				inw[j]++;
			}
		}
	}
	ans=max(ans,toposort());

	printf("%d\n",ans);
	return 0;
}
分类:

发表评论

电子邮件地址不会被公开。 必填项已用*标注