逆向きに考え、\(d[i][x]\) を「頂点 \(x\) 、\(k=i\) から始めた時に両者が最善に行動した時に最終的に得られる文字列」として定義した DP を考えます。

この DP は \(i\) の偶奇に対し文字列の辞書順最小・最大をそれぞれ計算することで計算することができますが、このままだと計算量が \(O(NM+NK^2)\) となり TLE ないし MLE となります。

辞書順最小・最大を考える際、最も重要なのは \(1\) 文字目で、\(1\) 文字目が同じ場合は \(2\) 文字目以降の辞書順を比較することになります。したがって、\(d'[i][x]\) を「\(d[i][x]\) が \(d[i][1],d[i][2],\ldots,d[i][N]\) の中で辞書順で何番目に小さいか」として \(d\) ではなく \(d'\) を順に計算していくことでこの問題に正答することができます。計算量は \(O(NM+NK)\) です。

実装例(Python3)

n, m, k = map(int, input().split())
g = [[] for _ in range(n)]
for i in range(m):
    u, v, c = map(str, input().split())
    g[int(v) - 1].append((int(u) - 1, c))
to = [[-1] * n for _ in range(2 * k)]
ch = [["?"] * n for _ in range(2 * k)]
d = [0] * n
INF = 10**9
for turn in range(2 * k):
    if turn % 2 == 1:  # Alice
        dd = [INF] * n
        for x in range(n):
            for y, c in g[x]:
                val = ord(c) + d[x] * 26
                if dd[y] > val:
                    dd[y] = val
                    to[turn][y] = x
                    ch[turn][y] = c
        d = dd
    else:  # Bob
        dd = [-1] * n
        for x in range(n):
            for y, c in g[x]:
                val = ord(c) + d[x] * 26
                if dd[y] < val:
                    dd[y] = val
                    to[turn][y] = x
                    ch[turn][y] = c
        d = dd
    b = sorted(set(d))
    dc = {v: i for i, v in enumerate(b)}
    d = list(map(lambda v: dc[v], d))
ans = []
now = 0
for turn in reversed(range(2 * k)):
    ans.append(ch[turn][now])
    now = to[turn][now]
print("".join(ans[::-1]))