Submission #6229243

---

Source Code Expand

import sys
input = sys.stdin.readline
from scipy.sparse import *

N,M,K = map(int,input().split())
C = input().split()
A,B = [],[]
for _ in range(M):
    a,b = map(lambda x: int(x)-1,input().split())
    A.append(a)
    B.append(b)

graph = csr_matrix(([1]*M,(A,B)),(N,N))

_,labels = csgraph.connected_components(graph,connection='strong')

# 縮約して作り直し
N = labels.max()
alphabets = [[] for _ in range(N+1)]
edges = [set() for _ in range(N+1)]

for i,c in enumerate(C):
    alphabets[labels[i]].append(c)
for a,b in zip(A,B):
    a1 = labels[a]
    b1 = labels[b]
    if a1 != b1:
        edges[a1].add(b1)

INF = chr(ord('z')+1)
dp = [[INF]*(K+1) for _ in range(N+1)] # 出発、長さ -> 辞書最小

def dfs(x):
    if dp[x][0] != INF:
        return
    alphabets[x].sort()
    my_str = ''.join(alphabets[x])[:K]
    len_me = len(my_str)
    for i in range(len_me+1):
        dp[x][i] = my_str[:i]
    for y in edges[x]:
        dfs(y)
        for i in range(len_me+1):
            left = my_str[:i]
            if left == INF:
                break
            for j in range(K+1):
                if i+j > K:
                    break
                right = dp[y][j]
                if right == INF:
                    break
                s = left + right
                if dp[x][i+j] > s:
                    dp[x][i+j] = s

for i in range(N+1):
    dfs(i)

answer = INF
for i in range(N+1):
    if answer > dp[i][K]:
        answer = dp[i][K]
if answer == INF:
    answer = '-1'

print(answer)

Submission Info

Judge Result