107012024-04-09 23:15:17111Autó-tortúracpp17Wrong answer 24/100717ms12584 KiB
#include<bits/stdc++.h>
using namespace std;

#define int long long

#define INF (int)1e16

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
#ifdef CB
	freopen("be2.txt","r",stdin);
//	freopen("ki.txt","w",stdout);
#endif
	int N,M,K;
	cin>>N>>M>>K;
	vector<vector<int>>g(N+1);
	for(int i=0;i<M;i++){
		int a,b;
		cin>>a>>b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	int L;
	cin>>L;
	vector<int>l(L);
	for(int i=0;i<L;i++){
		cin>>l[i];
	}
	int B;
	cin>>B;
	vector<int>b(B);
	for(int i=0;i<B;i++){
		cin>>b[i];
	}
	vector<vector<int>>x(B,vector<int>(L,INF));
	vector<vector<int>>y(B,vector<int>(B,INF));
	for(int i=0;i<B;i++){
		deque<int>q;
		vector<int>d(N+1,INF);
		d[b[i]]=0;
		q.push_back(b[i]);
		while(!q.empty()){
			int i=q.front();
			q.pop_front();
			for(int j:g[i]){
				if(d[i]+1<d[j]){
					d[j]=d[i]+1;
					q.push_back(j);
				}
			}
		}
		for(int j=0;j<L;j++){
			if(d[l[j]]<=K){
				x[i][j]=d[l[j]];
			}
		}
		for(int j=0;j<B;j++){
			if(d[b[j]]<=K){
				y[i][j]=d[b[j]];
			}
		}
	}
	for(int i=0;i<B;i++){
		for(int j=0;j<B;j++){
			for(int k=0;k<B;k++){
				y[j][k]=min(y[j][k],y[j][i]+y[i][k]);
			}
		}
	}
	vector<int>a(K+2);
	a[K+1]=INF;
	for(int i=1;i<L;i++){
		vector<int>b(K+2,INF);
		deque<int>q;
		vector<int>d(N+1,INF);
		d[l[i-1]]=0;
		q.push_back(l[i-1]);
		while(!q.empty()){
			int i=q.front();
			q.pop_front();
			for(int j:g[i]){
				if(d[i]+1<d[j]){
					d[j]=d[i]+1;
					q.push_back(j);
				}
			}
		}
		int dl=d[l[i]];
		for(int j=0;j+dl<=K;j++){
			b[j]=min(b[j],a[j+dl]+dl);
		}
		for(int k=0;k<B;k++){
			int j=K-x[k][i];
			if(j<0){
				continue;
			}
			if(x[k][i-1]<=K){
				b[j]=min(b[j],a[x[k][i-1]]+x[k][i-1]+x[k][i]);
			}
			for(int kk=0;kk<B;kk++){
				int jj=K-x[kk][i];
				if(jj<0){
					continue;
				}
				if(x[k][i-1]<=K){
					b[min(j,jj)]=min(b[min(j,jj)],a[x[k][i-1]]+x[k][i-1]+x[kk][i]+y[k][kk]);
				}
			}
		}
		for(int j=K-1;j>=0;j--){
			b[j]=min(b[j],b[j+1]);
		}
		a=b;
	}
	cout<<(a[0]==INF?-1:a[0])<<'\n';
	return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1836 KiB
2Accepted345ms7256 KiB
subtask20/12
3Accepted3ms2536 KiB
4Accepted3ms2644 KiB
5Accepted3ms2528 KiB
6Accepted3ms2472 KiB
7Accepted3ms2424 KiB
8Wrong answer2ms2488 KiB
9Wrong answer3ms2620 KiB
10Accepted3ms2828 KiB
subtask30/18
11Accepted3ms2536 KiB
12Accepted3ms2644 KiB
13Accepted3ms2528 KiB
14Accepted3ms2472 KiB
15Accepted3ms2424 KiB
16Wrong answer2ms2488 KiB
17Wrong answer3ms2620 KiB
18Accepted3ms2828 KiB
19Accepted4ms3120 KiB
20Accepted16ms3800 KiB
21Accepted14ms4004 KiB
22Accepted14ms4144 KiB
23Accepted7ms3836 KiB
24Wrong answer4ms3744 KiB
25Wrong answer8ms4128 KiB
26Wrong answer8ms4136 KiB
27Wrong answer4ms4076 KiB
subtask40/25
28Accepted3ms2536 KiB
29Accepted3ms2644 KiB
30Accepted3ms2528 KiB
31Accepted3ms2472 KiB
32Accepted3ms2424 KiB
33Wrong answer2ms2488 KiB
34Wrong answer3ms2620 KiB
35Accepted3ms2828 KiB
36Accepted35ms4464 KiB
37Accepted32ms4608 KiB
38Accepted35ms4904 KiB
39Accepted24ms4632 KiB
40Accepted14ms4452 KiB
41Accepted7ms4388 KiB
42Wrong answer32ms4928 KiB
43Accepted25ms4712 KiB
44Wrong answer25ms4712 KiB
45Wrong answer13ms4656 KiB
subtask524/24
46Accepted416ms4628 KiB
47Accepted365ms4620 KiB
48Accepted404ms4716 KiB
49Accepted374ms4588 KiB
50Accepted238ms4452 KiB
51Accepted411ms4712 KiB
52Accepted360ms4708 KiB
53Accepted400ms4804 KiB
54Accepted368ms4804 KiB
55Accepted233ms4812 KiB
subtask60/21
56Accepted3ms2536 KiB
57Accepted3ms2644 KiB
58Accepted3ms2528 KiB
59Accepted3ms2472 KiB
60Accepted3ms2424 KiB
61Wrong answer2ms2488 KiB
62Wrong answer3ms2620 KiB
63Accepted3ms2828 KiB
64Accepted4ms3120 KiB
65Accepted16ms3800 KiB
66Accepted14ms4004 KiB
67Accepted14ms4144 KiB
68Accepted7ms3836 KiB
69Wrong answer4ms3744 KiB
70Wrong answer8ms4128 KiB
71Wrong answer8ms4136 KiB
72Wrong answer4ms4076 KiB
73Accepted35ms4464 KiB
74Accepted32ms4608 KiB
75Accepted35ms4904 KiB
76Accepted24ms4632 KiB
77Accepted14ms4452 KiB
78Accepted7ms4388 KiB
79Wrong answer32ms4928 KiB
80Accepted25ms4712 KiB
81Wrong answer25ms4712 KiB
82Wrong answer13ms4656 KiB
83Accepted416ms4628 KiB
84Accepted365ms4620 KiB
85Accepted404ms4716 KiB
86Accepted374ms4588 KiB
87Accepted238ms4452 KiB
88Accepted411ms4712 KiB
89Accepted360ms4708 KiB
90Accepted400ms4804 KiB
91Accepted368ms4804 KiB
92Accepted233ms4812 KiB
93Accepted111ms6244 KiB
94Wrong answer98ms6344 KiB
95Wrong answer127ms6300 KiB
96Wrong answer133ms6348 KiB
97Wrong answer29ms5912 KiB
98Accepted111ms7192 KiB
99Accepted97ms6016 KiB
100Accepted685ms12304 KiB
101Accepted717ms12352 KiB
102Accepted662ms12172 KiB
103Accepted578ms12148 KiB
104Accepted460ms12260 KiB
105Accepted612ms12280 KiB
106Accepted591ms12284 KiB
107Accepted558ms12204 KiB
108Accepted676ms12584 KiB
109Accepted140ms4932 KiB
110Accepted361ms7584 KiB
111Accepted412ms4996 KiB
112Accepted328ms5272 KiB
113Accepted351ms5096 KiB
114Wrong answer587ms12536 KiB
115Wrong answer87ms5960 KiB
116Wrong answer90ms6072 KiB
117Wrong answer361ms12120 KiB
118Wrong answer109ms11988 KiB