#include <bits/stdc++.h>
#define fr first
#define sc second
#define mk make_pair
#define pb push_back
#define OK puts("OK");
#define sz(s) (int)s.size()
#define all(s) s.begin(), s.end()
using namespace std;
const int N = 2005, inf = 1e9 + 7;
int n, m, u[N][N], pos[N], pw[N], ans = 1e9 + 7;
vector <int> vec[N];
priority_queue < pair < int, pair <int, int> > > q;
main()
{
cin >> n >> m;
for (int i = 0; i < m; i++)
{
scanf("%d%d", &pos[i], &pw[i]);
vec[pos[i]].pb(pw[i]);
}
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
u[i][j] = inf;
for (auto to : vec[ pos[0] ])
{
if (u[ pos[0] ][to] > 0)
{
q.push( mk( 0, mk(pos[0], to) ) );
u[ pos[0] ][to] = 0;
}
}
vec[ pos[0] ].clear();
while (!q.empty() )
{
int v = q.top().sc.fr, cur_pow = q.top().sc.sc, cur_len = -q.top().fr;
q.pop();
if ( cur_len > u[v][cur_pow] ) continue;
for (auto it : vec[v])
{
if (u[v][it] > u[v][cur_pow])
{
u[v][it] = u[v][cur_pow];
q.push( mk(-u[v][it], mk(v, it) ) );
}
}
vec[v].clear();
if ( v - cur_pow >= 0 && u[v - cur_pow][cur_pow] > u[v][cur_pow] + 1 )
{
u[v - cur_pow][cur_pow] = u[v][cur_pow] + 1;
q.push( mk(-u[v - cur_pow][cur_pow], mk(v - cur_pow, cur_pow) ) );
}
if ( v + cur_pow < n && u[v + cur_pow][cur_pow] > u[v][cur_pow] + 1 )
{
u[v + cur_pow][cur_pow] = u[v][cur_pow] + 1;
q.push( mk( -u[v + cur_pow][cur_pow], mk(v + cur_pow, cur_pow) ) );
}
}
for (int i = 0; i < m; i++)
ans = min(ans, u[ pos[1] ][i] );
if (ans == inf)
ans = -1;
cout << ans << endl;
}
/**
5 3
0 2
1 1
4 1
**/
Compilation message
skyscraper.cpp:21:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main()
^
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:26:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &pos[i], &pw[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
16120 KB |
Output is correct |
2 |
Correct |
14 ms |
16120 KB |
Output is correct |
3 |
Incorrect |
14 ms |
16176 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
16196 KB |
Output is correct |
2 |
Correct |
14 ms |
16228 KB |
Output is correct |
3 |
Incorrect |
14 ms |
16228 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
16284 KB |
Output is correct |
2 |
Correct |
14 ms |
16288 KB |
Output is correct |
3 |
Incorrect |
13 ms |
16304 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
16304 KB |
Output is correct |
2 |
Correct |
13 ms |
16360 KB |
Output is correct |
3 |
Incorrect |
14 ms |
16360 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
16360 KB |
Output is correct |
2 |
Correct |
15 ms |
16492 KB |
Output is correct |
3 |
Incorrect |
13 ms |
16492 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |