fork download
copy 
  1. #include <iostream>
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <string.h>
  5. #include <algorithm>
  6. using namespace std;
  7. #define re(i, n) for (int i=0; i<n; i++)
  8. #define re1(i, n) for (int i=1; i<=n; i++)
  9. #define re2(i, l, r) for (int i=l; i<r; i++)
  10. #define re3(i, l, r) for (int i=l; i<=r; i++)
  11. #define rre(i, n) for (int i=n-1; i>=0; i--)
  12. #define rre1(i, n) for (int i=n; i>0; i--)
  13. #define rre2(i, r, l) for (int i=r-1; i>=l; i--)
  14. #define rre3(i, r, l) for (int i=r; i>=l; i--)
  15. #define ll long long
  16. const int MAXN = 50010, MAXM = 7000010, INF = ~0U >> 2;
  17. struct edge {
  18.     int b, w, next;
  19. } E[MAXM];
  20. int n, m = 0, s, t, n0, A0[MAXN][10], hd[MAXN], tl[MAXN], WW[10], dist[MAXN], No[MAXN], pos[MAXN], res = 0;
  21. ll A[MAXN], B0[10];
  22. char sss[20];
  23. void init()
  24. {
  25. 	scanf("%d", &n);
  26. 	re(i, 10) scanf("%d", &WW[i]);
  27. 	re(i, n) {scanf("%s", sss); A[i] = 0; re(j, 10) A[i] = A[i] * 10 + sss[j] - 48;}
  28. }
  29. void add_edge(int a, int b, int w)
  30. {
  31. 	E[m].b = b; E[m].w = w; E[m].next = -1; if (hd[a] == -1) hd[a] = m; else E[tl[a]].next = m; tl[a] = m++;
  32. }
  33. void prepare()
  34. {
  35. 	ll sw = A[0], tw = A[n - 1], x; sort(A, A + n);
  36. 	re(i, n) {
  37. 		if (A[i] == sw) s = i; if (A[i] == tw) t = i; hd[i] = tl[i] = -1;
  38. 		x = A[i]; rre(j, 10) {A0[i][j] = x % 10; x /= 10;}
  39. 	}
  40. 	B0[9] = 1; rre(i, 9) B0[i] = B0[i + 1] * 10;
  41. 	int l, r, mid, kk; ll y;
  42. 	re(i, n) {
  43. 		re(j, 10) {
  44. 			x = A[i] - A0[i][j] * B0[j];
  45. 			re(k, 10) {
  46. 				if (k != A0[i][j]) {
  47. 					l = 0; r = n - 1; kk = -1;
  48. 					while (l <= r) {mid = l + r >> 1; y = A[mid]; if (y == x) {kk = mid; break;} else if (y < x) l = mid + 1; else r = mid - 1;}
  49. 					if (kk >= 0) add_edge(i, kk, WW[j]);
  50. 				}
  51. 				x += B0[j];
  52. 			}
  53. 		}
  54. 		re(j, 9) re2(k, j+1, 10) if (A0[i][j] != A0[i][k]) {
  55. 			x = A[i] - A0[i][j] * B0[j] - A0[i][k] * B0[k];
  56. 			x += A0[i][k] * B0[j] + A0[i][j] * B0[k];
  57. 			l = 0; r = n - 1; kk = -1;
  58. 			while (l <= r) {mid = l + r >> 1; y = A[mid]; if (y == x) {kk = mid; break;} else if (y < x) l = mid + 1; else r = mid - 1;}
  59. 			if (kk >= 0) add_edge(i, kk, WW[j]);
  60. 		}
  61. 	}
  62. }
  63. void swap(int s1, int s2)
  64. {
  65. 	pos[No[s1]] = s2; pos[No[s2]] = s1; int tmp = No[s1]; No[s1] = No[s2]; No[s2] = tmp;
  66. }
  67. void heap_up(int x)
  68. {
  69. 	int y; while (x > 1 && dist[No[x]] < dist[No[y = x >> 1]]) {swap(x, y); x = y;}
  70. }
  71. void heap_down(int x)
  72. {
  73. 	int lc = x << 1;
  74. 	if (lc > n0) return; else if (lc == n0) {
  75. 		if (dist[No[x]] > dist[No[lc]]) swap(x, lc); return;
  76. 	} else {
  77. 		int d0 = dist[No[x]], d1 = dist[No[lc]], d2 = dist[No[lc + 1]];
  78. 		if (d0 <= d1 && d0 <= d2) return; else if (d1 <= d2) {swap(x, lc); heap_down(lc);} else {swap(x, lc + 1); heap_down(lc + 1);}
  79. 	}
  80. }
  81. void del_root()
  82. {
  83. 	swap(1, n0); n0--; heap_down(1);
  84. }
  85. void solve()
  86. {
  87. 	re(i, n) {No[i + 1] = i; pos[i] = i + 1; dist[i] = INF;} dist[s] = 0; swap(1, s + 1);
  88. 	int x, y, d0, d1; n0 = n;
  89. 	re2(i, 1, n) {
  90. 		x = No[1]; del_root(); d0 = dist[x];
  91. 		for (int p=hd[x]; p != -1; p=E[p].next) {
  92. 			y = E[p].b; d1 = d0 + E[p].w;
  93. 			if (d1 < dist[y]) {dist[y] = d1; heap_up(pos[y]);}
  94. 		}
  95. 	}
  96. 	res = dist[t];
  97. }
  98. void pri()
  99. {
  100. 	if (res == INF) printf("%d\n", -1); else printf("%d\n", res);
  101. }
  102. int main()
  103. {
  104. 	init();
  105. 	prepare();
  106. 	solve();
  107. 	pri();
  108. 	return 0;
  109. }
  110.  
Success #stdin #stdout 0.01s 88064KB
comments (?)
stdin
copy 
5
100 10 10 10 1 1 1 1 1 1
9123493342
3123493942
9223433942
3223493942
9223433945
stdout
copy 
211
https://ideone.com/T8Ad8p
language:
C++ (gcc 8.3)
created:
12 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!