結果

問題 No.1190 Points
コンテスト
ユーザー Rumain831
提出日時 2026-11-06 04:24:09
言語 C++23(gcc16)
(gcc 16.2.0 + boost 1.92.0 + ACL)
コンパイル:
g++-16 -O2 -fplugin=/usr/lib/yukicoder/noavx512-gcc16.so -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 96 ms / 2,000 ms
+ 465µs
コード長 1,382 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,630 ms
コンパイル使用メモリ 216,148 KB
実行使用メモリ 20,252 KB
最終ジャッジ日時 2026-11-06 04:24:18
合計ジャッジ時間 7,479 ms
ジャッジサーバーID
（参考情報） 		judge7_0 / judge4_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main(void){
  int n, m, p; cin >> n >> m >> p;
  int s, g; cin >> s >> g; s--, g--;
  vector<vector<int>> to(n);
  for(int i=0; i<m; i++){
    int u, v; cin >> u >> v; u--, v--;
    to[u].push_back(v); swap(u, v);
    to[u].push_back(v);
  }
  auto BFS=[&](int st){
    int inf=1e9+10;
    vector dist(n, vector<int>(2, inf));
    dist[st][0]=0;
    queue<P> bfs;
    bfs.emplace(0, st);
    while(bfs.size()){
      auto [d, id]=bfs.front(); bfs.pop();
      if(dist[id][d%2]!=d) continue;
      for(auto v:to[id]){
        int nd=d+1;
        if(dist[v][nd%2]>nd){
          dist[v][nd%2]=nd;
          bfs.emplace(nd, v);
        }
      }
    }
    return dist;
  };
  auto d1=BFS(s);
  auto d2=BFS(g);
  vector<int> ans;
  for(int i=0; i<n; i++){
    bool ok=false;
    int mi=1e9;
    for(int p1=0; p1<2; p1++)for(int p2=0; p2<2; p2++){
      int d=d1[i][p1]+d2[i][p2];
      mi=min(mi, d);
      int pa=d%2;
      if(pa!=(p%2)) continue;
      if(d>p) continue;
      ok=true;
    }
    //cout << "? " << i << ' ' << mi << endl;
    if(ok) ans.push_back(i+1);
  }
  sort(begin(ans), end(ans));
  if(ans.empty()) cout << -1 << endl;
  else{
    cout << ans.size() << endl;
    for(auto p:ans) cout << p << '\n';
  }
  return 0; 
}
0