結果

問題 No.95 Alice and Graph
コンテスト
ユーザー rpy3cpp
提出日時 2016-07-20 19:17:49
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 891 ms / 5,000 ms
コード長 2,512 bytes
コンパイル時間 361 ms
コンパイル使用メモリ 82,220 KB
実行使用メモリ 89,236 KB
最終ジャッジ日時 2024-11-14 13:36:32
合計ジャッジ時間 5,641 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

def read_data():
    N, M, K = map(int, input().split())
    Es = [[] for i in range(N)]
    for m in range(M):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        Es[u].append(v)
        Es[v].append(u)
    return N, M, K, Es

def solve(N, M, K, Es):
    '''
    dist[u][v]: 頂点 u から頂点 v までの距離
    used: 訪問対象として選択された頂点のリスト
    '''
    global dp
    if K == 0 or M == 0:
        return 0
    dp = [[float('inf')] * (K + 1) for mask in range(1 << K)]
    dp[0][0] = 0
    dist = calc_dist(N, Es)
    score = 0
    used = [0]
    for u in range(N - 1, 0, -1):
        if dist[0][u] > K:
            continue
        if can_reach(u, used, dist, K):
            used.append(u)
            score += (1 << u) - 1
        if len(used) == K + 1:
            break
    return score

def calc_dist(N, Es):
    dist = [[float('inf')] * N for i in range(N)]
    for i in range(N):
        dist[i][i] = 0
    for u, neighbours in enumerate(Es):
        for v in neighbours:
            dist[u][v] = 1
    for i in range(N):
        for u in range(N):
            for v in range(N):
                dist[u][v] = min(dist[u][v], dist[u][i] + dist[i][v])
    return dist

def can_reach(u, used, dist, K):
    '''
    dp[mask][u]: mask でbitの立った頂点をすべて訪問し、最後に 頂点 u に至る経路の、最小コスト
    頂点番号 0 は、始点で、常に訪問先の中に含まれているから、maskには含まないことにする。
    ただし、dp[mask][u] や dist[u][v] の u, v には、頂点番号0 も含む。
    '''
    global dp
    vs = used + [u]
    k = len(vs) - 1
    mydist = [[dist[i][j] for j in vs] for i in vs]
    begin = 1 << (k - 1)
    end = 1 << k
    dp[begin][k] = mydist[0][k]
    for mask in range(begin + 1, end):
        dpm = dp[mask]
        for v in range(k):  # 頂点番号より 1 少ない値を使用。
            if (1 << v) & mask:
                submask = mask ^ (1 << v)
                distv = mydist[v + 1]
                dps = dp[submask]
                dpmv = float('inf')
                for u in range(k):  # 頂点番号より 1 少ない値を使用。
                    if (1 << u) & submask:
                        tmp = dps[u + 1] + distv[u + 1]
                        if tmp < dpmv:
                            dpmv = tmp
                dpm[v + 1] = dpmv
    return min(dp[end - 1]) <= K

N, M, K, Es = read_data()
print(solve(N, M, K, Es))
0