QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#274401	#5073. Elden Ring	LLLLL	WA	152ms	10304kb	C++14	2.0kb	2023-12-03 15:17:29	2023-12-03 15:17:29

Judging History

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

[2023-12-03 15:17:29]
评测

测评结果：WA
用时：152ms
内存：10304kb

查看

[2023-12-03 15:17:29]
提交

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,-1,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])/(B-A);
			else
			{
				if(l[i]<l[1])c[i]=0;
				else c[i]=(l[i]-l[1]-1)/(A-B)+1;
			}
//			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]==-1))
					{
						dis[to]=dis[now.id]+1;
						q.push((nod){to,dis[to]});
					}
				}
			}
			printf("%d\n",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]});
			}
			for(int i=1;i<=n;i++)
				if(vis[i])dis[i]=1e9;
			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]+1);
		}
	}
	return 0;
}

源文件, 语言: C++14

详细

Test #1:

score: 100

Accepted

time: 0ms

memory: 10088kb

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: 152ms

memory: 10304kb

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:

0
-1
0
2
-1
-1
-1
0
0
-1
2
-1
-1
-1
-1
0
0
0
0
-1
-1
2
0
-1
-1
0
-1
-1
0
0
0
-1
-1
0
0
0
-1
-1
-1
0
0
0
-1
-1
-1
-1
0
0
0
0
-1
-1
0
-1
0
3
0
-1
4
0
2
0
-1
0
1
-1
0
-1
0
0
0
0
-1
0
-1
-1
-1
-1
-1
0
-1
-1
-1
1
1
0
-1
0
-1
0
-1
0
-1
-1
-1
-1
-1
3
0
0
-1
0
0
-1
0
-1
-1
-1
-1
0
0
0
-1
0
0
-1
1
2
-1
0
2
-...

result:

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