fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class Solution {
  5.     vector<int>* findEdit(unordered_map<int, unordered_map<int, pair<vector<int>*, int>>>& dp, int n, int x, int index, vector<vector<bool>> &graph, vector<string>& names, vector<string>& targetPath, int &edit) {
  6.         if(index >= targetPath.size()) return new vector<int>();
  7.         if(dp.find(x) != dp.end()) {
  8.             if(dp[x].find(index) != dp[x].end()) {
  9.                 edit = dp[x][index].second;
  10.                 return dp[x][index].first;
  11.             }
  12.         }
  13.         int res = INT_MAX;
  14.         vector<int> *soln;
  15.  
  16.         for(int i=0; i<n; i++) {
  17.             if(graph[x][i]) {
  18.                 int e=0;
  19.                  vector<int>* so = findEdit(dp, n, i, index+1, graph, names, targetPath, e);
  20.                 if(e<res) {
  21.                     res = e;
  22.                     soln = so;
  23.                 }
  24.             }
  25.         }
  26.         soln->push_back(x);
  27.  
  28.         if(names[x].compare(targetPath[index]) != 0) res++;
  29.         edit = res;
  30.         dp[x][index] = make_pair(soln, res);
  31.         return soln;
  32.     }
  33. public:
  34.     vector<int> mostSimilar(int n, vector<vector<int>> roads, vector<string> names, vector<string> targetPath) {
  35.         vector<vector<bool>> graph(n, vector<bool>(n, false));
  36.         for(int i=0; i<roads.size(); i++) {
  37.             graph[roads[i][0]][roads[i][1]] = graph[roads[i][1]][roads[i][0]] = true;
  38.         }
  39.         unordered_map<int, unordered_map<int, pair<vector<int>*, int>>> dp;
  40.         vector<int> *soln;
  41.         int res = INT_MAX;
  42.  
  43.         for(int i=0;i<n;i++) {
  44.             int e=0;
  45.             vector<int> *s = findEdit(dp, n, i, 0, graph, names, targetPath, e);
  46.             if(e<res){
  47.                 res = e;
  48.                 soln = s;
  49.             }
  50.         }
  51.         reverse(soln->begin(), soln->end());
  52.         return *soln;
  53.     }
  54. };
  55.  
  56. int main() {
  57. 	Solution s;
  58. 	auto ans = s.mostSimilar(5, {{0,2},{0,3},{1,2},{1,3},{1,4},{2,4}}, 
  59. 	{"ATL","PEK","LAX","DXB","HND"}, {"ATL","DXB","HND","LAX"});
  60. 	for (auto &a: ans)
  61. 	{
  62. 		cout << a << " ";
  63. 	}
  64. 	return 0;
  65. }
Success #stdin #stdout 0.01s 5512KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
4 3 2 1 1 4 0 3 2 4 1 0 2
https://ideone.com/4DHs2f
language:
C++ (gcc 8.3)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!