QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#556296#5073. Elden RingHarry27182WA 136ms14032kbC++141.5kb2024-09-10 16:40:082024-09-10 16:40:22

Judging History

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

  • [2024-09-10 16:40:22]
  • 评测
  • 测评结果:WA
  • 用时:136ms
  • 内存:14032kb
  • [2024-09-10 16:40:08]
  • 提交

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;
			while(!q.empty())
			{
				int u=q.top().second;q.pop();
				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]))
					{
						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: 100
Accepted
time: 2ms
memory: 13772kb

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: 136ms
memory: 14032kb

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:

9
-1
37
1
-1
-1
-1
32
18
-1
1
-1
-1
-1
-1
22
160
18
29
-1
-1
2
31
-1
-1
9
-1
-1
22
37
28
-1
-1
47
16
826
-1
-1
-1
7
26
18
-1
-1
-1
-1
44
84
98
20
-1
-1
26
-1
27
3
44
-1
3
16
2
15
-1
255
1
-1
17
-1
115
38
80
59
-1
30
-1
-1
-1
-1
-1
46
-1
-1
-1
1
1
28
-1
31
-1
35
-1
46
-1
-1
-1
-1
-1
2
30
29
-1
32
7
-...

result:

wrong answer 1st numbers differ - expected: '-1', found: '9'