fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int n;
  5. vector<int> words;
  6. vector<int> wlen;
  7.  
  8. int main() {
  9. 	ios::sync_with_stdio(0), cin.tie(0);
  10. 	cin >> n;
  11. 	words.resize(n);
  12. 	wlen.resize(n);
  13. 	for (int i = 0; i < n; i++) {
  14. 		string s;
  15. 		cin >> s;
  16. 		int cur = 0;
  17. 		wlen[i] = int(s.size());
  18. 		for (int j = 0; j < wlen[i]; j++) {
  19. 			cur = 2 * cur + int(s[j] - '0');
  20. 		}
  21. 		words[i] = cur;
  22. 	}
  23. 	priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
  24. 	vector<vector<int> > dist(n);
  25. 	for (int i = 0; i < n; i++) {
  26. 		dist[i].assign(wlen[i]+1, -1);
  27. 		dist[i][wlen[i]] = wlen[i];
  28. 		pq.push(make_pair(wlen[i], i * 20 + wlen[i]));
  29. 	}
  30. 	while (!pq.empty()) {
  31. 		int d = pq.top().first;
  32. 		int cur = pq.top().second;
  33. 		int i = cur / 20;
  34. 		int r = cur % 20;
  35. 		pq.pop();
  36. 		if (r == 0) {
  37. 			cout << d << '\n';
  38. 			exit(0);
  39. 		}
  40. 		if (dist[i][r] < d) continue;
  41. 		int suffix = words[i] & ((1 << r) - 1);
  42. 		for (int j = 0; j < n; j++) {
  43. 			if (i == j && r == wlen[j]) continue;
  44. 			int newi = -1, newr = -1, extra = 0;
  45. 			if (wlen[j] <= r) {
  46. 				if ((suffix >> (r - wlen[j])) == words[j]) {
  47. 					newi = i;
  48. 					newr = r - wlen[j];
  49. 					extra = 0;
  50. 				}
  51. 			} else {
  52. 				if (suffix == (words[j] >> (wlen[j] - r))) {
  53. 					newi = j;
  54. 					newr = wlen[j] - r;
  55. 					extra = newr;
  56. 				}
  57. 			}
  58. 			if (newi == -1) continue;
  59. 			int newd = d + extra;
  60. 			if (dist[newi][newr] == -1 || dist[newi][newr] > newd) {
  61. 				dist[newi][newr] = newd;
  62. 				pq.push(make_pair(newd, newi * 20 + newr));
  63. 			}
  64. 		}
  65. 	}
  66. 	cout << 0 << '\n';
  67. }
  68.  
Success #stdin #stdout 0s 4388KB
comments (?)
stdin
copy 
10
1001
1011
01000
00011
01011
1010
00100
10011
11110
0110
stdout
copy 
13
https://ideone.com/7Rb0ps
language:
C++14 (gcc 8.3)
created:
4 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!