QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#556332	#5073. Elden Ring	Harry27182	WA	131ms	13992kb	C++14	1.6kb	2024-09-10 16:57:55	2024-09-10 16:57:56

Judging History

你现在查看的是最新测评结果

[2024-09-10 16:57:56]
评测

测评结果：WA
用时：131ms
内存：13992kb

查看

[2024-09-10 16:57:55]
提交

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct edge{int v,nxt;}e[2000005]; 
int T,n,m,A,B,h[500005],w[500005],t[500005],cnt,dis[500005],vis[500005],u,v;
void add(int u,int v){e[++cnt]={v,h[u]};h[u]=cnt;}
signed main()
{
	cin.tie(0)->sync_with_stdio(0);
	cin>>T;
	for(int _=1;_<=T;_++)
	{
		cin>>n>>m>>A>>B;
		for(int i=1;i<=n;i++)h[i]=0;cnt=0;
		for(int i=1;i<=m;i++)
		{
			cin>>u>>v;
			add(u,v);add(v,u);
		}
		for(int i=1;i<=n;i++)cin>>w[i];
		for(int i=2;i<=n;i++)w[i]+=B;
		if(A<=B)
		{
			for(int i=2;i<=n;i++)
			{
				if(A==B)t[i]=(w[i]<w[1]?0x3f3f3f3f:0);
				else t[i]=max(0ll,(w[1]-w[i]-1)/(B-A)+1);
			}
			queue<int>q;q.push(1);
			for(int i=1;i<=n;i++)dis[i]=-1;dis[1]=0;
			while(!q.empty())
			{
				int u=q.front();q.pop();
				for(int i=h[u];i;i=e[i].nxt)
				{
					int v=e[i].v;
					if(dis[v]==-1&&dis[u]+1<=t[v])
					{
						dis[v]=dis[u]+1;
						q.push(v);
					}
				}
			}
			cout<<dis[n]<<'\n';
		}
		else 
		{
			for(int i=2;i<=n;i++)t[i]=(w[i]<w[1]?1:(w[i]-w[1])/(A-B)+2);
			priority_queue<pair<int,int> >q;q.push(make_pair(0,1));
			for(int i=1;i<=n;i++)dis[i]=0x3f3f3f3f,vis[i]=0;dis[1]=0;
			int tot=0;
			while(!q.empty())
			{
				int u=q.top().second;q.pop();
				if(vis[u])continue;vis[u]=1;
				if(tot<dis[u]){dis[u]=0x3f3f3f3f;continue;}
				tot++;
				for(int i=h[u];i;i=e[i].nxt)
				{
					int v=e[i].v;
					if(dis[v]>max(dis[u]+1,t[v]))
					{
						dis[v]=max(dis[u]+1,t[v]);
						q.push(make_pair(-dis[v],v));
					}
				}
			}
			if(dis[n]==0x3f3f3f3f)cout<<-1<<'\n';
			else cout<<dis[n]<<'\n';
		}
	}
	return 0;
}

源文件, 语言: C++14

详细

Test #1:

score: 100

Accepted

time: 0ms

memory: 13992kb

input:

2
5 4 5 8
1 2
1 3
1 4
4 5
15 1 1 1 1
5 4 10 5
1 2
1 3
1 4
4 5
10 4 4 4 19

output:

2
4

result:

ok 2 number(s): "2 4"

Test #2:

score: -100

Wrong Answer

time: 131ms

memory: 13736kb

input:

100000
6 10 107812 105568
6 5
3 6
4 6
4 2
5 1
5 6
4 5
1 3
1 2
2 5
124065 140875 29890 80077 116532 35394
9 10 82107 88302
1 2
2 3
5 3
5 1
1 4
9 6
3 5
8 2
5 6
7 5
22670 3735 33660 92823 139960 89319 83335 158330 117349
6 10 181257 173221
5 3
3 4
3 1
5 1
2 1
3 6
3 1
6 2
3 6
4 3
76902 46253 123092 2661...

output:

-1
-1
-1
1
-1
-1
-1
-1
-1
-1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
2
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
3
-1
2
-1
-1
-1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
2
-1
-1
-1
-1
-1
...

result:

wrong answer 484th numbers differ - expected: '-1', found: '2'