結果
問題 | No.1190 Points |
ユーザー |
![]() |
提出日時 | 2020-08-22 13:46:03 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 349 ms / 2,000 ms |
コード長 | 1,173 bytes |
コンパイル時間 | 2,971 ms |
コンパイル使用メモリ | 203,256 KB |
最終ジャッジ日時 | 2025-01-13 08:00:50 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 25 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:36:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 36 | scanf("%d %d",&u,&v); | ~~~~~^~~~~~~~~~~~~~~
ソースコード
#include <bits/stdc++.h> using namespace std; #define modulo 998244353 #define mod(mod_x) ((((long long)mod_x+modulo))%modulo) #define Inf 1000000005 vector<int> get(vector<vector<int>> E,int s){ vector<int> ret(E.size(),Inf); ret[s] = 0; queue<int> Q; Q.push(s); while(Q.size()!=0){ int u = Q.front(); Q.pop(); for(int i=0;i<E[u].size();i++){ int v = E[u][i]; if(ret[v]!=Inf)continue; ret[v] = ret[u]+1; Q.push(v); } } return ret; } int main(){ int N,M,P,S,G; cin>>N>>M>>P>>S>>G; S--;G--; vector<vector<int>> E(2*N,vector<int>()); for(int i=0;i<M;i++){ int u,v; scanf("%d %d",&u,&v); u--;v--; E[2*u].push_back(2*v+1); E[2*u+1].push_back(2*v); E[2*v].push_back(2*u+1); E[2*v+1].push_back(2*u); } vector<int> d0 = get(E,S*2),d1 = get(E,G*2); vector<int> ans; for(int i=0;i<N;i++){ int m = Inf; if(P%2==0){ m = min(d0[i*2]+d1[i*2],d0[i*2+1]+d1[i*2+1]); } else{ m = min(d0[i*2]+d1[i*2+1],d0[i*2+1]+d1[i*2]); } if(m<=P){ ans.push_back(i); } } if(ans.size()==0)cout<<-1<<endl; else{ cout<<ans.size()<<endl; for(int i=0;i<ans.size();i++)cout<<ans[i]+1<<endl; } return 0; }