一个小疑问
  • 板块CF76A Gift
  • 楼主masonpop
  • 当前回复4
  • 已保存回复4
  • 发布时间2022/11/25 17:42
  • 上次更新2023/11/5 21:54:06
查看原帖
一个小疑问
614725
masonpop楼主2022/11/25 17:42

请问答案 ansans 每次取 minmin ,如果将 ansans 初值赋 LONG_MAX 会 WA on #10,并且错误原因是输出了 -1 ,改成一个别的数(如4e18) 就会 AC 请问这是为什么?

  • 这里是代码。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=4e18;
int n,m;
int S,T;
const int maxn=2e6+10;
struct coins{
	int x,y,s,t;
	bool operator<(const coins &o) const{
		return t<o.t;
	}
}a[maxn],tmp[maxn];//tmp临时数组 (维护生成树) 
int fa[maxn];
inline int get(int x)
{
	if(x==fa[x])return x;
	return fa[x]=get(fa[x]);
}
signed main() 
{ 
	scanf("%lld%lld",&n,&m);
	scanf("%lld%lld",&S,&T);
	int ans=inf;
	for(int i=1;i<=m;i++)scanf("%lld%lld%lld%lld",&a[i].x,&a[i].y,&a[i].s,&a[i].t);
	sort(a+1,a+m+1);
	int tot=0,now=0;
	for(int i=1;i<=m;i++)
	{
		tmp[++tot]=a[i];
    	for(int j=tot-1;j>=1;j--)
    	{
    		if(tmp[j].s>tmp[j+1].s)
            {
                swap(tmp[j],tmp[j+1]);
            }
		}
        now=0;
        for(int j=1;j<=n;j++)fa[j]=j;
        for(int j=1;j<=tot;j++)
        {
            int fa1=get(tmp[j].x),fa2=get(tmp[j].y);
            if(fa1!=fa2)
            {
                fa[fa1]=fa2;
                tmp[++now]=tmp[j];//更新kruskal 
            }
        }
        if(now==n-1)
        {
            ans=min(ans,S*tmp[now].s+T*a[i].t);//更新 
        }
        tot=now;
	}
	if(ans==inf)puts("-1");
	else printf("%lld\n",ans);
	return 0;
}
2022/11/25 17:42
加载中...