結果

問題 No.95 Alice and Graph
ユーザー rpy3cpprpy3cpp
提出日時 2016-07-20 19:17:18
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,512 bytes
コンパイル時間 115 ms
コンパイル使用メモリ 12,800 KB
実行使用メモリ 18,560 KB
最終ジャッジ日時 2024-10-15 17:55:35
合計ジャッジ時間 24,575 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3,610 ms
18,304 KB
testcase_01 AC 606 ms
18,304 KB
testcase_02 AC 675 ms
18,304 KB
testcase_03 AC 130 ms
18,304 KB
testcase_04 TLE -
testcase_05 AC 4,130 ms
18,304 KB
testcase_06 AC 4,820 ms
18,432 KB
testcase_07 AC 606 ms
18,304 KB
testcase_08 AC 27 ms
10,880 KB
testcase_09 AC 26 ms
10,752 KB
testcase_10 AC 27 ms
10,752 KB
testcase_11 AC 33 ms
10,752 KB
testcase_12 AC 30 ms
10,880 KB
testcase_13 AC 356 ms
18,304 KB
権限があれば一括ダウンロードができます

ソースコード

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