P4822 AC Code 求助
查看原帖
P4822 AC Code 求助
365654
封禁用户楼主2022/4/3 14:12

rt,我的代码怎么 AC 的?(确实不知道)能 hack 吗?

#include<bits/stdc++.h>
using namespace std;
struct Side
{
	int from;
	int to;
	int cost;
};
bool cmp(Side a,Side b)
{
	if(a.from!=b.from) return a.from<b.from;
	return a.to<b.to;
}
struct Svdt
{
	int dot;
	int val;
	int path[52];
	bool operator<(const Svdt anth)const
	{
		return val<anth.val;
	}
	bool operator>(const Svdt anth)const
	{
		return val>anth.val;
	}
	void operator=(const Svdt anth)
	{
		dot=anth.dot;
		val=anth.val;
		for(int i=0;i<=51;i++)
			path[i]=anth.path[i];
	}
}inition;
void swap(Svdt &a,Svdt &b)
{
	Svdt t;
	t=a,a=b,b=t;
}
Svdt h[4112];
int size;
void initsvdt()
{
	inition.dot=0;
	inition.val=2147483647;
	memset(inition.path,0,sizeof(inition.path));
	for(int i=0;i<=4111;i++)
		h[i]=inition;
	size=0;
}
void ins(Svdt newsvdt)
{
	size++;
	h[size]=newsvdt;
	int npos=size;
	while(npos>1)
	{
		if(h[npos]<h[npos/2])
		{
			swap(h[npos],h[npos/2]);
			npos/=2;
		}
		else break;
	}
}
Svdt top()
{
	if(size==0) return inition;
	return h[1];
}
void del()
{
	if(size==0) return;
	h[1]=h[size];
	h[size]=inition;
	size--;
	int npos=1;
	while(npos*2<=size)
	{
		if(h[npos]>h[npos*2]||h[npos]>h[npos*2+1])
		{
			if(h[npos*2]<h[npos*2+1])
			{
				swap(h[npos],h[npos*2]);
				npos*=2;
			}
			else
			{
				swap(h[npos],h[npos*2+1]);
				npos*=2,npos++;
			}
		}
		else break;
	}
}
int n;
int m;
int sss;
int k;
Side sds[2012];
int sdsbg[52];
int sdscnt[52];
int stpfrom;
int stp[52];
int paths[52][52];
int tmp[52];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie();
    cout.tie();
	cin>>n>>m>>k;
	sss=1;
	m*=2;
	for(int i=1;i<=m;i+=2)
	{
		cin>>sds[i].from>>sds[i].to>>sds[i].cost;
		sds[i+1].from=sds[i].to;
		sds[i+1].to=sds[i].from;
		sds[i+1].cost=sds[i].cost;
	}
 	memset(sdsbg,-1,sizeof(sdsbg));
	memset(sdscnt,0,sizeof(sdscnt));
	sort(sds+1,sds+m+1,cmp);
	int now=0;
	for(int i=1;i<=m;i++)
	{
		if(sds[i].from!=now) now=sds[i].from,sdsbg[sds[i].from]=i,sdscnt[sds[i].from]=1;
		else sdscnt[now]++;
	}
	stpfrom=sss;
	for(int i=1;i<=n;i++)
		stp[i]=2147483647;
	stp[sss]=0;
	int okcnt=1;
	int nding=sss;
	initsvdt();
	while(okcnt<n)
	{
		for(int i=sdsbg[nding],j=1;j<=sdscnt[nding];i++,j++)
		{
			memset(tmp,0,sizeof(tmp));
			for(int j=0;j<=51;j++)
				tmp[j]=paths[nding][j];
			int inspos=51;
			while(inspos>1&&tmp[inspos-1]<sds[i].cost) tmp[inspos]=tmp[inspos-1],inspos--;
			tmp[inspos]=sds[i].cost;
			int ans=0;
			for(int j=1;j<=51;j++)
				ans+=((j<=k)?(tmp[j]/2):(tmp[j]));
			Svdt instion;
			instion.dot=sds[i].to;
			instion.val=ans;
			for(int j=0;j<=51;j++)
				instion.path[j]=tmp[j];
   			ins(instion);
		}
		while(1)
		{
			Svdt nxtnding=top();
			if(nxtnding.val==2147483647)
			{
				okcnt=-okcnt;
				break;
			}
			del();
			if(stp[nxtnding.dot]!=2147483647) continue;
			stp[nxtnding.dot]=nxtnding.val;
			for(int i=0;i<=51;i++)
				paths[nxtnding.dot][i]=nxtnding.path[i];
			okcnt++;
			nding=nxtnding.dot;
			break;
		}
		if(okcnt<0)
		{
			okcnt=-okcnt;
			break;
		}
	}
	cout<<stp[n];
    return 0;
}
2022/4/3 14:12
加载中...