結果

問題 No.95 Alice and Graph
コンテスト
ユーザー szkhts
提出日時 2026-06-22 09:51:47
言語 Python3
(3.14.3 + numpy 2.4.4 + scipy 1.17.1)
コンパイル:
python3 -mpy_compile _filename_
実行:
python3 _filename_
結果
TLE  
実行時間 -
コード長 1,840 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 467 ms
コンパイル使用メモリ 20,824 KB
実行使用メモリ 48,392 KB
最終ジャッジ日時 2026-06-22 09:52:36
合計ジャッジ時間 13,300 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 13
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
input = sys.stdin.readline

def solve():
    N, M, K = map(int, input().split())
    INF = 10**9

    # --- Floyd-Warshall 用行列 ---
    dist = [[INF]*N for _ in range(N)]
    for i in range(N):
        dist[i][i] = 0

    for _ in range(M):
        a, b = map(int, input().split())
        a -= 1; b -= 1
        dist[a][b] = dist[b][a] = 1

    # --- 全点間最短距離 ---
    for k in range(N):
        dk = dist[k]
        for i in range(N):
            di = dist[i]
            via = di[k]
            if via == INF:
                continue
            for j in range(N):
                nd = via + dk[j]
                if nd < di[j]:
                    di[j] = nd

    # --- 高い番号から貪欲に採用 ---
    V = [0]  # 必ず 0 番（頂点1）は入れておく
    score = 0

    for i in range(N-1, 0, -1):
        if len(V) >= K+1:
            break

        V.append(i)

        # bitDP: V の全頂点を巡回する最短距離
        L = len(V)
        dp = [[10**9]*L for _ in range(1 << L)]
        dp[1][0] = 0  # 最初は V[0]（頂点1）から開始

        for mask in range(1, 1 << L):
            for x in range(L):
                if not (mask & (1 << x)):
                    continue
                dpx = dp[mask][x]
                if dpx >= 10**9:
                    continue
                for y in range(L):
                    if mask & (1 << y):
                        continue
                    dp[mask | (1 << y)][y] = min(
                        dp[mask | (1 << y)][y],
                        dpx + dist[V[x]][V[y]]
                    )

        full = (1 << L) - 1
        ok = any(dp[full][j] <= K for j in range(L))

        if ok:
            score += (1 << i) - 1
        else:
            V.pop()

    print(score)


if __name__ == "__main__":
    solve()
0