救救孩子,WA了一个点,死活调不出来
查看原帖
救救孩子,WA了一个点,死活调不出来
376137
Lazy_Labs楼主2022/8/31 22:50

能否有大佬HACK或者帮忙找出问题,十分感谢!

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout)
#define dbout cerr<<"[DeBug]:"
#define mem(x,y) memset(x,y,sizeof(x))
inline int read()
{
 	int x(0),f(1);char c=getchar();
    while(c>'9'||c<'0')f=c=='-'?-1:1,c=getchar();
    while(c>='0'&&c<='9')x=x*10+c-48,c=getchar();
	return f*x;
}
const int N=1510,M=10010;
//int head[N],nxt[M<<1],to[M<<1],val[M<<1],tot;
//void add(int x,int y,int z)
//{
//	nxt[++tot]=head[x];head[x]=tot;to[tot]=y;val[tot]=z;
//	nxt[++tot]=head[y];head[y]=tot;to[tot]=x;val[tot]=z;
//}
int mp[N][N];
int f[N];bool vis[N];
int n,m;
int s1,t1,s2,t2;
void dij(int s)
{
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;i++)f[i]=mp[s][i];
	f[s]=0;
	vis[s]=1;
	for(int i=1;i<n;i++)
	{
		int minn=INT_MAX,nw;
		for(int j=1;j<=n;j++)if(!vis[j]&&f[j]<minn)
		minn=f[j],nw=j;
		vis[nw]=1;
		for(int j=1;j<=n;j++)if(mp[nw][j]!=2139062143)
		f[j]=min(f[j],f[nw]+mp[nw][j]);
	}
}
bool st1[N][N];
void rev(int x)
{
	vis[x]=1;
	for(int i=1;i<=n;i++)if(f[i]+mp[x][i]==f[x])
	{st1[i][x]=1;if(!vis[i])rev(i);}
}
bool st2[N][N];int du[N];
void rve(int x)
{
	vis[x]=1;
	for(int i=1;i<=n;i++)if(f[i]+mp[x][i]==f[x])
	{st2[i][x]=1;du[x]++;if(!vis[i])rve(i);}
}
queue<int>q;
int f2[N];
int topsort()
{
	memset(f,0,sizeof(f));
	q.push(s2);
	while(!q.empty())
	{
		int x=q.front();q.pop();
		for(int i=1;i<=n;i++)if(st2[x][i])
		{
			du[i]--;
			if(st1[x][i])f[i]=max(f[i],f[x]+mp[x][i]);else f[i]=f[x];
			if(st1[i][x])f2[i]=max(f2[i],f2[x]+mp[i][x]);else f2[i]=f2[x];
			if(!du[i])q.push(i);
		}
	}
	return max(f[t2],f2[t2]);
}
int main()
{
	n=read(),m=read();s1=read();t1=read();s2=read();t2=read();
	memset(mp,127,sizeof(mp));
	for(int i=1;i<=m;i++)
	{
		int x=read(),y=read(),z=read();
		mp[x][y]=mp[y][x]=z;
	}
	dij(s1);memset(vis,0,sizeof(vis));rev(t1);
	dij(s2);memset(vis,0,sizeof(vis));rve(t2);
	printf("%d",topsort());
	return 0;
}
2022/8/31 22:50
加载中...