fork download
copy 
  1. /*
  2. 98 22 17 13
  3. 117 24 50 94 157 116 52 179 68 171 106 137 61 22 128 151 54 81 195 62 182 192
  4. 194 11 169 48 122 144 82 151 16 103 152 118 164 41 92 133 28 127 66 144 6 111
  5. 78 41 35 32 25 167 176 25 188 157 143 199 172 21 166 182 62 7 13 163 165 116
  6. 190 103 154 192 160 78 140 128 44 145 24 8 52 176 26 40 112 52 45 8 76 52
  7. 71 161 47 158 169 174 164 41 5 91 142 168 17 44 176 73 131 162 171 47 37 106
  8. 91 5 115 30 84 29 186 144 112 64 27 43 133 198 113 132 85 168 200 90 30 124
  9. 102 74 187 168 54 190 2 27 74 79 80 97 17 72 2 13 130 197 157 156 8 20
  10. 88 31 102 90 112 65 181 73 132 194 59 25 187 11 198 141 19 131 58 31 195 146
  11. 39 150 11 164 54 23 26 200 157 154 80 89 66 15 166 172 20 113 26 43 96 1
  12. 119 66 59 150 69 176 59 131 29 169 187 25 119 145 30 111 119 155 91 159 101 139
  13. 122 140 141 81 135 193 87 167 76 139 71 116 140 65 31 50 77 106 20 69 181 168
  14. 103 190 113 172 20 199 98 187 152 87 153 55 22 71 43 41 123 70 152 29 187 171
  15. 49 14 51 9 169 77 193 168 14 132 169 169 56 151 57 162 145 37 55 139 188 114
  16. 42 176 43 161 174 120 172 66 19 117 76 102 40 45 151 130 21 8 182 75 158 19
  17. 130 151 47 29 200 85 76 8 158 101 143 10 101 106 112 92 103 63 176 35 42 144
  18. 174 85 190 11 22 150 92 39 7 52 168 36 84 40 144 155 69 174 77 22 23 150
  19. 161 171 9 132 105 70 40 20 14 69 29 99 15 128 70 178 193 176 155 12 57 134
  20. 145 82 65 111 164 53 49 151 160 84 40 197 169 118 196 126 116 58 198 148 78 53
  21. 113 79 147 124 68 180 137 146 110 134 126 69 186 2 80 100 43 120 148 91 98 135
  22. 160 67 181 167 157 19 42 165 95 52 93 98 23 43 182 61 91 144 62 51 36 63
  23. 76 148 176 172 11 23 193 37 30 49 118 34 95 90 193 160 99 16 185 71 186 176
  24. 80 113 70 170 16 156 11 29 65 113 142 83 6 61 64 182 57 136 77 179 12 109
  25. 23 86 10 57 65 142 20 56 153 66 120 156 173 4 112 175 34 109 55 91 169 121
  26. 57 31 107 148 11 29 150 14 72 82 48 75 38 174 75 126 137 21 106 15 22 189
  27. 75 106 146 97 45 90 28 52 108 53 17 82 99 34 79 4 106 49 132 187 104 74
  28. 127 127 106 32 70 151 52 31 50 12 167 196 48 17 140 68 90 174 160 48 102 14
  29. 57 79 165 141 168 60 54 86 87 58 35 51 173 69 157 198 152 155 52 144 146 138
  30. 49 73 142 68 128 151 61 17 32 2 188 83 157 199 41 104 136 115 14 163 180 3
  31. 69 188 28 122 125 17 20 195 51 141 14 31 132 41 78 32 154 120 55 87 93 111
  32. 23 132 133 76 72 148 61 157 185 191 57 53 85 82 84 44 66 187 27 196 133 100
  33. 46 99 59 121 24 61 155 149 92 153 83 106 27 88 192 159 59 33 162 79 10 9
  34. 191 176 196 25 118 169 161 200 103 192 179 50 105 138 198 121 44 68 32 195 105 114
  35. 43 29 55 94 33 47 135 147 8 7 177 2 118 10 48 173 46 96 116 50 83 199
  36. 135 27 109 91 171 195 18 85 169 195 182 97 85 167 30 149 80 98 2 111 141 97
  37. 33 110 17 151 17 108 165 28 167 41 45 147 196 43 14 20 9 166 44 15 116 39
  38. 41 163 187 117 53 86 88 1 42 69 14 197 127 142 84 36 104 108 31 137 52 115
  39. 108 162 151 101 158 38 8 20 21 108 181 169 32 190 126 53 100 30 144 126 93 40
  40. 171 139 92 25 126 115 98 174 50 163 133 71 92 63 72 69 126 148 15 74 160 43
  41. 52 136 187 192 179 165 103 179 21 102 86 86 99 98 120 41 49 200 152 115 198 10
  42. 79 74 120 52 143 85 61 16 66 47 55 20 109 150 176 183 15 13 79 71 22 183
  43. 169 23 37 182 91 191 54 43 7 164 54 198 190 74 153 39 125 23 20 142 10 97
  44. 106 65 145 139 200 12 34 68 53 14 5 80 132 1 17 20 101 42 137 92 59 138
  45. 97 119 134 172 79 29 140 32 141 88 83 119 150 169 19 32 79 140 26 115 152 126
  46. 159 4 115 86 83 57 172 2 165 103 177 196 45 67 109 85 11 117 127 71 25 89
  47. 64 49 158 65 197 159 76 13 130 65 133 93 128 149 9 24 103 79 11 70 96 111
  48. 126 123 68 44 185 4 9 56 194 135 31 172 138 70 197 166 21 117 130 175 38 109
  49. 57 34 104 95 195 50 167 116 3 67 200 93 119 180 79 39 51 147 176 1 2 137
  50. 48 81 175 88 156 91 152 50 58 131 125 156 7 110 56 123 136 60 77 189 109 153
  51. 99 172 171 164 36 174 65 23 106 192 38 64 154 85 129 87 69 25 104 41 148 163
  52. 5 60 29 18 54 53 84 103 140 63 19 12 79 164 44 163 143 184 6 162 62 124
  53. 47 13 36 41 65 117 195 21 168 160 4 195 2 32 89 150 48 192 29 134 165 5
  54. 81 23 76 137 137 125 79 182 134 101 189 153 157 8 27 117 40 193 47 81 123 177
  55. 72 172 73 144 18 137 64 103 193 166 123 132 124 177 159 38 172 132 40 106 141 48
  56. 84 133 116 97 184 147 137 193 98 159 71 159 38 131 34 113 13 187 104 55 116 181
  57. 3 26 1 3 174 173 58 53 54 139 193 112 3 73 171 76 151 85 113 149 110 56
  58. 17 143 191 120 93 191 106 176 35 200 122 124 7 116 181 40 38 156 105 56 12 161
  59. 65 6 145 43 57 143 200 34 38 175 104 148 177 190 70 78 110 82 26 86 8 39
  60. 33 64 96 117 59 72 189 130 46 16 54 135 147 50 14 14 143 64 79 100 28 81
  61. 170 116 193 159 173 133 160 7 150 164 119 17 63 29 65 121 99 182 85 164 25 76
  62. 151 31 38 43 6 133 95 168 54 87 136 17 126 97 22 199 45 67 28 122 89 101
  63. 68 46 200 30 115 30 34 151 146 158 63 59 139 196 69 194 161 186 172 142 3 141
  64. 118 13 194 34 121 41 177 34 47 93 132 155 176 129 172 153 150 135 91 188 89 142
  65. 10 44 28 119 187 10 176 94 52 33 127 179 65 165 92 106 21 75 145 24 26 81
  66. 33 48 167 191 167 165 169 150 199 96 110 176 195 195 126 73 56 159 58 196 67 51
  67. 186 200 62 111 113 189 88 144 20 162 179 124 19 81 39 176 39 141 63 32 117 82
  68. 163 104 105 22 38 192 150 30 65 77 45 92 199 37 61 176 26 91 194 85 54 197
  69. 169 118 133 58 58 168 19 103 31 145 106 140 125 177 177 83 152 64 128 184 11 168
  70. 8 71 128 69 160 122 37 42 131 139 184 62 32 49 133 183 98 134 149 141 154 120
  71. 25 74 129 190 7 17 82 94 188 173 119 4 3 91 107 13 77 10 80 29 57 65
  72. 170 78 102 83 36 179 87 79 9 148 158 26 46 178 52 41 134 141 23 57 133 195
  73. 134 130 129 28 17 4 38 116 100 8 162 25 149 178 97 166 20 158 97 47 75 56
  74. 47 46 46 16 140 150 101 86 51 141 87 99 44 183 98 56 110 184 120 34 136 58
  75. 67 55 113 129 13 106 88 59 9 101 54 196 142 47 172 96 117 4 199 106 161 77
  76. 179 13 71 7 126 121 78 48 140 97 152 143 180 66 89 148 104 14 64 40 50 34
  77. 12 69 150 13 8 193 179 194 170 32 46 7 161 8 56 183 61 81 102 181 43 20
  78. 162 83 129 2 16 129 15 97 84 137 55 147 42 115 46 191 181 109 59 164 140 109
  79. 199 59 67 130 46 93 166 103 85 141 187 186 68 15 40 4 151 144 106 81 159 136
  80. 168 139 182 38 103 194 59 2 71 15 122 33 54 161 168 140 124 112 166 138 15 183
  81. 3 160 112 95 127 62 61 50 173 156 96 141 41 156 72 194 27 33 198 5 146 185
  82. 83 141 52 39 152 69 76 156 38 124 118 175 48 178 112 42 165 28 33 87 42 129
  83. 150 147 144 157 42 42 129 14 54 147 17 6 145 133 75 65 154 82 17 192 188 91
  84. 80 12 177 157 163 102 98 106 70 135 182 186 78 35 177 140 152 164 174 96 184 164
  85. 57 31 131 3 38 85 174 170 14 165 56 182 139 21 165 65 89 84 29 38 16 98
  86. 164 148 159 199 75 197 44 150 144 191 49 163 177 74 145 75 167 83 19 19 8 120
  87. 85 28 117 77 182 149 149 175 37 50 193 119 109 187 19 106 101 48 25 198 75 163
  88. 118 159 98 142 114 123 84 136 112 114 145 18 193 2 39 198 8 66 172 186 85 46
  89. 35 1 118 106 132 195 51 35 15 119 104 154 193 190 41 154 48 57 33 140 20 173
  90. 3 40 87 150 100 23 22 98 129 55 72 32 29 31 23 17 46 20 68 149 41 179
  91. 168 161 98 103 40 88 177 189 120 23 17 62 140 189 3 70 195 155 107 83 109 32
  92. 17 135 38 81 2 41 163 167 112 137 101 49 71 11 12 196 73 142 197 71 13 142
  93. 167 92 44 22 170 36 140 98 129 82 200 91 18 163 39 92 84 116 116 22 144 189
  94. 79 47 75 173 130 167 74 6 158 190 199 98 94 16 172 166 12 107 37 21 180 59
  95. 171 24 14 100 102 197 71 40 122 62 138 16 61 12 2 184 152 19 60 183 21 7
  96. 179 36 128 47 172 88 128 89 67 87 184 95 77 128 49 177 40 192 3 59 64 169
  97. 131 128 99 33 135 54 151 40 144 148 106 58 79 161 2 151 91 183 63 39 18 193
  98. 150 145 14 80 39 93 26 116 137 49 133 33 140 138 70 96 103 179 33 111 27 10
  99. 64 36 16 113 102 62 110 2 136 172 183 23 77 27 196 81 39 49 5 175 106 167
  100. 196 146 77 7 116 190 47 115 182 36 172 38 60 125 96 14 74 49 83 170 194 34
  101. 1 5
  102. 8 10
  103. 14 17
  104. 21 25
  105. 28 31
  106. 32 34
  107. 35 36
  108. 38 41
  109. 44 45
  110. 48 51
  111. 54 55
  112. 59 60
  113. 62 66
  114. 68 72
  115. 74 76
  116. 77 78
  117. 81 83
  118. 84 22 62 9
  119. */
  120.  
  121. // Đạt đz s1 tg
  122.  
  123. #include <bits/stdc++.h>
  124.  
  125. #define f first
  126. #define s second
  127. #define mod 1000000007
  128. #define PB push_back
  129. #define PF push_front
  130. #define inf 10000007
  131. #define round(m,n) setprecision((int)m) << fixed << double(n)
  132. #define ll long long
  133. #define int long long
  134. #define bit(x, i) ((x >> i) & 1)
  135. #define pii pair<int, int>
  136. #define TASK "exbot"
  137.  
  138. using namespace std;
  139.  
  140. void ADD(int &x, int y){
  141.     x += y;
  142.     if (x >= mod) x -= mod;
  143.     if (x < 0) x += mod;
  144. }
  145.  
  146. int n, m, q, W;
  147. int a[1505][1505];
  148. int X1, Y1, x2, y2;
  149. pii b[100005];
  150. int w[1505][1505];
  151. int dx[4] = {0, 1, 0, -1};
  152. int dy[4] = {1, 0, -1, 0};
  153.  
  154. struct gay{
  155.     int x, y, w;
  156. };
  157.  
  158. struct comp{
  159.     bool operator()(const gay &a, const gay &b){
  160.         return a.w > b.w;
  161.     }
  162. };
  163.  
  164. int Path(){
  165.     for(int i = 1; i <= n; i++)
  166.     for(int j = 1; j <= m; j++)
  167.         w[i][j] = 2e15;
  168.  
  169.     w[X1][Y1] = a[X1][Y1];
  170.     priority_queue<gay, vector<gay>, comp> q;
  171.     q.push({X1, Y1, a[X1][Y1]});
  172.     while(q.size()){
  173.         gay x = q.top();
  174.         q.pop();
  175.         for(int i = 0; i <= 3; i++){
  176.             int u = x.x + dx[i];
  177.             int v = x.y + dy[i];
  178.             if(u < 1 || u > n) continue;
  179.             if(v < 1 || v > m) continue;
  180.             if(w[u][v] > x.w + a[u][v]){
  181.                 w[u][v] = x.w + a[u][v];
  182.                 q.push({u, v, w[u][v]});
  183.             }
  184.         }
  185.     }
  186.     return w[x2][y2] - a[x2][y2];
  187. }
  188.  
  189. void sub12(){
  190.     cout << Path();
  191. }
  192.  
  193. int belong[1505][1505];
  194. vector<pii> ungay[100005];
  195. vector<gay> sieugay;
  196.  
  197. int DoPath(){
  198.     for(int i = 1; i <= n; i++)
  199.     for(int j = 1; j <= m; j++)
  200.         w[i][j] = 2e17;
  201.  
  202.     w[X1][Y1] = 0;
  203.     priority_queue<gay, vector<gay>, comp> q;
  204.     q.push({X1, Y1, 0});
  205.  
  206.     while(q.size()){
  207.         gay x = q.top();
  208.         q.pop();
  209.         for(int i = 0; i <= 3; i++){
  210.             int u = x.x + dx[i];
  211.             int v = x.y + dy[i];
  212.             if(u < 1 || u > n) continue;
  213.             if(v < 1 || v > m) continue;
  214.             if(w[u][v] > x.w + a[x.x][x.y]){
  215.                 w[u][v] = x.w + a[x.x][x.y];
  216.                 q.push({u, v, w[u][v]});
  217.             }
  218.         }
  219.         for(pii X : ungay[belong[x.x][x.y]]){
  220.             if(w[X.f][X.s] > x.w + W){
  221.                 w[X.f][X.s] = x.w + W;
  222.                 q.push({X.f, X.s, w[X.f][X.s]});
  223.             }
  224.         }
  225.     }
  226.  
  227.     return w[x2][y2];
  228. }
  229.  
  230. int cmp(gay a, gay b){
  231.     return a.w < b.w;
  232. }
  233.  
  234. void sub345(){
  235.     sort(b + 1, b + q + 1);
  236.  
  237.     for(int i = 1; i <= n; i++)
  238.     for(int j = 1; j <= n; j++)
  239.     sieugay.PB({i, j, a[i][j]});
  240.  
  241.     sort(sieugay.begin(), sieugay.end(), cmp);
  242.  
  243.     int j = -1;
  244.     for(int i = 1; i <= q; i++){
  245.         while(j + 1 < sieugay.size() && sieugay[j + 1].w >= b[i].f && sieugay[j + 1].w <= b[i].s){
  246.             j++;
  247.             ungay[i].PB({sieugay[j].x, sieugay[j].y});;
  248.             belong[sieugay[j].x][sieugay[j].y] = i;
  249.         }
  250.     }
  251.  
  252.     cout << DoPath();
  253. }
  254.  
  255. signed main(){
  256.     ios_base::sync_with_stdio(0);
  257.     cin.tie(0); cout.tie(0);
  258.  
  259.     if(fopen(TASK".INP", "r")){
  260.         freopen(TASK".INP", "r", stdin);
  261.         freopen(TASK".OUT", "w", stdout);
  262.     }
  263.  
  264.     cin >> n >> m >> q >> W;
  265.     for(int i = 1; i <= n; i++)
  266.     for(int j = 1; j <= m; j++)
  267.         cin >> a[i][j];
  268.  
  269.     for(int i = 1; i <= q; i++)
  270.         cin >> b[i].f >> b[i].s;
  271.  
  272.     cin >> X1 >> Y1 >> x2 >> y2;
  273.  
  274.     if(q == 0) sub12();
  275.     else sub345();
  276. }
  277.  
Success #stdin #stdout 0.01s 9896KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/HVrfe6
language:
C++ (gcc 8.3)
created:
5 hours 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!