nikunjsoni

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.        
  5.         vector<vector<int>> adj(n);
  6.         int total_t = targetPath.size();
  7.         for (vector<int> road: roads) {
  8.             int u = road[0];
  9.             int v = road[1];
  10.             adj[u].push_back(v);
  11.             adj[v].push_back(u);
  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