Submission #19812154

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#!/usr/bin/env python3
# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    N,M = map(int, input().split())
    edges = [[] for _ in range(N)]
    for _ in range(M):
        a,b = map(int,input().split())
        a-=1
        b-=1
        edges[a].append(b)
        edges[b].append(a)
    K = int(input())
    cs = [int(s)-1 for s in input().split()]
    dist = []
    for i in range(K):
        diff = [-1 for _ in range(N)]
        diff[cs[i]] = 0
        queue = [cs[i]]
        ind = 0
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#!/usr/bin/env python3


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    N,M = map(int, input().split())
    edges = [[] for _ in range(N)]
    for _ in range(M):
        a,b = map(int,input().split())
        a-=1
        b-=1
        edges[a].append(b)
        edges[b].append(a)
    K = int(input())
    cs = [int(s)-1 for s in input().split()]
    dist = []
    for i in range(K):
        diff = [-1 for _ in range(N)]
        diff[cs[i]] = 0
        queue = [cs[i]]
        ind = 0
        while  ind<len(queue):
            v = queue[ind]
            ind += 1
            for v2 in edges[v]:
                #print(f"v={v}, v2={v2}")
                if diff[v2]==-1:
                    diff[v2] = diff[v]+1
                    queue.append(v2)
        # print(cs[i], diff)
        dist.append( [diff[cs[j]] for j in range(K)])

    # print(dist)
    for s in dist:
        if -1 in s:
            print(-1)
            return
    inf = 10**20
    dp = [ [inf for bin in range(2**K)] for t in range(K)]
    for t in range(K):
        dp[t][1<<t] = 1
    for bin in range(2**K):
        for t1 in range(K):
            for t2 in range(K):
                dp[t2][(1<<t2) | bin]  = min( dp[t2][(1<<t2) | bin], dp[t1][bin]+dist[t1][t2] )
    ret = min(dp[t][2**K-1] for t in range(K))
    print(ret)
    # Failed to predict input format
    pass

if __name__ == '__main__':
    main()

Submission Info

Judge Result