CCC2022S3题解解释

该题解题思路是基于图论和贪心算法的思想，需要首先将输入的任意两个字符串之间的编辑距离计算出来，并构建成一张加权无向图。其中，字符串之间的编辑距离通过Levenshtein距离计算得到。编辑距离的值作为图中边的权值，表示两个字符串之间的编辑距离。

接着，使用Prim算法求解这张加权无向图的最小生成树。最小生成树的边权值之和即为全局的最小编辑距离。具体实现过程中，需要先将任意两个字符串之间的编辑距离预处理出来，并构建成图的邻接矩阵。接下来，从任意一个字符串开始，按照Prim算法的思想，找到邻接矩阵中权值最小且未被处理过的边，加入到最小生成树中。然后，将新加入的边所连接的点标记为已处理过，继续寻找未处理过的最小边，直到所有点都被标记为已处理过。

下面给出Python代码示例：

import sys

def levenshtein(s, t):
    m, n = len(s), len(t)
    dp = [[0] * (n+1) for _ in range(m+1)]
    for i in range(1, m+1):
        dp[i][0] = i
    for j in range(1, n+1):
        dp[0][j] = j
    for i in range(1, m+1):
        for j in range(1, n+1):
            cost = 0 if s[i-1] == t[j-1] else 1
            dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1