import io,os,sys
from collections import deque
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
sys.setrecursionlimit(10010)
def getdistance(source,neigh):
n = len(neigh)
queue = deque()
output = [-1]*n
queue.append((source,0))
output[source] = 0
while queue:
index,step = queue.popleft()
for nextindex in neigh[index]:
if output[nextindex] >= 0: continue output[nextindex] = step + 1
queue.append((nextindex,step+1))
return output
def main(t):
n,m = map(int,input().split())
neigh = [[] for _ in range(n)]
for _ in range(m):
u,v = map(int,input().split())
neigh[u-1].append(v-1)
neigh[v-1].append(u-1)
friendnum = int(input())
friends = list(map(int,input().split()))
nocarnum = int(input())
nocars = list(map(int,input().split()))
for i in range(len(friends)): friends[i] -= 1
for i in range(len(nocars)): nocars[i] -= 1
distance = getdistance(0,neigh)
dic = {0:distance}
temp = []
for nocar in nocars:
temp.append([distance[friends[nocar]],friends[nocar] ])
dic[friends[nocar]] = getdistance(friends[nocar],neigh)
temp.sort()
avail = [[] for _ in range(friendnum)]
for b in range(1,1<<nocarnum):
s = bin(b)[2:]
s = (nocarnum-len(s)) * '0' + s
seq = [0]
for i,c in enumerate(s):
if c=='1': seq.append(temp[i][1] )
for k,f in enumerate(friends):
if k in nocars: continue
seq.append(f)
accud = 0
for j in range(len(seq)-1):
accud += dic[seq[j]][seq[j+1]]
if accud == dic[0][f]:
avail[k].append(b)
seq.pop()
reala = []
for ele in avail:
if not ele: continue
reala.append(ele)
dp = [[2147483647 for _ in range(1<<nocarnum)] for _ in range(len(reala)+1)]
for state in range(1<<nocarnum):
output = 0
for d in range(nocarnum):
if (1<<d) & state == 0: output += 1
dp[len(reala)][state] = output
for index in range(len(reala)-1,-1,-1):
for state in range(1<<nocarnum):
dp[index][state] = dp[index+1][state]
for b in reala[index]:
dp[index][state] = min(dp[index][state], dp[index+1][state|b] )
ans = dp[0][0]
print(ans)
T = int(input())
t = 1
while t<=T:
main(t)
t += 1
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
int sum(int x)
{
int res = 0;
while (x)
{
if (x & 1) res ++;
x >>= 1;
}
return res;
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
int T; cin >> T;
while (T --)
{
int n, m; cin >> n >> m;
vector<int> e[n + 1];
for (int i = 0; i < m; i ++)
{
int u, v; cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
int cnt; cin >> cnt;
vector<int> home(cnt + 1);
for (int i = 1; i <= cnt; i ++) cin >> home[i];
int no_car_cnt; cin >> no_car_cnt;
vector<int> car(cnt + 1, 1), c(no_car_cnt + 1);
for (int i = 1; i <= no_car_cnt; i ++)
{
int x; cin >> x;
car[x] = 0, c[i] = home[x];
}
vector dist(no_car_cnt + 1, vector<int> (n + 1, -1));
function<void(int, int)> bfs = [&](int u, int num)
{
queue<int> q;
dist[num][u] = 0;
q.push(u);
while (!q.empty())
{
auto t = q.front();
q.pop();
for (int i : e[t])
{
if (dist[num][i] == -1)
{
dist[num][i] = dist[num][t] + 1;
q.push(i);
}
}
}
};
bfs(1, 0);
for (int i = 1; i <= no_car_cnt; i ++) bfs(c[i], i);
vector<int> f(1 << no_car_cnt, 0), g((1 << no_car_cnt), 0);
f[0] = 1;
function<bool(int, int)> cmp = [&](int A, int B)
{
return dist[0][c[A]] < dist[0][c[B]];
};
for (int i = 1; i <= cnt; i ++)
{
if (!car[i]) continue;
for (int j = 1; j < (1 << no_car_cnt); j ++)
{
vector<int> now;
for (int k = 0; k < no_car_cnt; k ++)
if (j >> k & 1) now.push_back(k + 1);
sort(now.begin(), now.end(), cmp);
int s = dist[0][c[now[0]]];
for (int k = 1; k < now.size(); k ++) s += dist[now[k - 1]][c[now[k]]];
s += dist[now.back()][home[i]];
g[j] = s == dist[0][home[i]];
}
for (int j = (1 << no_car_cnt) - 1; j; j --)
for (int k = 1; k <= j; k ++)
if ((k ^ j) + k == j) f[j] |= f[j ^ k] & g[k];
}
int ans = 0;
for (int i = 1; i < (1 << no_car_cnt); i ++) if (f[i]) ans = max(ans, sum(i));
cout << no_car_cnt - ans << endl;
}
}580A- Kefa and First Steps | 1472B- Fair Division |
996A - Hit the Lottery | MSNSADM1 Football |
MATCHES Playing with Matches | HRDSEQ Hard Sequence |
DRCHEF Doctor Chef | 559. Maximum Depth of N-ary Tree |
821. Shortest Distance to a Character | 1441. Build an Array With Stack Operations |
1356. Sort Integers by The Number of 1 Bits | 922. Sort Array By Parity II |
344. Reverse String | 1047. Remove All Adjacent Duplicates In String |
977. Squares of a Sorted Array | 852. Peak Index in a Mountain Array |
461. Hamming Distance | 1748. Sum of Unique Elements |
897. Increasing Order Search Tree | 905. Sort Array By Parity |
1351. Count Negative Numbers in a Sorted Matrix | 617. Merge Two Binary Trees |
1450. Number of Students Doing Homework at a Given Time | 700. Search in a Binary Search Tree |
590. N-ary Tree Postorder Traversal | 589. N-ary Tree Preorder Traversal |
1299. Replace Elements with Greatest Element on Right Side | 1768. Merge Strings Alternately |
561. Array Partition I | 1374. Generate a String With Characters That Have Odd Counts |