#include "bits/stdc++.h"
using namespace std;
const int MAXN = 30007;
const int MAXM = 30007;
int n,m;
vector<int> arr[MAXN];
int power[MAXM];
int dist[MAXN][MAXM];
deque<pair<int,int>> dq;
bool seenposition[MAXN];
int main() {
#ifdef LOCAL
freopen("submission/input.in", "r", stdin);
freopen("submission/output.out", "w", stdout);
#else
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#endif
cin >> n >> m;
int start,end;
memset(dist,10,sizeof(dist));
for (int i = 0; i<m; i++) {
int x; cin >> x >> power[i];
if (i == 0) start = x;
if (i == 1) end = x;
arr[x].push_back(i);
}
dq.push_back({0,start});
dist[0][start] = 0;
int jumps = -1;
while (!dq.empty()) {
int x = dq.front().first, y = dq.front().second; dq.pop_front();
if (0<=y-power[x] && dist[x][y]+1<dist[x][y-power[x]]) {
dist[x][y-power[x]] = dist[x][y]+1;
dq.push_back({x,y-power[x]});
}
if (y+power[x]<n && dist[x][y]+1<dist[x][y+power[x]]) {
dist[x][y+power[x]] = dist[x][y]+1;
dq.push_back({x,y+power[x]});
}
if (seenposition[y]) continue;
seenposition[y] = true;
if (end == y) {
jumps = dist[x][y]; break;
}
for (int i : arr[y]) {
if (i == x) continue;
dist[i][y] = dist[x][y]; dq.push_front({i,y});
}
}
cout << jumps << '\n';
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
/tmp/ccyGGi5Z.o: in function `__tcf_0':
skyscraper.cpp:(.text+0x9): relocation truncated to fit: R_X86_64_PC32 against symbol `arr' defined in .bss section in /tmp/ccyGGi5Z.o
/tmp/ccyGGi5Z.o: in function `main':
skyscraper.cpp:(.text.startup+0xf): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cin' defined in .bss._ZSt3cin section in /usr/lib/gcc/x86_64-linux-gnu/13/libstdc++.a(globals_io.o)
skyscraper.cpp:(.text.startup+0x3a): relocation truncated to fit: R_X86_64_PC32 against symbol `n' defined in .bss section in /tmp/ccyGGi5Z.o
skyscraper.cpp:(.text.startup+0x44): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cin' defined in .bss._ZSt3cin section in /usr/lib/gcc/x86_64-linux-gnu/13/libstdc++.a(globals_io.o)
skyscraper.cpp:(.text.startup+0x4f): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cout' defined in .bss._ZSt4cout section in /usr/lib/gcc/x86_64-linux-gnu/13/libstdc++.a(globals_io.o)
skyscraper.cpp:(.text.startup+0x5f): relocation truncated to fit: R_X86_64_PC32 against symbol `m' defined in .bss section in /tmp/ccyGGi5Z.o
skyscraper.cpp:(.text.startup+0x7f): relocation truncated to fit: R_X86_64_PC32 against symbol `m' defined in .bss section in /tmp/ccyGGi5Z.o
skyscraper.cpp:(.text.startup+0x9b): relocation truncated to fit: R_X86_64_PC32 against symbol `power' defined in .bss section in /tmp/ccyGGi5Z.o
skyscraper.cpp:(.text.startup+0xaf): relocation truncated to fit: R_X86_64_PC32 against symbol `arr' defined in .bss section in /tmp/ccyGGi5Z.o
skyscraper.cpp:(.text.startup+0xe8): relocation truncated to fit: R_X86_64_PC32 against symbol `m' defined in .bss section in /tmp/ccyGGi5Z.o
skyscraper.cpp:(.text.startup+0x224): additional relocation overflows omitted from the output
/usr/lib/gcc/x86_64-linux-gnu/13/libstdc++.a(ios_init.o): in function `std::ios_base::Init::Init()':
(.text._ZNSt8ios_base4InitC2Ev+0x1f): failed to convert GOTPCREL relocation against '_ZNSt8ios_base4Init11_S_refcountE'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x1ed): failed to convert GOTPCREL relocation against '_ZSt4cout'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x252): failed to convert GOTPCREL relocation against '_ZSt3cin'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x2bc): failed to convert GOTPCREL relocation against '_ZSt4cerr'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x316): failed to convert GOTPCREL relocation against '_ZSt4clog'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x50f): failed to convert GOTPCREL relocation against '_ZSt5wcout'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x57d): failed to convert GOTPCREL relocation against '_ZSt4wcin'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x5f0): failed to convert GOTPCREL relocation against '_ZSt5wcerr'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x654): failed to convert GOTPCREL relocation against '_ZSt5wclog'; relink with --no-relax
/usr/bin/ld: final link failed
collect2: error: ld returned 1 exit status
