#include<bits/stdc++.h>
using namespace std;
int nodes, nr, N, M, ver[409][409], hor[409][409], verC[409][409], horC[409][409], city[409][409], code[42][42][1030];
pair < int, int > cell[409 * 409];
vector < pair < int, int > > v[1700009];
long long dist[2000009];
void addEdge (int x, int y, int z)
{
v[x].push_back ({y, z});
v[y].push_back ({x, z});
}
priority_queue < pair < long long, int > > PQ;
long long dijkstra (int source, int destination)
{
for (int i=1; i<=nodes; i++)
dist[i] = 1LL << 60;
dist[source] = 0, PQ.push ({0, source});
while (!PQ.empty ())
{
auto curr = PQ.top ();
PQ.pop ();
if (dist[curr.second] != -curr.first) continue;
int nod = curr.second;
for (auto it : v[nod])
if (dist[it.first] > dist[nod] + it.second)
dist[it.first] = dist[nod] + it.second, PQ.push ({-dist[it.first], it.first});
}
return dist[destination];
}
int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);
scanf ("%d %d", &N, &M);
for (int i=1; i<=N; i++)
for (int j=1; j<=M; j++)
{
scanf ("%d", &city[i][j]);
if (city[i][j])
cell[nr ++] = {i, j};
}
for (int i=1; i<=N; i++)
for (int j=0; j<=M; j++)
{
scanf ("%d", &verC[i - 1][j]);
for (int k=0; k<nr; k++)
if (cell[k].first == i && cell[k].second <= j)
ver[i - 1][j] |= 1 << k;
}
for (int i=0; i<=N; i++)
for (int j=0; j<M; j++)
scanf ("%d", &horC[i][j]);
for (int i=0; i<=N; i++)
for (int j=0; j<=M; j++)
for (int k=0; k<(1 << nr); k++)
code[i][j][k] = ++nodes;
for (int i=0; i<=N; i++)
for (int j=0; j<=M; j++)
{
if (i < N)
{
for (int k=0; k<(1 << nr); k++)
addEdge (code[i][j][k], code[i + 1][j][k ^ ver[i][j]], verC[i][j]);
}
if (j < M)
{
for (int k=0; k<(1 << nr); k++)
addEdge (code[i][j][k], code[i][j + 1][k], horC[i][j]);
}
}
printf ("%lld\n", dijkstra (code[0][0][0], code[0][0][(1 << nr) - 1]));
return 0;
}
Compilation message
wall.cpp: In function 'int main()':
wall.cpp:40:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d %d", &N, &M);
~~~~~~^~~~~~~~~~~~~~~~~
wall.cpp:44:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d", &city[i][j]);
~~~~~~^~~~~~~~~~~~~~~~~~~
wall.cpp:51:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d", &verC[i - 1][j]);
~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
wall.cpp:58:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d", &horC[i][j]);
~~~~~~^~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
36 ms |
40952 KB |
Output is correct |
| 2 |
Correct |
40 ms |
41200 KB |
Output is correct |
| 3 |
Correct |
36 ms |
41200 KB |
Output is correct |
| 4 |
Correct |
40 ms |
41272 KB |
Output is correct |
| 5 |
Correct |
35 ms |
41272 KB |
Output is correct |
| 6 |
Correct |
46 ms |
44576 KB |
Output is correct |
| 7 |
Correct |
886 ms |
91812 KB |
Output is correct |
| 8 |
Correct |
62 ms |
91812 KB |
Output is correct |
| 9 |
Correct |
38 ms |
91812 KB |
Output is correct |
| 10 |
Correct |
40 ms |
91812 KB |
Output is correct |
| 11 |
Correct |
1442 ms |
112280 KB |
Output is correct |
| 12 |
Correct |
103 ms |
112280 KB |
Output is correct |
| 13 |
Correct |
579 ms |
112280 KB |
Output is correct |
| 14 |
Correct |
1919 ms |
136936 KB |
Output is correct |
| 15 |
Correct |
41 ms |
136936 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
84 ms |
136936 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
407 ms |
225300 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Runtime error |
436 ms |
225300 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Correct |
44 ms |
225300 KB |
Output is correct |
| 5 |
Runtime error |
100 ms |
225300 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
96 ms |
225300 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
97 ms |
225300 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Runtime error |
412 ms |
225300 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 9 |
Correct |
261 ms |
225300 KB |
Output is correct |
| 10 |
Correct |
53 ms |
225300 KB |
Output is correct |
| 11 |
Runtime error |
219 ms |
225300 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 |
Runtime error |
89 ms |
225300 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 13 |
Runtime error |
539 ms |
225300 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 14 |
Runtime error |
455 ms |
254016 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 15 |
Correct |
257 ms |
254016 KB |
Output is correct |
| 16 |
Correct |
47 ms |
254016 KB |
Output is correct |
| 17 |
Runtime error |
97 ms |
254016 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 18 |
Runtime error |
89 ms |
254016 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
108 ms |
254016 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
110 ms |
254016 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Runtime error |
125 ms |
254016 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Runtime error |
277 ms |
254016 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
1854 ms |
254016 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
122 ms |
254016 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
149 ms |
254016 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Runtime error |
180 ms |
254016 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
135 ms |
254016 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
147 ms |
254016 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 11 |
Execution timed out |
2074 ms |
254016 KB |
Time limit exceeded |
| 12 |
Runtime error |
243 ms |
254016 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 13 |
Runtime error |
294 ms |
254016 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 14 |
Runtime error |
619 ms |
254016 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 15 |
Runtime error |
182 ms |
254016 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 16 |
Runtime error |
173 ms |
254016 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 17 |
Runtime error |
177 ms |
254016 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 18 |
Runtime error |
175 ms |
254016 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 19 |
Runtime error |
267 ms |
254016 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 20 |
Runtime error |
524 ms |
254016 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
