結果
問題 | No.1190 Points |
ユーザー | kotatsugame |
提出日時 | 2020-08-22 16:40:52 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 264 ms / 2,000 ms |
コード長 | 1,314 bytes |
コンパイル時間 | 934 ms |
コンパイル使用メモリ | 79,200 KB |
実行使用メモリ | 11,456 KB |
最終ジャッジ日時 | 2023-08-05 13:28:20 |
合計ジャッジ時間 | 6,594 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge12 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3 ms
6,452 KB |
testcase_01 | AC | 3 ms
6,412 KB |
testcase_02 | AC | 3 ms
6,528 KB |
testcase_03 | AC | 130 ms
10,196 KB |
testcase_04 | AC | 90 ms
9,604 KB |
testcase_05 | AC | 140 ms
9,304 KB |
testcase_06 | AC | 97 ms
10,864 KB |
testcase_07 | AC | 203 ms
11,216 KB |
testcase_08 | AC | 261 ms
11,456 KB |
testcase_09 | AC | 247 ms
11,032 KB |
testcase_10 | AC | 264 ms
11,408 KB |
testcase_11 | AC | 173 ms
9,688 KB |
testcase_12 | AC | 244 ms
11,272 KB |
testcase_13 | AC | 150 ms
9,128 KB |
testcase_14 | AC | 23 ms
8,640 KB |
testcase_15 | AC | 252 ms
11,320 KB |
testcase_16 | AC | 18 ms
7,284 KB |
testcase_17 | AC | 232 ms
10,880 KB |
testcase_18 | AC | 92 ms
8,400 KB |
testcase_19 | AC | 16 ms
8,812 KB |
testcase_20 | AC | 128 ms
8,788 KB |
testcase_21 | AC | 37 ms
8,488 KB |
testcase_22 | AC | 41 ms
9,744 KB |
testcase_23 | AC | 260 ms
11,320 KB |
testcase_24 | AC | 260 ms
11,232 KB |
testcase_25 | AC | 116 ms
10,928 KB |
testcase_26 | AC | 79 ms
10,788 KB |
testcase_27 | AC | 118 ms
10,908 KB |
コンパイルメッセージ
main.cpp:9:1: 警告: ISO C++ では型の無い ‘main’ の宣言を禁止しています [-Wreturn-type] 9 | main() | ^~~~
ソースコード
#include<iostream> #include<vector> #include<queue> using namespace std; int N,M,P; int s,t; vector<int>G[1<<17]; int ds[2][1<<17],dt[2][1<<17]; main() { cin>>N>>M>>P>>s>>t; s--,t--; for(int i=0;i<M;i++) { int u,v;cin>>u>>v; u--,v--; G[u].push_back(v); G[v].push_back(u); } for(int i=0;i<N;i++) { for(int j=0;j<2;j++) { ds[j][i]=P+1; dt[j][i]=P+1; } } { ds[0][s]=0; priority_queue<pair<int,int> >P; P.push(make_pair(0,s)); while(!P.empty()) { int c=-P.top().first,u=P.top().second; P.pop(); int f=c%2; for(int v:G[u]) { int nc=c+1; int nf=nc%2; if(ds[nf][v]>nc) { ds[nf][v]=nc; P.push(make_pair(-nc,v)); } } } dt[0][t]=0; P.push(make_pair(0,t)); while(!P.empty()) { int c=-P.top().first,u=P.top().second; P.pop(); int f=c%2; for(int v:G[u]) { int nc=c+1; int nf=nc%2; if(dt[nf][v]>nc) { dt[nf][v]=nc; P.push(make_pair(-nc,v)); } } } } vector<int>ans; for(int i=0;i<N;i++) { bool ok=false; for(int js=0;js<2;js++)for(int jt=0;jt<2;jt++) { int now=ds[js][i]+dt[jt][i]; if(now<=P&&(P-now)%2==0)ok=true; } if(ok)ans.push_back(i+1); } if(ans.empty()) { cout<<-1<<endl; return 0; } cout<<ans.size()<<endl; for(int a:ans)cout<<a<<endl; }