tarjan+spfaWA掉,54分,求大佬调试,玄3关
查看原帖
tarjan+spfaWA掉,54分,求大佬调试,玄3关
77612
_扶笙_楼主2024/9/20 13:09
#include<bits/stdc++.h>
#define int long long 
using namespace std;
int a[500010],b[500010],c[500010],d[500010],vis[500010],low[500010],dfn[500010],dis[500010];
int u[500010],v[500010],que[1000010],x,y,cnt,num,belong[500010],tim,st[500010],top,to;
int val[500010],bar[500010],n,m,start,P,h,t,ans;
inline void add(int x,int y)
{
	a[++cnt]=y;b[cnt]=d[x];d[x]=cnt;
}
inline void dfs(int x)
{
	vis[x]=1;tim++;dfn[x]=low[x]=tim;st[++top]=x;
	for(int i=d[x];i;i=b[i])
		{
			to=a[i];
			if(vis[to]==0)	dfs(to),low[x]=min(low[x],low[to]);
			else	if(vis[to]==1)	low[x]=min(low[x],dfn[to]);
		}
	if(dfn[x]==low[x])
		{
			y=st[top];top--;num++;cout<<num<<" "<<y<<endl;
			while(y)
				{
					belong[y]=num;vis[y]=2;val[num]+=c[y];
					if(x==y) break;
					y=st[top];top--;
				}
		}
}
signed main()
{
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++)	cin>>u[i]>>v[i],add(u[i],v[i]);
	for(int i=1;i<=n;i++)   cin>>c[i];
	cin>>start>>P;
	for(int i=1;i<=P;i++)	cin>>bar[i];
	for(int i=1;i<=n;i++)
		if(vis[i]==0)	dfs(i);
	for(int i=1;i<=m;i++) a[i]=b[i]=d[i]=0;cnt=0;
	for(int i=1;i<=m;i++)
		{
			x=belong[u[i]];y=belong[v[i]];
			if(x!=y)	add(x,y);
		}
	memset(vis,0,sizeof(vis));
	h=1;t=1;que[t]=belong[start];dis[que[t]]=val[que[t]];vis[que[t]]=1;
	while(h<=t)
		{
			x=que[h];
			for(int i=d[x];i;i=b[i])
				{
					to=a[i];
					if(dis[to]<dis[x]+val[to])
						{
							dis[to]=dis[x]+val[to];
							if(!vis[to])  t++,que[t]=to,vis[to]=1;
						}
				}
			h++;
		}
	for(int i=1;i<=P;i++) ans=max(ans,dis[belong[bar[i]]]);
	cout<<ans<<endl;
	return 0;
}
2024/9/20 13:09
加载中...