結果

問題 No.2565 はじめてのおつかい
コンテスト
ユーザー Yazawa Itsuchi
提出日時 2025-05-30 22:25:17
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 41 ms / 2,000 ms
コード長 1,700 bytes
コンパイル時間 2,093 ms
コンパイル使用メモリ 201,148 KB
実行使用メモリ 13,244 KB
最終ジャッジ日時 2025-05-30 22:25:24
合計ジャッジ時間 6,722 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>

using namespace std;
#define int long long
#define fi first
#define se second
#define PB push_back
#define pii pair<int, int>
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FOD(i, a, b) for (int i = (a); i >= (b); i--)
#define REP(i, n) for (int i = 0; i < (n); i++)
#define ALL(x) (x).begin(), (x).end()
#define __Suchi__ signed main()
#define TIME (1.0 * clock()/CLOCKS_PER_SEC)

const int N = 1e5+7;
const int M = 1e3+1;

int n, m, k;

int d[N][4];
int vis[N];
vector<int> g[N];

void bfs(int s, int idx){
    memset(vis, 0 , sizeof vis);
    queue<int> q;
    q.push(s);
    d[s][idx] = 0;
    while(!q.empty()){
        int u = q.front(); q.pop();

        if (vis[u]) continue;
        vis[u] = 1;

        for(auto v : g[u]) if (d[v][idx] > d[u][idx] + 1){
            d[v][idx] = d[u][idx] + 1;
            q.push(v);
        }
    }
}

void solve(){
    FOR(i,1,k){
        int x,y ; cin >> x >> y;
        g[x].PB(y);
    }
    FOR(i,1,n) d[i][1] = d[i][2] = d[i][3] = 1000000000;

    bfs(1, 1);
    bfs(n-1, 2);
    bfs(n, 3);

    // FOR(i,1,n) cout << d[i][1] << " ";
    // cout << "\n";
    // FOR(i,1,n) cout << d[i][2] << " ";
    // cout << "\n";
    // FOR(i,1,n) cout << d[i][3] << " ";
    // cout << "\n";
    // 1 -> n -> n-1 -> 1
    // 1 -> n-1 -> n -> 1

    int res = min(d[n-1][1] + d[n][2] + d[1][3], d[n][1] + d[n-1][3] + d[1][2]);
    cout << (res >= 1000000000 ? -1 : res);
}

__Suchi__{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    int t = 1;

    FOR(i, 1, t){
        cin >> n >> k;
        solve();
    }


    cerr << "Time elapsed: " << TIME << "s.\n";
    return (0 ^ 0);
}
0