陷入死循环QwQ
查看原帖
陷入死循环QwQ
250699
mot1ve楼主2020/6/14 19:23

运行不出来 大佬看看哪里有问题感激

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int x,y,z,ans=0,n,m,idx1,idx2,w[100010],d[100010],f[100010],vis1[100010],vis2[100010];
int head1[100010],head2[100010];
struct node{
	int nxt,w,to;
}edge1[500010],edge2[500010];
void add1(int u,int v)//建正图 
{
	idx1++;
	edge1[idx1].nxt=head1[u];
	edge1[idx1].to=v;
	edge1[idx1].w=w[v];
	head1[u]=idx1;
}
void add2(int u,int v)//建反图 
{
	idx2++;
	edge2[idx2].nxt=head2[u];
	edge2[idx2].to=v;
	edge2[idx2].w=w[v];
	head2[u]=idx2;
}
void spfa1()//跑正图
{
	memset(d,0x3f3f3f3f,sizeof(d));
	memset(vis1,0,sizeof(vis1));
	queue <int> q1;
	q1.push(1);
	d[1]=w[1];
	vis1[1]=1;
	while(!q1.empty())
	{
		int u=q1.front();
		q1.pop();
		vis1[u]=0;
		for(int i=head1[u];i;i=edge1[i].nxt)
		{
			int v=edge1[i].to;
			if(min(d[u],edge1[i].w)<d[v]);
			{
				d[v]=min(d[u],edge1[i].w);
				if(!vis1[v])
				{
					q1.push(v);
					vis1[v]=1;
				}
			}
		}
    }
}
void spfa2()//跑反图
{
	memset(f,-0x3f3f3f3f,sizeof(f));
	memset(vis2,0,sizeof(vis2));
	queue <int> q2;
	q2.push(n);
	vis2[n]=1;
	f[n]=w[n];
	while(!q2.empty())
	{
		int u=q2.front();
		q2.pop();
		vis2[u]=0;
		for(int i=head2[u];i;i=edge2[i].nxt)
		{
			int v=edge2[i].to;
			if(max(f[u],edge2[i].w)>f[v])
			{
				f[v]=max(f[u],edge2[i].w);
				if(!vis2[v])
				{
					q2.push(v);
				    vis2[v]=1;
				}
			}
		}
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	scanf("%d",&w[i]);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		if(z==1)
		{
			add1(x,y),add2(y,x);
		}
		if(z==2)
		{
			add1(x,y),add1(y,x),add2(y,x),add2(x,y);
		}
	}
	spfa1();
	spfa2();
	for(int i=1;i<=n;i++)
	{
		ans=max(f[i]-d[i],ans);
	}
	cout<<ans;
	return 0;
}
2020/6/14 19:23
加载中...