LeetCode 1548. The Most Similar Path in a Graph（动态规划）
LeetCode 1548. The Most Similar Path in a Graph（动态规划）
文章目录
1. 题目
We have n cities and m bi-directional roads where roads[i] = [ai, bi] connects city ai with city bi. Each city has a name consisting of exactly 3 upper-case English letters given in the string array names. Starting at any city x, you can reach any city y where y != x (i.e. the cities and the roads are forming an undirected connected graph).
You will be given a string array targetPath. You should find a path in the graph of the same length and with the minimum edit distance to targetPath.
You need to return the order of the nodes in the path with the minimum edit distance, The path should be of the same length of targetPath and should be valid (i.e. there should be a direct road between ans[i] and ans[i + 1]). If there are multiple answers return any one of them.
The edit distance is defined as follows:
Follow-up: If each node can be visited only once in the path, What should you change in your solution?
Example 1:
Input: n = 5,
roads = [[0,2],[0,3],[1,2],[1,3],[1,4],[2,4]],
names = ["ATL","PEK","LAX","DXB","HND"],
targetPath = ["ATL","DXB","HND","LAX"]
Output: [0,2,4,2]
Explanation: [0,2,4,2], [0,3,0,2] and [0,3,1,2] are accepted answers.
[0,2,4,2] is equivalent to ["ATL","LAX","HND","LAX"] which has edit distance = 1 with targetPath.
[0,3,0,2] is equivalent to ["ATL","DXB","ATL","LAX"] which has edit distance = 1 with targetPath.
[0,3,1,2] is equivalent to ["ATL","DXB","PEK","LAX"] which has edit distance = 1 with targetPath.Example 2:
Input: n = 4,
roads = [[1,0],[2,0],[3,0],[2,1],[3,1],[3,2]],
names = ["ATL","PEK","LAX","DXB"],
targetPath = ["ABC","DEF","GHI","JKL","MNO","PQR","STU","VWX"]
Output: [0,1,0,1,0,1,0,1]
Explanation: Any path in this graph has edit distance = 8 with targetPath.Example 3:
Input: n = 6,
roads = [[0,1],[1,2],[2,3],[3,4],[4,5]],
names = ["ATL","PEK","LAX","ATL","DXB","HND"],
targetPath = ["ATL","DXB","HND","DXB","ATL","LAX","PEK"]
Output: [3,4,5,4,3,2,1]
Explanation: [3,4,5,4,3,2,1] is the only path with edit distance = 0 with targetPath.
It's equivalent to ["ATL","DXB","HND","DXB","ATL","LAX","PEK"]
Constraints:
2 <= n <= 100
m == roads.length
n - 1 <= m <= (n * (n - 1) / 2)
0 <= ai, bi <= n - 1
ai != bi
The graph is guaranteed to be connected and each pair of nodes may have at most one direct road.
names.length == n
names[i].length == 3
names[i] consists of upper-case English letters.
1 <= targetPath.length <= 100
targetPath[i].length == 3
targetPath[i] consists of upper-case English letters.来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/the-most-similar-path-in-a-graph 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 解题
class Solution {
public:
vector<int> mostSimilar(int n, vector<vector<int>>& roads, vector<string>& names, vector<string>& targetPath) {
vector<vector<int>> g(n);
for(auto& r : roads)
{
g[r[0]].push_back(r[1]);
g[r[1]].push_back(r[0]);
}//建图
int len = targetPath.size();
vector<vector<int>> dp(len, vector<int>(n, INT_MAX));
//走完 ？target后的 在城市 ni 的最小编辑距离
vector<vector<int>> path1(n);//n个城市作为结束的最佳路线
vector<vector<int>> path2(n);//存储下一个状态的路径
for(int i = 0; i < n; ++i)//初始化
{
dp[0][i] = (names[i] != targetPath[0]);
path1[i].push_back(i);
}
int mindis = INT_MAX, minidx = -1;
for(int k = 1; k < len; ++k)
{ //样本维度
for(int i = 0; i < n; ++i)
{ //前一个城市
if(dp[k-1][i] == INT_MAX)
continue;
for(int j : g[i])
{ //下一个相连的城市
if(dp[k][j] > dp[k-1][i]+(names[j]!=targetPath[k]))
{
dp[k][j] = dp[k-1][i]+(names[j]!=targetPath[k]);
path2[j] = path1[i];
path2[j].push_back(j);
}
}
}
swap(path1, path2);//滚动数组，更新当前的最佳路径至path1
}
for(int i = 0; i < n; i++)
{
if(mindis > dp[len-1][i])
{
mindis = dp[len-1][i];
minidx = i;
}
}//取编辑距离最小的城市编号
return path1[minidx];//返回路径
}
};1260 ms 109.6 MB
腾讯云开发者
