結果
問題 |
No.3 ビットすごろく
|
ユーザー |
![]() |
提出日時 | 2018-03-24 18:19:20 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 32 ms / 5,000 ms |
コード長 | 2,321 bytes |
コンパイル時間 | 1,216 ms |
コンパイル使用メモリ | 124,860 KB |
実行使用メモリ | 7,364 KB |
最終ジャッジ日時 | 2024-07-01 08:58:09 |
合計ジャッジ時間 | 2,718 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
# include <iostream> # include <algorithm> #include <array> # include <cassert> #include <cctype> #include <climits> #include <numeric> # include <vector> # include <string> # include <set> # include <map> # include <cmath> # include <iomanip> # include <functional> # include <tuple> # include <utility> # include <stack> # include <queue> # include <list> # include <bitset> # include <complex> # include <chrono> # include <random> # include <limits.h> # include <unordered_map> # include <unordered_set> # include <deque> # include <cstdio> # include <cstring> using namespace std; using LL = long long; using ULL = unsigned long long; constexpr long long MOD = 1000000000 + 7; constexpr long long INF = std::numeric_limits<long long>::max(); const double PI = acos(-1); #define fir first #define sec second typedef pair<LL, LL> Pll; typedef pair<LL, pair<LL, LL>> Ppll; typedef pair<LL, pair<LL, bitset<100001>>> Pbll; typedef pair<LL, pair<LL, vector<LL>>> Pvll; typedef pair<LL, LL> Vec2; struct Tll { LL first, second, third; }; typedef pair<LL, Tll> Ptll; #define rep(i,rept) for(LL i=0;i<rept;i++) #define Mfor(i,mf) for(LL i=mf-1;i>=0;i--) LL h, w, n, m, k, s, t, q, sum, last, ans, cnt,a[100000],d[100000]; struct Edge { LL to, cost,mon; }; string str; bool f = 0; void YN(bool f) { if (f) cout << "YES" << endl; else cout << "NO" << endl; } void yn(bool f) { if (f) cout << "Yes" << endl; else cout << "No" << endl; } vector<Edge>vec[100000]; void add_edge(LL x, LL y, LL z) { vec[x].push_back(Edge{ y,z }); } void DIUX(LL s) { for (int i = 0; i < 100000; i++) d[i] = INF; d[s] = 1; priority_queue<Pll, vector<Pll>, greater<Pll>> pq; pq.push(make_pair(d[s], s)); // (cost,頂点番号) while (!pq.empty()) { Pll pp; pp = pq.top(); LL cos = pp.first, vv = pp.second; pq.pop(); if (d[vv] < pp.first)continue; for (int i = 0; i < vec[vv].size(); i++) { if (vec[vv][i].cost + d[vv] < d[vec[vv][i].to]) { d[vec[vv][i].to] = vec[vv][i].cost + d[vv]; pq.push(make_pair(d[vec[vv][i].to], vec[vv][i].to)); } } } } int main() { cin >> n; for(int i=1;i<=n;i++) { bitset<10000>bi = i; if(i + bi.count()<=n) add_edge(i, i+bi.count(), 1); if(i - bi.count()>0) add_edge(i, i-bi.count(), 1); } DIUX(1); cout << (d[n] == INF ? -1 : d[n]) << endl; return 0; }