QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#556309#5073. Elden RingHarry27182WA 0ms13740kbC++141.6kb2024-09-10 16:46:052024-09-10 16:46:05

Judging History

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

  • [2024-09-10 16:46:05]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:13740kb
  • [2024-09-10 16:46:05]
  • 提交

answer

#include<bits/stdc++.h>
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;}
int main()
{
	cin.tie(0)->sync_with_stdio(0);
	cin>>T;
	while(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(0,(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();tot++;
				if(vis[u])continue;vis[u]=1;
				for(int i=h[u];i;i=e[i].nxt)
				{
					int v=e[i].v;
					if(dis[v]>max(dis[u]+1,t[v])&&tot>=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;
}

详细

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 13740kb

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
-1

result:

wrong answer 2nd numbers differ - expected: '4', found: '-1'