社区讨论

求助!!55pts RE 5个点

P2149[SDOI2009] Elaxia的路线参与者 2已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@lod1xdte
此快照首次捕获于
2023/10/30 23:25
2 年前
此快照最后确认于
2023/11/05 09:44
2 年前
查看原帖
CPP
#include<iostream>
#include<cstdio>
#include<map>
#include<cstring>
#include<queue>
#define max(a,b) (a>b?a:b)
#define re register int
using namespace std;
int n,m,a,b,c,d,ans;
inline int read()
{
	int x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')
		ch=getchar();
	while(ch>='0'&&ch<='9')
	{
		x=(x<<3)+(x<<1)+ch-'0';
		ch=getchar();
	}
	return x;
}
const  int N=1500+5,M=1e4+5;
struct tq
{
	int to,next,w,flag;
}q[M<<1],t[M<<1];

int head[N],cnt;
inline void add(int u,int v,int w)
{
	q[++cnt].to=v;
	q[cnt].next=head[u];
	q[cnt].w=w;
	head[u]=cnt;
}

struct node
{
	int dis,x;
	inline bool operator < (const node &a) const
	{
		return dis>a.dis;
	}
};


int dis[N][4],vis[N];
inline void dijkstra(int s,int cnt)
{	
	dis[s][cnt]=0;
	memset(vis,0,sizeof(vis));
	priority_queue <node> que;
	que.push((node){0,s});
	while(!que.empty())
	{
		int u=que.top().x;
		que.pop();
		if(vis[u])
			continue;
		vis[u]=1;
		for(re i=head[u];i;i=q[i].next)
		{
			re v=q[i].to,w=q[i].w;
			if(dis[u][cnt]+w<dis[v][cnt])
			{
				dis[v][cnt]=dis[u][cnt]+w;	
				que.push((node){dis[v][cnt],v});
			}				
		}		
	}
}

int _head[N],_cnt,flag[N];
inline void _add(int u,int v,int w)
{
	t[++_cnt].to=v;
	t[_cnt].next=_head[u];
	t[_cnt].w=w;
	_head[u]=_cnt;
	flag[u]=flag[v]=1;
}

inline void rebuild()
{
	for(re u=1;u<=n;++u)
		for(re i=head[u];i;i=q[i].next)
		{
			re v=q[i].to,w=q[i].w;	
			if(dis[u][0]+w+dis[v][1]==dis[b][0])
			{
				if(dis[u][2]+w+dis[v][3]==dis[d][2])
					_add(u,v,w);
				if(dis[v][2]+w+dis[u][3]==dis[d][2])
					_add(v,u,w);
			}			
		}
}

int f[N];
inline int dfs(int u)
{
	if(f[u])
		return f[u];
	for(re i=_head[u];i;i=t[i].next)
	{
		re v=t[i].to,w=t[i].w;
		f[u]=max(f[u],dfs(v)+w);
	}
	return f[u];
}

int main()
{
	memset(dis,127,sizeof(dis));
	n=read();
	m=read();
	a=read(),b=read(),c=read(),d=read();
//	printf("\n%d %d %d %d\n",a,b,c,d);
	for(re i=1;i<=m;++i)
	{
		re u=read(),v=read(),w=read();
		add(u,v,w);
		add(v,u,w);	
	}
	dijkstra(a,0);
	dijkstra(b,1);	
	dijkstra(c,2);		
	dijkstra(d,3);	
	rebuild();	
	for(re i=1;i<=n;++i)
		if(flag[i]&&!f[i])
			dfs(i);
	for(re i=1;i<=n;++i)	
		ans=max(ans,f[i]);
	printf("%d",ans);
}

回复

1 条回复,欢迎继续交流。

正在加载回复...