P2149 60pts求助
查看原帖
P2149 60pts求助
557510
AzureHair楼主2023/5/11 19:14

调不出来了救命啊

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,x11,y11,x22,y22,cnt1=0,cnt2=0,head[1510],head1[1510],dis[5][1510],vis[1510],rd[1510],l1=1,l2=1,len[1510],ans=0;
struct node
{
	int next,to,v;
}e[600010],e1[600010];
struct node1
{
	int s,x;
	node1(int s,int x):s(s),x(x) {}
	bool operator <(const node1 &a) const
	{
		return s>a.s;
	}
};
queue <int> q1;
priority_queue <node1> q;
void add(int from,int to,int v)
{
	e[++cnt1].next=head[from];
	e[cnt1].to=to;
	e[cnt1].v=v;
	head[from]=cnt1;
}
void add2(int from,int to,int v)
{
	e1[++cnt2].next=head1[from];
	e1[cnt2].to=to;
	e1[cnt2].v=v;
	head1[from]=cnt2;
	rd[to]++;
}
void djs(int k,int x)
{
	memset(vis,0,sizeof(vis));
	dis[k][x]=0;
	q.push(node1(0,x));
	while(!q.empty())
	{
		//cout<<114<<endl;
		node1 tmp=q.top();
		q.pop();
		int pos=tmp.x;
		//cout<<pos<<endl;
		vis[pos]=1;
		for(int i=head[pos];i;i=e[i].next)
		{
			//cout<<e[i].to<<endl;
			if(dis[k][pos]+e[i].v<dis[k][e[i].to])
			{
				dis[k][e[i].to]=dis[k][pos]+e[i].v;
				if(!vis[e[i].to])
				{
					q.push(node1(dis[k][e[i].to],e[i].to));
				}
			}
		}
	}
	return ;
}
void topo()
{
	for(int i=1;i<=n;i++)
	{
		if(rd[i]==0)
		{
			q1.push(i);
		}
	}
	while(!q1.empty())
	{
		int pos=q1.front();
		q1.pop();
		for(int i=head1[pos];i;i=e1[i].next)
		{
			rd[e1[i].to]--;
			len[e1[i].to]=max(len[e1[i].to],len[pos]+e1[i].v);
			if(rd[e1[i].to]==0)
			{
				q1.push(e1[i].to);
			}
		}
	}
}
signed main()
{
	cin>>n>>m>>x11>>y11>>x22>>y22;
	memset(dis,0x3f3f3f3f,sizeof(dis));
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		cin>>x>>y>>z;
		add(x,y,z);add(y,x,z);
	}
	djs(1,x11);djs(2,y11);djs(3,x22);djs(4,y22);
	//cout<<114<<endl;
	for(int i=1;i<=n;i++)
	{
		for(int j=head[i];j;j=e[j].next)
		{
			if(dis[1][i]+e[j].v+dis[2][e[j].to]==dis[1][y11]&&dis[3][i]+e[j].v+dis[4][e[j].to]==dis[3][y22])
			{
				add2(i,e[j].to,e[j].v);
			}
		}
	}
	topo();
	cnt2=0;
	memset(head1,0,sizeof(head1));
	memset(rd,0,sizeof(rd));
	memset(len,0,sizeof(len));
	for(int i=1;i<=n;i++)
	{
		ans=max(ans,len[i]);
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=head[i];j;j=e[j].next)
		{
			if(dis[1][i]+e[j].v+dis[2][e[j].to]==dis[1][y11]&&dis[4][i]+e[j].v+dis[3][e[j].to]==dis[3][y22])
			{
				add2(i,e[j].to,e[j].v);
			}
		}
	}
	topo();
	for(int i=1;i<=n;i++)
	{
		ans=max(ans,len[i]);
	}
	cout<<ans<<endl;
	return 0;
}
2023/5/11 19:14
加载中...