# 1548

Jul 26th, 2021
119
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. class Solution {
2. public:
3.     vector<int> mostSimilar(int n, vector<vector<int>>& roads, vector<string>& names, vector<string>& targetPath) {
4.
6.         int total_t = targetPath.size();
12.         }
13.
14.
15.         vector<vector<int>> dp(n, vector<int>(total_t, INT_MAX));
16.         vector<vector<int>> parent(n, vector<int>(total_t, INT_MAX));
17.
18.         // Set dp table for 1st city in target path.
19.         for (int u = 0; u < n; u++) {
20.             string city = targetPath[0];
21.             dp[u][0] = names[u] == city ? 0 : 1;
22.         }
23.
24.         // For each city in target..
25.         for (int t = 1; t < total_t; t++) {
26.             // Compare the target city with every city.
27.             for (int u = 0; u < n; u++) {
28.                 string city = targetPath[t];
29.                 int cost =  names[u] == city ? 0 : 1;
30.                 int min_cost = INT_MAX;
31.
32.                 // For every neighbour of city, assume it to be previous target city.
33.                 for (int neighbor : adj[u]) {
34.                     int curr_total_cost = dp[neighbor][t-1] + cost;
35.                     // Set cost and parent if min found.
36.                     if (curr_total_cost < min_cost) {
37.                         parent[u][t] = neighbor;
38.                         min_cost = curr_total_cost;
39.                     }
40.                 }
41.                 dp[u][t] = min_cost;
42.             }
43.         }
44.
45.         // FInally find the path and return.
46.         vector<int> ans(total_t);
47.         int final_min_cost = INT_MAX;
48.         int last = -1;
49.         for (int u = 0; u < n; u++) {
50.             if (dp[u][total_t-1] < final_min_cost) {
51.                 last = u;
52.                 final_min_cost = dp[u][total_t-1];
53.             }
54.         }
55.
56.         for (int t = total_t - 1; t>=0 ; t--) {
57.             ans[t] = last;
58.             last = parent[last][t];
59.         }
60.         return ans;
61.
62.     }
63. };
RAW Paste Data