結果
問題 | No.1190 Points |
ユーザー | ate |
提出日時 | 2020-08-22 16:05:13 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,984 bytes |
コンパイル時間 | 2,265 ms |
コンパイル使用メモリ | 218,904 KB |
実行使用メモリ | 14,952 KB |
最終ジャッジ日時 | 2024-10-15 10:12:41 |
合計ジャッジ時間 | 6,864 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 2 ms
5,248 KB |
testcase_03 | AC | 140 ms
11,288 KB |
testcase_04 | AC | 94 ms
9,524 KB |
testcase_05 | AC | 160 ms
11,056 KB |
testcase_06 | AC | 130 ms
12,456 KB |
testcase_07 | AC | 231 ms
14,672 KB |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | AC | 24 ms
7,840 KB |
testcase_15 | WA | - |
testcase_16 | AC | 16 ms
5,248 KB |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | AC | 19 ms
8,572 KB |
testcase_20 | WA | - |
testcase_21 | AC | 35 ms
7,364 KB |
testcase_22 | AC | 42 ms
10,108 KB |
testcase_23 | WA | - |
testcase_24 | WA | - |
testcase_25 | AC | 113 ms
13,668 KB |
testcase_26 | AC | 86 ms
13,152 KB |
testcase_27 | AC | 110 ms
13,656 KB |
ソースコード
#if loc||local #define _GLIBCXX_DEBUG #endif #include<bits/stdc++.h> using namespace std; #define rep(i,n) for(ll i=0;i<(n);++i) using ll = int_fast64_t; using pll = pair<ll,ll>; constexpr ll INF = 1LL<<60; constexpr ll MOD = 1e9+7; template<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(a>b){a=b;return 1;}return 0;} #if loc||local template<class T>void dump(T&& t){cerr<<t<<endl;} template<class T,class... Ts> void dump(T&& h, Ts&&... t){cerr<<h<<", ";dump(forward<Ts>(t)...);} #else void dump(){} template<class T,class... Ts> void dump(T&& h, Ts&&... t){} #endif template<class T> istream &operator>>(istream&is,vector<T>&v){for(auto &elemnt:v)is>>elemnt;return is;} template<class T,class U> istream &operator>>(istream&is,pair<T,U>&p){is>>p.first>>p.second;return is;} template<class T> ostream &operator<<(ostream& os,vector<T>const& v){for(auto const& vi:v)os<<vi<<" ";return os;} template<class T,class U> ostream &operator<<(ostream& os,pair<T,U>const& p){os<<p.first<<","<<p.second;return os;} template<class T>vector<T> vec(size_t a){return vector<T>(a);} template<class T, class... Ts>auto vec(size_t a, Ts... ts){return vector<decltype(vec<T>(ts...))>(a, vec<T>(ts...));} using vertex = struct vertex{ll to,cost;vertex(ll to,ll cost):to(to),cost(cost){}}; using edge = struct edge{ll from,to,cost;edge(ll from,ll to,ll cost):from(from),to(to),cost(cost){}}; using weighted_adjlist = vector<vector<vertex>>; using weighted_edge = vector<edge>; auto Dijkstra(weighted_adjlist& adj,ll S){ ll N=(ll)adj.size(); vector<ll> dist(N,(1LL<<60)); vector<ll> prev_v(N,-1LL); using pll = pair<ll,ll>; priority_queue<pll,vector<pll>,greater<>> que; dist[S]=0LL; que.emplace(dist[S],S); while(!que.empty()){ ll cost,from; tie(cost,from) = que.top(); que.pop(); if(dist[from]<cost)continue; for(const auto& v:adj[from]){ if( chmin(dist[v.to],dist[from]+v.cost) ){ prev_v[v.to]=from; que.emplace(dist[v.to],v.to); } } } return dist; //return prev_v; //return make_pair(dist,prev_v); } signed main(){ ll n,m,p; cin>>n>>m>>p; ll s,g; cin>>s>>g; weighted_adjlist adj(n+1); rep(i,m){ int u,v; cin>>u>>v; adj[u].emplace_back(v,1); adj[v].emplace_back(u,1); } auto dist_s = Dijkstra(adj,s); auto dist_g = Dijkstra(adj,g); // 1 indexed set<int> ans; for(int v=1;v<=n;++v){ ll min_dist = dist_s[v]+dist_g[v]; if(min_dist>p)continue; if((p-min_dist)%2==0){ ans.emplace(v); continue; } for(auto&nv:adj[v]){ if(dist_s[v]==dist_s[nv.to] and dist_s[v]+dist_s[nv.to]+1<=p ){ ans.emplace(v); break; } if(dist_g[v]==dist_g[nv.to] and dist_g[v]+dist_g[nv.to]+1<=p){ ans.emplace(v); break; } } } if(size(ans)==0){ cout<< -1 <<endl; return 0; } cout<<size(ans)<<endl; for(auto& v:ans)cout<<v<<endl; }