QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#283131#5073. Elden RingsslwcrWA 51ms12020kbC++142.9kb2023-12-13 21:24:252023-12-13 21:24:25

Judging History

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

  • [2023-12-13 21:24:25]
  • 评测
  • 测评结果:WA
  • 用时:51ms
  • 内存:12020kb
  • [2023-12-13 21:24:25]
  • 提交

answer

#include<bits/stdc++.h>
#include<vector>
#include<queue>
#include<bitset>
#define int long long
using namespace std;
inline int read()
{
	int ret,c,f=1;
	while (((c=getchar())> '9'||c< '0')&&c!='-');
	if (c=='-') f=-1,ret=0;
	else ret=c-'0';
	while ((c=getchar())>='0'&&c<='9') ret=ret*10+c-'0';
	return ret*f;
}
bool vis[200005];
int T,n,m,A,B,l[200005],dis[200005],head[200005],to[400005],nxt[400005],tot;
void add(int x,int y)
{
	to[++tot]=y;
	nxt[tot]=head[x];
	head[x]=tot;
	return;
}
priority_queue<pair<int,int> > q;
bool caa[200005];
signed main()
{
	T=read();
	while (T--)
	{
		n=read(),m=read(),A=read(),B=read();
		tot=0;
		for (int i=1;i<=n;i++)
		{
			head[i]=0;
			dis[i]=10000000;
			vis[i]=caa[i]=0;
		}
		for (int i=1;i<=m;i++)
		{
			int x=read(),y=read();
			add(x,y),add(y,x);
		}
		for (int i=1;i<=n;i++) l[i]=read();
		if (A==B)
		{
			dis[1]=0;
			while (q.size()) q.pop();
			q.push(make_pair(0,1));
			while (q.size())
			{
				int x=q.top().second;
				q.pop();
				if (vis[x]==1) continue;
				vis[x]=1;
				for (int i=head[x];i;i=nxt[i])
				{
					if (vis[to[i]]) continue;
					if (l[to[i]]+B>=l[1]) continue;
					if (dis[to[i]]>dis[x]+1)
					{
						dis[to[i]]=dis[x]+1;
						q.push(make_pair(-dis[to[i]],to[i]));
					}
				}
			}
			if (dis[n]==10000000) printf("-1\n");
			else printf("%lld\n",dis[n]);
			continue;
		}
		if (A<B)
		{
			dis[1]=0;
			while (q.size()) q.pop();
			q.push(make_pair(0,1));
			while (q.size())
			{
				int x=q.top().second;
				q.pop();
				if (vis[x]==1) continue;
				vis[x]=1;
				for (int i=head[x];i;i=nxt[i])
				{
					if (vis[to[i]]) continue;
					if (l[to[i]]+dis[x]*(B-A)+B>=l[1]) continue;
					if (dis[to[i]]>dis[x]+1)
					{
						dis[to[i]]=dis[x]+1;
						q.push(make_pair(-dis[to[i]],to[i]));
					}
				}
			}
			if (dis[n]==10000000) printf("-1\n");
			else printf("%lld\n",dis[n]);
			continue;
		}
		dis[1]=0;
		caa[1]=1;
		while (q.size()) q.pop();
		int TT=-1;
		q.push(make_pair(0,1));
		while (q.size())
		{
			int x=q.top().second;
			q.pop();
			if (x!=1&&l[x]+(B-A)*TT+B>=l[1]) continue;
			caa[x]=1;
			TT++;
			for (int i=head[x];i;i=nxt[i])
			{
				if (caa[to[i]]==1) continue;
				q.push(make_pair(-l[to[i]],to[i]));
			}
		}
		if (!caa[n])
		{
			printf("-1\n");
			continue;
		}
		while (q.size()) q.pop();
		q.push(make_pair(0,1));
		while (q.size())
		{
			int x=q.top().second;
			q.pop();
			if (vis[x]==1) continue;
			vis[x]=1;
			for (int i=head[x];i;i=nxt[i])
			{
				if (vis[to[i]]) continue;
				if (caa[to[i]]==0) continue;
				int V=ceil(1.0*(l[1]-l[to[i]]-B)/(B-A));
				V=max(dis[x]+1,V+1);
				if (V<dis[to[i]])
				{
					dis[to[i]]=V;
					q.push(make_pair(-dis[to[i]],to[i]));
				}
			}
		}
		if (dis[n]==10000000) printf("-1\n");
		else printf("%lld\n",dis[n]);
	}
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 9916kb

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: 51ms
memory: 12020kb

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