专栏首页wym[SDOI2009]Elaxia的路线 最短路+拓扑排序

[SDOI2009]Elaxia的路线 最短路+拓扑排序

[SDOI2009]Elaxia的路线

题意明确求两个人的最短路最长公共路径

1.所求是一段链,若答案不是连续路径,则两人会有再次相遇的情况,若有再次相遇则对另一方就不是最短路;

2.我们要求最长公共路径,就对每一个点跑最短路,也就是跑4遍,再把两个人重合的地方构建一个新图

如何判断重合,对于x1的最短路 有 dis[1][1~n],同理有dis[2][1~n],dis[3][1~n],dis[4][1~n].

对于一条边 u 到 v 长 w ,重合的条件是 dis[1][u] + dis[2][v] + w = dis[1][y1];这是第一个人的边满足是最短路的条件

第二个人同理 dis[3][u] + dis[4][v] + w = dis[3][y2]。  同时满足这两个条件就是重合的最短路

3.注意方向,由于第二次构图考虑方向,要把两个人同时同向和同时反向分开算。 

#include <bits/stdc++.h>
using namespace std;
#define INF 0x7fffffff
const int N = 1550;
int dis[5][N];
int head1[N],head2[N];
int len[N];
int cnt1,cnt2;
int n,m;
struct Edge{
	int w,v,nxt;
};
Edge edge1[N*N],edge2[N*N];
int in[N],book[N];
void add1(int u,int v,int w){
	cnt1++;
	edge1[cnt1].v = v;
	edge1[cnt1].w = w;
	edge1[cnt1].nxt = head1[u];
	head1[u] = cnt1;
}
void add2(int u,int v,int w){
	cnt2++;
	edge2[cnt2].v = v;
	edge2[cnt2].w = w;
	edge2[cnt2].nxt = head2[u];
	head2[u] = cnt2;
	in[v]++;
}
void spfa(int id,int s){
	memset(book,0,sizeof(book));
	queue<int> q;while(!q.empty())q.pop();
	for(int i=1;i<=n;i++)
	dis[id][i] = INF;
	dis[id][s]=0; book[s]=1; q.push(s);
	while(!q.empty()){
		int u=q.front(); book[u]=0; q.pop();
		for(int w,v,i=head1[u];i;i=edge1[i].nxt){
			v = edge1[i].v; w = edge1[i].w+dis[id][u];
			if(dis[id][v]>w){
				dis[id][v]=w;
				if(!book[v]) book[v]=1,q.push(v);
			}
		}
	}	
}
void topo(){
	queue<int> q;while(!q.empty())q.pop();
	for(int i=1;i<=n;i++)if(!in[i])q.push(i);
	while(!q.empty()){
		int u = q.front(); q.pop();
		for(int v,w,i=head2[u];i;i=edge2[i].nxt){
			v = edge2[i].v; w = edge2[i].w + len[u];
			len[v] = max(len[v],w);
			in[v]--;
			if(!in[v])q.push(v);
		}
	}
}
int main()
{
	 scanf("%d %d",&n,&m);
	int x1,y1,x2,y2;
	scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
	for(int i=1;i<=m;i++){
		int u,v,w;
		scanf("%d %d %d",&u,&v,&w);
		add1(u,v,w);
		add1(v,u,w);
	}
	 
	spfa(1,x1); spfa(2,y1); 
	spfa(3,x2); 
	spfa(4,y2);
//	printf("%d",dis[3][4]);
//	printf("%d\n",dis[3][8]);
	for(int i=1;i<=n;i++)
	{
		for(int j=head1[i];j;j=edge1[j].nxt)
		{	int v = edge1[j].v,w = edge1[j].w;
			if(dis[1][i]+dis[2][v]+w==dis[1][y1]){
				if(dis[3][i]+dis[4][v]+w==dis[3][y2])
				add2(i,v,w);
			}	
		}
	}
	topo();
	int ans = 0;
	for(int i=1;i<=n;i++)ans=max(ans,len[i]);
	//printf("%d\n",ans);
	memset(len,0,sizeof(len));
	memset(in,0,sizeof(in));
	for(int i=1;i<=n;i++)
	{
		for(int j=head1[i];j;j=edge1[j].nxt)
		{	int v = edge1[j].v,w = edge1[j].w;
			if(dis[1][i]+dis[2][v]+w==dis[1][y1]){
				if(dis[3][v]+dis[4][i]+w==dis[3][y2])
				add2(i,v,w);
			}	
		}
	}
	topo();	
	for(int i=1;i<=n;i++)ans=max(ans,len[i]);
	printf("%d\n",ans);
	return 0;
 } 

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • HDU1542 Atlantis 线段树+扫描线

    用户2965768
  • HDU 2586 How far away ?(最长公共祖先 LCA模板题)

    离线版本的思路是:每个点都把与它有关的查询放进它的那个vector里,然后对这棵树进行一次dfs,在dfs的过程中直接得出所有查询的答案,复杂度是O(n+q)。

    用户2965768
  • 南京网络预选赛 The Preliminary Contest for ICPC Asia Nanjing 2019 F 主席树 或 滑动窗口

    查询区间 [ id-k,id+k] 小于 val 的个数 num , 再在该区间查询第 num 大的数。

    用户2965768
  • P2746 [USACO5.3]校园网Network of Schools

    题目描述 一些学校连入一个电脑网络。那些学校已订立了协议:每个学校都会给其它的一些学校分发软件(称作“接受学校”)。注意即使 B 在 A 学校的分发列表中, A...

    attack
  • 最长公共子序列

    咱们就不拐弯抹角了,如题,需要你做的就是写一个程序,得出最长公共子序列。 tip:最长公共子序列也称作最长公共子串(不要求连续),英文缩写为LCS(Longes...

    书童小二
  • 【POJ 2886】Who Gets the Most Candies?

    约瑟夫问题的升级版,每次出去的是前一个出去的人位置+手上的数字(正往前,负往后)。第i个出去的人拿的糖是i的约数的个数。求拿糖最多的人和他的糖果数。

    饶文津
  • 特殊回文数-Java

    码农笔录
  • 2019HDU多校赛第二场 HDU 6599 I Love Palindrome String(回文树+哈希判回文)

    题意:多组输入string,判断长度从1 到 len(string)的字串中有 多少 回文串,且前 一半也为回文

    用户2965768
  • 547. Friend Circles

    There are N students in a class. Some of them are friends, while some are not. T...

    眯眯眼的猫头鹰
  • BZOJ 3714: [PA2014]Kuglarz(最小生成树)

    Description 魔术师的桌子上有n个杯子排成一行,编号为1,2,…,n,其中某些杯子底下藏有一个小球,如果你准确地猜出是哪些杯子,你就可以获得奖品。花...

    attack

扫码关注云+社区

领取腾讯云代金券