結果
問題 | No.2565 はじめてのおつかい |
ユーザー |
|
提出日時 | 2023-11-26 17:07:40 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 101 ms / 2,000 ms |
コード長 | 4,056 bytes |
コンパイル時間 | 5,930 ms |
コンパイル使用メモリ | 313,160 KB |
実行使用メモリ | 13,004 KB |
最終ジャッジ日時 | 2024-09-26 11:50:36 |
合計ジャッジ時間 | 10,416 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 50 |
ソースコード
#include<bits/stdc++.h>#include<atcoder/all>using namespace std;using namespace atcoder;// long longusing ll = long long;// unsigned long longusing ull = unsigned long long;// stringusing str = string;// long doubleusing ld = long double;// pairusing pll = pair < ll, ll >;// tupleusing tlll = tuple < ll, ll, ll >;// vectortemplate < class T > using v = vector < T >;using vl = v < ll >;using vbl = v < bool >;// priority_queuetemplate < class T > using pq = priority_queue < T >;template < class T > using pqg = priority_queue < T, v < T >, greater < T > >;// unordered_settemplate < class T > using uset = unordered_set < T > ;// unordered_maptemplate < class T, class U > using umap = unordered_map < T, U > ;// rep#define rep(i, a, b) for(ll i = a; i <= b; i ++)#define Rep(i, a) for(ll i = 0; i < a; i ++)#define rrep(i, a, b) for(ll i = a; i >= b; i --)#define repp(i, a, b, c) for(ll i = a; i <= b; i += c)// binary search#define lobo(x, k) lower_bound(x.begin(), x.end(), k) - x.begin()#define Lobo(x, a, b, k) lower_bound(x + a, x + b + 1, k) - x#define upbo(x, k) upper_bound(x.begin(), x.end(), k) - x.begin()#define Upbo(x, a, b, k) upper_bound(x + a, x + b + 1, k) - x;// snippet#define eruni(x) x.erase(unique(x.begin(), x.end()), x.end())#define eb emplace_back#define mp make_pair#define mt make_tuple#define all(x) x.begin(), x.end()#define rll(x) x.rbegin(), x.rend()#define sz(x) (ll)x.size()#define f first#define s second#define in insert#define pf push_front#define p_f pop_front#define pb push_back#define p_b pop_back#define p_p prev_permutation#define n_p next_permutation#define led leader#define print(a) printf("%.20Lf", a)#define func function// functiontemplate < class T > bool chmax(T &a, const T &b) {if (a < b) {a = b; return 1;} return 0;}template < class T > bool chmin(T &a, const T &b) {if (b < a) {a = b; return 1;} return 0;}// outvoid Yes(bool f = true) {cout << (f ? "Yes" : "No" ) << endl;}void No(bool f = true) {cout << (f ? "No" : "Yes" ) << endl;}void YES(bool f = true) {cout << (f ? "YES" : "NO" ) << endl;}void NO(bool f = true) {cout << (f ? "NO" : "YES" ) << endl;}template < class T > void out(T a) {cout << a << endl;}template < class T > void out1(T a) {cout << a << " ";}template < class T, class U > void out2(T a, U b) {cout << a << " " << b << endl;}template < class T> void allout(T &a) {for(auto x : a) cout << x << " ";cout << endl;}template < class T > void allout1(T &a) {for(auto x : a) cout << x << endl;}// modintusing modi = modint998244353;using mint = modint1000000007;// constantconst ll md = 998244353;const ll mo = 1000000007;const ld pi = acos(-1);const ll inf = (1LL << 60);const ll n1 = 100009;const ll n2 = 200009;const ll n3 = 300009;const ll n5 = 500009;// gridconst pll ar1[4] = { {0, 0}, {1, 0}, {0, 1}, {1, 1} };const pll ar2[4] = { {-1, 0}, {0, -1}, {1, 0}, {0, 1} };const pll ar3[8] = { {-1, 0}, {0, -1}, {1, 0}, {0, 1}, {-1, 1}, {1, -1}, {1, 1}, {-1, -1} };int main(){ll n, m;vl G[n2];cin >> n >> m;Rep(i, m){ll a, b;cin >> a >> b;G[a].eb(b);}auto bfs = [&](ll x, ll y){vl D(n2, -1);queue < ll > Q;Q.push(x);D[x] = 0;while(sz(Q)){ll p = Q.front();Q.pop();for(auto nex : G[p]){if(D[nex] == -1){D[nex] = D[p] + 1;Q.push(nex);}}}return D[y];};ll d1 = -1, d2 = -1, ans = inf;bool f1 = true, f2 = true;if(bfs(1, n - 1) == -1 || bfs(n - 1, n) == -1 || bfs(n, 1) == -1) f1 = false;if(bfs(1, n) == -1 || bfs(n, n - 1) == -1 || bfs(n - 1, 1) == -1) f2 = false;if(f1){d1 ++;d1 += bfs(1, n - 1);d1 += bfs(n - 1, n);d1 += bfs(n, 1);chmin(ans, d1);}if(f2){d2 ++;d2 += bfs(1, n);d2 += bfs(n, n - 1);d2 += bfs(n - 1, 1);chmin(ans, d2);}if(ans == inf) ans = -1;out(ans);}