QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#735660#6306. Chase Gamedsbdsb#WA 3ms11668kbC++141.4kb2024-11-11 21:10:192024-11-11 21:10:19

Judging History

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

  • [2024-11-11 21:10:19]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:11668kb
  • [2024-11-11 21:10:19]
  • 提交

answer

#include<bits/stdc++.h>
#define N 200010
#define ll long long
#define pli pair<ll,int>
#define fi first
#define se second
using namespace std;
int n,m,k,dn[N],dk[N];
ll d,dis[N];
vector<int> ve[N];
queue<int> q;
priority_queue<pli> pq;

inline ll solve(ll x){
	ll fz=x/d,g=x%d;
	ll ans=fz*(d+1)*d/2+g*(2*d-g+1)/2;
	return ans;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m>>k>>d;
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		ve[u].push_back(v);
		ve[v].push_back(u);
	}
	memset(dn,-1,sizeof dn);
	q.push(n);
	dn[n]=0;
//	printf("!!!\n");
	while(!q.empty()){
		int e=q.front();q.pop();
		for(auto i:ve[e]) if(dn[i]==-1){
			q.push(i);
			dn[i]=dn[e]+1;
		}
	}
	q.push(k);
	memset(dk,-1,sizeof dk);
	dk[k]=0;
	while(!q.empty()){
		int e=q.front();q.pop();
		for(auto i:ve[e]) if(dk[i]==-1){
			q.push(i);
			dk[i]=dk[e]+1;
		}
	}
	if(dk[1]>=d+1){
		cout<<solve(dn[1]);
		return 0;
	}
	for(auto i:ve[1]){
		if(dk[i]<d){
			pq.push({dk[i]-d,i});
		}
	}
	ll ans=1e18;
	memset(dis,-1,sizeof dis);
	dis[1]=0;
	while(!pq.empty()){
		pli e=pq.top();pq.pop();
		if(dis[e.se]!=-1) continue;
		dis[e.se]=-e.fi;
		if(dk[e.se]==d){
			ans=min(ans,solve(dn[e.se]+1)-e.fi);
			continue;
		}
		for(auto i:ve[e.se]){
			if(dis[i]!=-1) continue;
			pq.push({e.fi+dk[i]-d,i});
		}
	}
	ans=min(ans,solve(dn[1]));
	cout<<ans;
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 3ms
memory: 11352kb

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: 3ms
memory: 11364kb

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: 3ms
memory: 11372kb

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: 11424kb

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: 3ms
memory: 11668kb

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: 3ms
memory: 11360kb

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: -100
Wrong Answer
time: 0ms
memory: 11312kb

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:

27

result:

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