QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#274426#5073. Elden RingMaMengQi2WA 151ms10180kbC++141.9kb2023-12-03 15:27:362023-12-03 15:27:37

Judging History

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

  • [2023-12-03 15:27:37]
  • 评测
  • 测评结果:WA
  • 用时:151ms
  • 内存:10180kb
  • [2023-12-03 15:27:36]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int T,n,m,A,B,l[N];
#define ll long long
int dis[N],c[N],vis[N];
vector<int>e[N];
struct nod{
	int id,val;
	bool operator<(const nod&x)const{
		return val>x.val;
	}
};
priority_queue<nod>q;
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d%d%d",&n,&m,&A,&B);
		memset(dis,0x7f,sizeof(int)*(n+1));
		for(int i=1;i<=n;i++)e[i].clear();
		for(int i=1,u,v;i<=m;i++)
		{
			scanf("%d%d",&u,&v);
			e[u].push_back(v);
			e[v].push_back(u);
		}
		for(int i=1;i<=n;i++)scanf("%d",&l[i]);
		for(int i=2;i<=n;i++)
		{
			l[i]+=B;
			if(A==B)c[i]=(l[i]<l[1])?0:1e9;
			else if(A<B)c[i]=(l[1]-l[i]-1)/(B-A);
			else
			{
				if(l[i]<l[1])c[i]=0;
				else c[i]=(l[i]-l[1])/(A-B)+2;
			}
//			printf("%d ",c[i]);
		}
//		puts("");
		if(A<=B)//最晚ci打
		{
			q.push((nod){1,0});
			dis[1]=0;
			while(!q.empty())
			{
				nod now=q.top();
				q.pop();
//				printf("now::%d %d\n",now.id,now.val);
				if(dis[now.id]!=now.val)continue;
				for(int to:e[now.id])
				{
					if(dis[now.id]<=c[to]&&dis[to]>dis[now.id]+1)
					{
						dis[to]=dis[now.id]+1;
						q.push((nod){to,dis[to]});
					}
				}
			}
			printf("%d\n",dis[n]>=5e8?-1:dis[n]);
		}
		else
		{
			memset(vis,0,sizeof(int)*(n+1));
			q.push((nod){1,0});
			int Nl=l[1];
			while(!q.empty())
			{
				nod now=q.top();
				q.pop();
				if(now.val>Nl)continue;
				vis[now.id]=1;
				Nl+=A-B;
				for(int to:e[now.id])
					if(!vis[to])q.push((nod){to,l[to]});
			}
			q.push((nod){1,0});
			dis[1]=0;
			while(!q.empty())
			{
				nod now=q.top();
				q.pop();
				if(dis[now.id]!=now.val)continue;
				for(int to:e[now.id])
				{
					if(vis[to]&&dis[to]>max(dis[now.id]+1,c[to]))
					{
						dis[to]=max(dis[now.id]+1,c[to]);
						q.push((nod){to,dis[to]});
					}
				}
			}
			printf("%d\n",dis[n]>=5e8?-1:(dis[n]));
		}
	}
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 9696kb

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: 151ms
memory: 10180kb

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
3
-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 56th numbers differ - expected: '-1', found: '3'