結果
問題 | No.1190 Points |
ユーザー | 沙耶花 |
提出日時 | 2020-08-22 13:46:03 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 280 ms / 2,000 ms |
コード長 | 1,173 bytes |
コンパイル時間 | 2,537 ms |
コンパイル使用メモリ | 205,924 KB |
実行使用メモリ | 26,668 KB |
最終ジャッジ日時 | 2024-04-23 08:10:43 |
合計ジャッジ時間 | 7,974 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,940 KB |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | AC | 158 ms
20,260 KB |
testcase_04 | AC | 115 ms
18,712 KB |
testcase_05 | AC | 156 ms
16,820 KB |
testcase_06 | AC | 149 ms
25,168 KB |
testcase_07 | AC | 239 ms
26,472 KB |
testcase_08 | AC | 239 ms
26,612 KB |
testcase_09 | AC | 234 ms
23,936 KB |
testcase_10 | AC | 246 ms
26,668 KB |
testcase_11 | AC | 167 ms
18,464 KB |
testcase_12 | AC | 226 ms
26,072 KB |
testcase_13 | AC | 154 ms
15,432 KB |
testcase_14 | AC | 43 ms
15,292 KB |
testcase_15 | AC | 267 ms
24,840 KB |
testcase_16 | AC | 19 ms
7,504 KB |
testcase_17 | AC | 250 ms
23,716 KB |
testcase_18 | AC | 89 ms
10,104 KB |
testcase_19 | AC | 36 ms
17,104 KB |
testcase_20 | AC | 134 ms
12,828 KB |
testcase_21 | AC | 48 ms
13,400 KB |
testcase_22 | AC | 77 ms
20,768 KB |
testcase_23 | AC | 278 ms
25,452 KB |
testcase_24 | AC | 280 ms
25,488 KB |
testcase_25 | AC | 151 ms
25,480 KB |
testcase_26 | AC | 135 ms
25,352 KB |
testcase_27 | AC | 151 ms
25,480 KB |
ソースコード
#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; }