提出 #58984892

---

ソースコード 拡げる

#include <bits/stdc++.h>
// #include "prettyprint.hpp"
#define fastio                 \
  ios::sync_with_stdio(false); \
  cin.tie(0)
#define ll long long
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x.size())

#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)

using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define ordered_set tree<array<ll, 2>, null_type, less<array<ll, 2>>, rb_tree_tag, tree_order_statistics_node_update>

template <int D, typename T>
struct Vec : public vector<Vec<D - 1, T>>
{
  static_assert(D >= 1, "Vector dimension must be greater than zero!");
  template <typename... Args>
  Vec(int n = 0, Args... args) : vector<Vec<D - 1, T>>(n, Vec<D - 1, T>(args...))
  {
  }
};
template <typename T>
struct Vec<1, T> : public vector<T>
{
  Vec(int n = 0, const T &val = T()) : vector<T>(n, val)
  {
  }
};

// Code begins here

const ll M = 1000000007LL;
const ll INF = 1e18 + 10;

template <typename T>
void maxa(T &v, const T &x)
{
  v = max(v, x);
}

template <typename T>
void mina(T &v, const T &x)
{
  v = min(v, x);
}

template <typename T>
void madd(T &v, const T &x)
{
  v = (v + x);
  v %= M;
}

const int mxn = 1e6 + 10;

ll pw(ll a, ll b)
{
  ll res = 1;
  while (b)
  {
    if (b & 1)
      res = (res * a) % M;
    a = (a * a) % M;
    b >>= 1;
  }
  return res;
}

void solve()
{
  int n,m;
  cin >> n >> m;
  Vec<2,int> adj(n);
  Vec<2,int> adj_rev(n);
  for(int i=0;i<m;i++){
    int u,v;
    cin >> u >> v;
    u--,v--;
    adj[u].push_back(v);
    adj_rev[v].push_back(u);
  }
  int re = M;

  auto Bfs = [&](int s,Vec<2,int> &adj){
    vector<int> dist(n,M);
    queue<int> q;
    q.push(s);
    dist[s]=0;
    while(!q.empty()){
      int u=q.front();
      q.pop();
      for(auto v:adj[u]){
        if(dist[v]==M){
          dist[v]=dist[u]+1;
          q.push(v);
        }
      }
    }
    return dist;
  };

  auto dis1 = Bfs(0,adj);
  auto dis2 = Bfs(0,adj_rev);
  for(int i=1;i<n;i++){
    re=min(re,dis1[i]+dis2[i]);
  }
  
  re=(re==M)?-1:re;
  cout << re << endl;
}

int main()
{
  fastio;
  // freopen("in.txt","r",stdin);
  // int t;
  // cin >> t;
  // while (t--)
  solve();
}

提出情報

ジャッジ結果