Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Solution {
- public:
- vector<int> mostSimilar(int n, vector<vector<int>>& roads, vector<string>& names, vector<string>& targetPath) {
- vector<vector<int>> adj(n);
- int total_t = targetPath.size();
- for (vector<int> road: roads) {
- int u = road[0];
- int v = road[1];
- adj[u].push_back(v);
- adj[v].push_back(u);
- }
- vector<vector<int>> dp(n, vector<int>(total_t, INT_MAX));
- vector<vector<int>> parent(n, vector<int>(total_t, INT_MAX));
- // Set dp table for 1st city in target path.
- for (int u = 0; u < n; u++) {
- string city = targetPath[0];
- dp[u][0] = names[u] == city ? 0 : 1;
- }
- // For each city in target..
- for (int t = 1; t < total_t; t++) {
- // Compare the target city with every city.
- for (int u = 0; u < n; u++) {
- string city = targetPath[t];
- int cost = names[u] == city ? 0 : 1;
- int min_cost = INT_MAX;
- // For every neighbour of city, assume it to be previous target city.
- for (int neighbor : adj[u]) {
- int curr_total_cost = dp[neighbor][t-1] + cost;
- // Set cost and parent if min found.
- if (curr_total_cost < min_cost) {
- parent[u][t] = neighbor;
- min_cost = curr_total_cost;
- }
- }
- dp[u][t] = min_cost;
- }
- }
- // FInally find the path and return.
- vector<int> ans(total_t);
- int final_min_cost = INT_MAX;
- int last = -1;
- for (int u = 0; u < n; u++) {
- if (dp[u][total_t-1] < final_min_cost) {
- last = u;
- final_min_cost = dp[u][total_t-1];
- }
- }
- for (int t = total_t - 1; t>=0 ; t--) {
- ans[t] = last;
- last = parent[last][t];
- }
- return ans;
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement