比赛 EYOI暨SBOI暑假快乐赛5th 评测结果 TTTTTTTTTT
题目名称 AND Sorting 最终得分 0
用户昵称 lavey 运行时间 10.000 s
代码语言 C++ 内存使用 10.39 MiB
提交时间 2022-06-29 11:13:08
显示代码纯文本
#include<bits/stdc++.h>
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define drep(x,y,z) for(int x=y;x>=z;x--)
#define ull unsigned long long
#define ll long long
using namespace std;
inline int read()
{
	int x=0;bool flag=1;char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-')flag=0;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
	if(flag) return x;
	return ~(x-1);
} 
inline void write(int x)
{
	if(x<0) {x=~(x-1);putchar('-');}
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
/////////////////////////
const int N=1e4+50;
const int M=2e5+50;
int nc,mc,s;
struct G
{
	int val;
	int ar;
	int nx;
}a[M<<1];
int aj;
int hd[N];
int sp,mn;
inline void ADD(int x,int y,int z)
{
	a[++aj].val=z;
	a[aj].ar=y;
	a[aj].nx=hd[x];
	hd[x]=aj;
}
//*
struct XGD
{
	int val;
	int ar;
};
struct cmp1
{
	bool operator()(XGD x,XGD y)
	{
		return x.val>y.val;
	}
};
priority_queue<XGD,vector<XGD>,cmp1> b;//以val为关键词的小根堆
//*
int p[N];
int pj;
inline int PRI()
{
	int re=a[mn].val;
//	cout<<"1:"<<re<<endl;
	XGD t1;
	p[a[mn].ar]=p[a[mn+1].ar]=1;
	pj=2;
	for(int i=hd[a[mn].ar];i;i=a[i].nx)
	{
		if(p[a[i].ar]) continue;
		t1.val=a[i].val;
		t1.ar=a[i].ar;
		b.push(t1);
	}
	for(int i=hd[a[mn+1].ar];i;i=a[i].nx)
	{
		if(p[a[i].ar]) continue;
		t1.val=a[i].val;
		t1.ar=a[i].ar;
		b.push(t1);
	}
	XGD t2;
	while(pj<nc)
	{
		t2=b.top();
		b.pop();
		if(p[t2.ar]) continue;
		p[t2.ar]=1;
		re+=t2.val;
		for(int i=hd[t2.ar];i;i=a[i].nx)
		{
			if(p[a[i].ar]) continue;
			t1.val=a[i].val;
			t1.ar=a[i].ar;
			b.push(t1);
		}
		pj++;
//		cout<<"2:"<<re<<" "<<pj<<","<<t2.ar<<" "<<t2.val<<endl;
	}
	return re;
}
int main()
{
    freopen("zxscs.in","r",stdin);
	freopen("zxscs.out","w",stdout);
    nc=read(),mc=read();
    int s1,s2,s3;
    a[mn].val=1<<30; 
    rep(i,1,mc)
    {
    	s1=read(),s2=read(),s3=read();
    	ADD(s1,s2,s3);
    	if(s3==-1) sp=aj;
    	else if(s3<a[mn].val) mn=aj;
    	ADD(s2,s1,s3);
	}
	s=read();
	a[sp].val=a[sp+1].val=0;
	s1=PRI();
	a[sp].val=a[sp+1].val=1<<30;
	while(!b.empty()) b.pop();
	memset(p,0,sizeof(p));
	pj=0;
	s2=PRI();
//	cout<<"S:"<<s1<<" "<<s2<<endl;
	if(s2<=s||s1>=s) printf("Poor van!\n");
	else printf("%d\n",s-s1);
    return 0;
}