結果

問題 No.1190 Points
コンテスト
ユーザー Haar
提出日時 2020-08-25 00:31:30
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 192 ms / 2,000 ms
コード長 3,819 bytes
コンパイル時間 2,683 ms
コンパイル使用メモリ 208,876 KB
最終ジャッジ日時 2025-01-13 13:39:41
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

#ifdef DEBUG
#include <Mylib/Debug/debug.cpp>
#else
#define dump(...) ((void)0)
#endif

template <typename T, typename U>
bool chmin(T &a, const U &b){
  return (a > b ? a = b, true : false);
}

template <typename T, typename U>
bool chmax(T &a, const U &b){
  return (a < b ? a = b, true : false);
}

template <typename T, size_t N, typename U>
void fill_array(T (&a)[N], const U &v){
  std::fill((U*)a, (U*)(a + N), v);
}

template <typename T>
auto make_vector(int n, int m, const T &value){
  return std::vector<std::vector<T>>(n, std::vector<T>(m, value));
}

template <typename T>
std::ostream& operator<<(std::ostream &s, const std::vector<T> &a){
  for(auto it = a.begin(); it != a.end(); ++it){
    if(it != a.begin()) s << " ";
    s << *it;
  }
  return s;
}

template <typename T>
std::istream& operator>>(std::istream &s, std::vector<T> &a){
  for(auto &x : a) s >> x;
  return s;
}


/**
 * @title Graph template
 * @docs graph_template.md
 */
template <typename Cost = int> class Edge{
public:
  int from,to;
  Cost cost;
  Edge() {}
  Edge(int to, Cost cost): to(to), cost(cost){}
  Edge(int from, int to, Cost cost): from(from), to(to), cost(cost){}
};

template <typename T> using Graph = std::vector<std::vector<Edge<T>>>;
template <typename T> using Tree = std::vector<std::vector<Edge<T>>>;

template <typename T, typename C> void add_edge(C &g, int from, int to, T w = 1){
  g[from].emplace_back(from, to, w);
}

template <typename T, typename C> void add_undirected(C &g, int a, int b, T w = 1){
  add_edge<T, C>(g, a, b, w);
  add_edge<T, C>(g, b, a, w);
}


/**
 * @title BFS shortest path
 * @docs bfs_shortest_path.md
 */
template <typename T>
std::vector<std::optional<int64_t>> bfs_shortest_path(const Graph<T> &g, const std::vector<int> &src){
  const int n = g.size();
  std::vector<std::optional<int64_t>> ret(n, std::nullopt);
  std::vector<bool> visited(n);
  std::queue<int> q;

  for(auto s : src){
    ret[s] = 0;
    q.push(s);
  }

  while(not q.empty()){
    const int cur = q.front(); q.pop();

    if(visited[cur]) continue;
    visited[cur] = true;

    for(auto &e : g[cur]){
      if(not ret[e.to] or *ret[e.to] > *ret[e.from] + 1){
        ret[e.to] = *ret[e.from] + 1;
        q.push(e.to);
      }
    }
  }

  return ret;
}


namespace solver{
  constexpr int INF = INT_MAX;
  
  void init(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(12);
    std::cerr << std::fixed << std::setprecision(12);
    std::cin.exceptions(std::ios_base::failbit);
  }
  
  void solve(){
    int N, M, P; std::cin >> N >> M >> P;
    int S, G; std::cin >> S >> G;
    --S, --G;

    Graph<int64_t> g(2 * N);

    for(int i = 0; i < M; ++i){
      int u, v; std::cin >> u >> v;
      --u, --v;
      add_undirected(g, u, v + N, 1);
      add_undirected(g, u + N, v, 1);
    }

    auto s_dist = bfs_shortest_path(g, {S});
    auto g_dist = bfs_shortest_path(g, {G});

    std::vector<int> ans;
    for(int i = 0; i < N; ++i){
      bool ok = false;

      if(P % 2 == 0){
        if(s_dist[i].value_or(INF) + g_dist[i].value_or(INF) <= P or
           s_dist[i + N].value_or(INF) + g_dist[i + N].value_or(INF) <= P){
          ok = true;
        }
      }else{
        if(s_dist[i].value_or(INF) + g_dist[i + N].value_or(INF) <= P or
           s_dist[i + N].value_or(INF) + g_dist[i].value_or(INF) <= P){
          ok = true;
        }
      }

      if(ok) ans.push_back(i + 1);
    }

    if(ans.empty()) std::cout << -1 << "\n";
    else{
      std::cout << ans.size() << "\n";
      for(auto x : ans) std::cout << x << "\n";
    }
  }
}

int main(){
  solver::init();
  while(true){
    try{
      solver::solve();
    }catch(const std::istream::failure &e){
      break;
    }
  }
  return 0;
}
0