#include <bits/stdc++.h>
#define ar array
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;
const int N = 30005;
const ll inf = 1e18;
int hv[N][N];
set <int> g[N];
vector <ar <int, 2>> e[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, m;
cin >> n >> m;
int strt = -1, end = -1;
for (int i = 0; i < m; i++) {
int b, p;
cin >> b >> p;
if (i == 0)
strt = b;
else if (i == 1)
end = b;
hv[b][p] = 1;
g[b].insert(p);
}
for (int x = 0; x < n; x++) {
for (int p : g[x]) {
int y = x, cnt = 0;
while (y + p < n) {
y += p, cnt++;
e[x].push_back({y, cnt});
if (hv[y][p])
break;
}
y = x, cnt = 0;
while (y - p >= 0) {
y -= p, cnt++;
e[x].push_back({y, cnt});
if (hv[y][p])
break;
}
}
}
vector <ll> vis(n, inf);
vis[strt] = 0;
priority_queue <ar <ll, 2>> q;
q.push({0, strt});
while (!q.empty()) {
auto now = q.top(); q.pop();
int x = now[1];
if (now[0] != vis[x])
continue;
for (auto &nw : e[x]) {
if (vis[nw[0]] > vis[x] + nw[1]) {
vis[nw[0]] = vis[x] + nw[1];
q.push({vis[nw[0]], nw[0]});
}
}
}
if (vis[end] == inf)
cout << -1;
else
cout << vis[end];
}
컴파일 시 표준 에러 (stderr) 메시지
/tmp/ccCtMphz.o: in function `main':
skyscraper.cpp:(.text.startup+0x13): 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/11/libstdc++.a(globals_io.o)
skyscraper.cpp:(.text.startup+0x41): 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/11/libstdc++.a(globals_io.o)
skyscraper.cpp:(.text.startup+0x4c): 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/11/libstdc++.a(globals_io.o)
skyscraper.cpp:(.text.startup+0x7ac): 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/11/libstdc++.a(globals_io.o)
skyscraper.cpp:(.text.startup+0x7f6): 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/11/libstdc++.a(globals_io.o)
/tmp/ccCtMphz.o: in function `_GLOBAL__sub_I_hv':
skyscraper.cpp:(.text.startup+0x851): relocation truncated to fit: R_X86_64_PC32 against `.bss'
/usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(vterminate.o): in function `__gnu_cxx::__verbose_terminate_handler()':
(.text._ZN9__gnu_cxx27__verbose_terminate_handlerEv+0x1e): relocation truncated to fit: R_X86_64_PC32 against `.bss._ZZN9__gnu_cxx27__verbose_terminate_handlerEvE11terminating'
(.text._ZN9__gnu_cxx27__verbose_terminate_handlerEv+0x2b): relocation truncated to fit: R_X86_64_PC32 against `.bss._ZZN9__gnu_cxx27__verbose_terminate_handlerEvE11terminating'
/usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(ios_init.o): in function `std::ios_base::Init::Init()':
(.text._ZNSt8ios_base4InitC2Ev+0x1c): failed to convert GOTPCREL relocation against '_ZNSt8ios_base4Init11_S_refcountE'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x60): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0x67): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0x72): additional relocation overflows omitted from the output
(.text._ZNSt8ios_base4InitC2Ev+0x1c6): failed to convert GOTPCREL relocation against '_ZSt4cout'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x260): failed to convert GOTPCREL relocation against '_ZSt3cin'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x2e2): failed to convert GOTPCREL relocation against '_ZSt4cerr'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x353): failed to convert GOTPCREL relocation against '_ZSt4clog'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x541): failed to convert GOTPCREL relocation against '_ZSt5wcout'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x5e5): failed to convert GOTPCREL relocation against '_ZSt4wcin'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x670): failed to convert GOTPCREL relocation against '_ZSt5wcerr'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x6e9): failed to convert GOTPCREL relocation against '_ZSt5wclog'; relink with --no-relax
collect2: error: ld returned 1 exit status
