QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#303051#6306. Chase GameLh_Ty#WA 2ms12264kbC++141.9kb2024-01-11 17:21:392024-01-11 17:21:40

Judging History

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

  • [2024-01-11 17:21:40]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:12264kb
  • [2024-01-11 17:21:39]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;
int read()
{
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
const int MAXN=2e5+10,inf=1e15;
int n,m,cnt,d,k,ans=inf;
int v[MAXN*4],first[MAXN],net[MAXN*4];
int disn[MAXN],disk[MAXN],vis[MAXN];
void add(int x,int y)
{
	++cnt;
	v[cnt]=y;
	net[cnt]=first[x];
	first[x]=cnt;
}
struct node
{
	int opt,x;
	friend bool operator <(node x,node y)
	{
		return x.x>y.x;
	}
};
void BFS(int s,int *dis)
{
	for(int i=1;i<=n;i++)vis[i]=0,dis[i]=inf;
	queue<int>q;
	q.push(s);
	dis[s]=0;
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		for(int i=first[x];i;i=net[i])
		{
			if(vis[v[i]])continue;
			dis[v[i]]=dis[x]+1;
			vis[v[i]]=1;
			q.push(v[i]);
		}
	}
}
int dis[MAXN];
void dij(int s)
{
	for(int i=1;i<=n;i++)vis[i]=0,dis[i]=inf;
	priority_queue<node>q;
	q.push({s,0});
	dis[s]=-d+disk[s];
	while(!q.empty())
	{
		int x=q.top().opt;
		q.pop();
		if(vis[x])continue;
		vis[x]=1;
		if(disk[x]>=d&&x!=s)
		{
			int t=disn[x]+1;
			int len=t/d,b=t%d;
			ans=min(ans,dis[x]+len*d*(d+1)/2+(d+d-b+1)*b/2);
			continue;
		}
		for(int i=first[x];i;i=net[i])
		{
			if(dis[v[i]]>dis[x]+d-disk[x])
			{
				dis[v[i]]=dis[x]+d-disk[x];
				q.push({v[i],dis[v[i]]});
			}
		}
	}
	if(disk[n]>=d)ans=min(ans,dis[n]+d);
	else ans=min(ans,dis[n]+d-disk[n]);
}
//bool tp()
//{
//	if(disk[1]>=d)
//	{
//		int t=disn[1];
//		int len=t/d,b=t%d;
//		ans=min(ans,len*d*(d+1)/2+(d+d-b+1)*b/2);
//		return 0;
//	}
//	return 1;
//}
signed main()
{
	n=read();m=read();k=read();d=read();
	for(int i=1;i<=m;i++)
	{
		int x,y;
		x=read();y=read();
		add(x,y);add(y,x);
	}
	BFS(n,disn);
	BFS(k,disk);
	//if(tp())
	dij(1);
	printf("%lld\n",ans);
	return 0;
}
/*
5 5 3 1
1 2
2 4
4 5
1 3
3 5
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5 5 3 1
1 2
2 4
4 5
1 3
3 5

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: 0
Accepted
time: 0ms
memory: 11936kb

input:

13 17 12 3
1 2
2 3
3 4
4 13
5 13
7 8
7 9
7 10
7 11
7 6
12 7
1 8
8 9
9 10
10 11
11 6
6 13

output:

7

result:

ok 1 number(s): "7"

Test #3:

score: 0
Accepted
time: 0ms
memory: 12264kb

input:

10 9 4 1
4 3
1 2
7 6
6 5
8 9
9 10
5 4
8 7
3 2

output:

9

result:

ok 1 number(s): "9"

Test #4:

score: 0
Accepted
time: 0ms
memory: 10148kb

input:

10 20 9 1
9 5
2 9
4 5
10 5
7 3
1 8
7 1
7 5
3 4
3 1
7 8
3 8
9 3
10 6
9 1
1 6
8 5
6 2
1 10
2 1

output:

1

result:

ok 1 number(s): "1"

Test #5:

score: 0
Accepted
time: 2ms
memory: 12180kb

input:

10 20 3 1
1 4
6 7
5 4
5 3
2 1
8 1
7 8
2 6
2 4
4 8
9 5
1 10
7 4
5 8
4 10
2 5
6 10
4 6
3 7
1 3

output:

1

result:

ok 1 number(s): "1"

Test #6:

score: 0
Accepted
time: 0ms
memory: 11920kb

input:

10 20 4 1
2 7
6 4
2 3
2 4
6 5
8 5
6 7
10 2
3 10
1 8
3 9
3 7
1 7
5 1
6 1
3 4
2 1
5 2
9 2
9 10

output:

2

result:

ok 1 number(s): "2"

Test #7:

score: 0
Accepted
time: 0ms
memory: 9836kb

input:

10 20 1 10
10 9
2 5
7 8
7 10
10 8
8 9
5 6
3 1
6 4
7 9
2 3
3 6
2 1
8 6
5 8
7 4
4 3
2 4
4 1
9 6

output:

24

result:

ok 1 number(s): "24"

Test #8:

score: 0
Accepted
time: 2ms
memory: 11988kb

input:

10 20 6 10
5 4
1 7
6 8
1 2
6 1
5 2
5 1
2 4
5 3
3 2
10 3
9 10
7 9
3 1
5 9
1 8
8 3
8 7
6 4
2 7

output:

15

result:

ok 1 number(s): "15"

Test #9:

score: 0
Accepted
time: 0ms
memory: 11940kb

input:

1000 999 387 1
505 506
314 313
410 411
680 681
884 885
491 492
60 59
343 342
396 397
880 881
954 953
833 834
53 54
284 283
794 793
241 240
347 348
89 88
787 786
551 550
673 672
56 57
683 682
168 169
814 813
726 725
877 876
981 982
799 800
228 227
568 569
387 386
211 212
30 29
298 299
514 515
561 562...

output:

999

result:

ok 1 number(s): "999"

Test #10:

score: 0
Accepted
time: 2ms
memory: 11952kb

input:

1000 2000 879 1
357 547
380 111
973 995
179 906
478 508
463 822
687 488
70 40
330 202
189 303
103 39
510 743
1000 236
311 695
29 338
156 77
299 249
289 275
419 57
352 704
739 825
676 194
783 828
769 169
270 325
354 29
145 197
309 461
456 461
997 816
478 387
117 626
931 803
445 91
730 160
1000 322
25...

output:

3

result:

ok 1 number(s): "3"

Test #11:

score: -100
Wrong Answer
time: 2ms
memory: 9944kb

input:

1000 2000 603 228
10 11
885 884
217 218
626 629
559 562
305 302
328 326
809 807
176 179
553 554
435 432
641 639
761 763
486 484
376 374
261 260
515 512
224 222
413 414
33 34
468 470
976 979
461 459
491 490
272 275
528 526
393 396
673 676
45 42
677 676
247 249
938 937
200 203
649 647
303 304
457 455
...

output:

49207

result:

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