結果

問題 No.1780 [Cherry Anniversary] 真冬に咲く26の櫻の木
ユーザー gew1fw
提出日時 2025-06-12 15:35:24
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,477 bytes
コンパイル時間 190 ms
コンパイル使用メモリ 82,636 KB
実行使用メモリ 169,184 KB
最終ジャッジ日時 2025-06-12 15:36:13
合計ジャッジ時間 5,387 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 14 TLE * 1 -- * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    input = sys.stdin.read().split()
    idx = 0

    C = list(map(int, input[idx:idx+26]))
    idx +=26

    K = list(map(int, input[idx:idx+26]))
    idx +=26

    N = int(input[idx])
    idx +=1

    abilities = {}
    for _ in range(N):
        S = input[idx]
        A = int(input[idx+1])
        B = int(input[idx+2])
        E = int(input[idx+3])
        idx +=4
        for c in S:
            if c not in abilities:
                abilities[c] = []
            abilities[c].append((A, B, E))
            abilities[c].append((B, A, E))

    alphabet = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
    trees = {}
    for i in range(26):
        c = alphabet[i]
        trees[c] = {
            'C': C[i],
            'K': K[i],
            'abilities': abilities.get(c, [])
        }

    max_sum = -float('inf')
    found = False

    for target in range(1, 17):
        possible = True
        total = 0
        for c in alphabet:
            tree = trees[c]
            if tree['K'] == 0:
                if tree['C'] != target:
                    possible = False
                    break
                else:
                    continue

            edges = tree['abilities']
            n = 16
            V = 16

            graph = [[] for _ in range(V+1)]
            for a, b, e in edges:
                graph[a].append((b, e))
                graph[b].append((a, e))

            start = tree['C']
            end = target

            dist = [-float('inf')] * (V+1)
            dist[start] = 0
            for _ in range(tree['K']):
                updated = False
                new_dist = [x for x in dist]
                for u in range(1, V+1):
                    if dist[u] == -float('inf'):
                        continue
                    for (v, e) in graph[u]:
                        if dist[u] + e > new_dist[v]:
                            new_dist[v] = dist[u] + e
                            updated = True
                dist = new_dist
                if not updated:
                    break

            if dist[end] == -float('inf'):
                possible = False
                break

            max_energy = dist[end]

            total += max_energy

        if possible:
            if total > max_sum:
                max_sum = total
                found = True

    if found:
        print(max_sum)
    else:
        print("Impossible")

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