萌新刚学sort函数前来求助
查看原帖
萌新刚学sort函数前来求助
19228
蒟蒻炒扇贝楼主2021/11/3 12:21

我怀疑sort函数是不是有什么隐藏效果...

signed main()
{
	cin>>n>>m>>b>>e;//ti[0].x=e;
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		cin>>x>>y>>z;
		addedge(x,y,z);
		addedge(y,x,z);
	}
	dij(b);
	int ans=2e18;
	cin>>T;
	for(int i=1;i<=T;i++)cin>>ti[i].t>>ti[i].x;
	sort(ti+1,ti+1+T,cmp);
	if(dis[e]<ti[1].t)ans=max(dis[e],0ll);
	for(int i=1;i<=T;i++)
	{
		int x=ti[i].x,t=ti[i].t;
		if(dis[x]<ti[i+1].t)ans=min(ans,max(dis[x],ti[i].t));//got you before you escape!
	}
	ans=min(ans,max(dis[ti[T].x],ti[T].t));
	cout<<ans;
	return 0;
}

这一份代码是可以AC的,然而下面一段代码会WA上几个点:

	cin>>n>>m>>b>>e;ti[0].x=e;
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		cin>>x>>y>>z;
		addedge(x,y,z);
		addedge(y,x,z);
	}
	dij(b);
	int ans=2e18;
	cin>>T;
	for(int i=1;i<=T;i++)cin>>ti[i].t>>ti[i].x;
	sort(ti+1,ti+1+T,cmp);
	if(dis[e]<ti[1].t)ans=max(dis[e],0ll);
	for(int i=1;i<=T;i++)
	{
		int x=ti[i].x,t=ti[i].t;
		if(dis[x]<ti[i+1].t)ans=min(ans,max(dis[x],ti[i].t));//got you before you escape!
	}
	ans=min(ans,max(dis[ti[T].x],ti[T].t));
	cout<<ans;
	return 0;

两份代码的区别在于ti[0].x=e;的有无。

那么问题来了,我除了在最开始的ti[0].x=e;代码中调用了ti[0]这一变量,在代码的剩余部分中均没有调用这一变量。也就是说ti[0].x=e;这一代码是可有可无的。

但为啥删除这行代码后程序就AC不了了呢?

接下来我做了一个实验:

以可以AC的代码为蓝本,在输出我们的答案前,我先让程序做了这样一件事:

if(ti[T].x==e)cout<<"HA";

评测记录在这里

可以发现这些WA了的点无一例外都输出了HA

但如果我把ti[0].x=e;去掉的话,WA的点就没有输出HA的情况。

这是否说明在这个程序里,sort(ti+1,ti+1+T,cmp);在排序的过程中也把ti[0]也给排序了?

也就是说,sort(ti+1,ti+1+T,cmp);sort(ti,ti+1+T,cmp);等价?

萌新不懂,只好来求助广大谷民。

2021/11/3 12:21
加载中...