結果
問題 | No.92 逃走経路 |
ユーザー | ldsyb |
提出日時 | 2017-09-18 03:23:53 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 115 ms / 5,000 ms |
コード長 | 787 bytes |
コンパイル時間 | 516 ms |
コンパイル使用メモリ | 67,848 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-04-25 15:09:08 |
合計ジャッジ時間 | 1,794 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 72 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,944 KB |
testcase_02 | AC | 1 ms
6,944 KB |
testcase_03 | AC | 2 ms
6,944 KB |
testcase_04 | AC | 2 ms
6,944 KB |
testcase_05 | AC | 5 ms
6,940 KB |
testcase_06 | AC | 6 ms
6,944 KB |
testcase_07 | AC | 6 ms
6,940 KB |
testcase_08 | AC | 2 ms
6,940 KB |
testcase_09 | AC | 9 ms
6,944 KB |
testcase_10 | AC | 60 ms
6,940 KB |
testcase_11 | AC | 65 ms
6,940 KB |
testcase_12 | AC | 115 ms
6,940 KB |
testcase_13 | AC | 4 ms
6,940 KB |
testcase_14 | AC | 11 ms
6,940 KB |
testcase_15 | AC | 28 ms
6,940 KB |
testcase_16 | AC | 34 ms
6,940 KB |
testcase_17 | AC | 65 ms
6,940 KB |
testcase_18 | AC | 43 ms
6,944 KB |
testcase_19 | AC | 28 ms
6,944 KB |
ソースコード
#include <iostream> using namespace std; int main(){ int n, m, k; cin >> n >> m >> k; int a[m], b[m], c[m], d[k]; for(int i = 0; i < m; i++){ cin >> a[i] >> b[i] >> c[i]; a[i]--; b[i]--; } for(int &i:d) cin >> i; bool dp[2][n]; for(int i = 0; i < n; i++) dp[0][i] = true; for(int i = 0; i < k; i++){ int now = i % 2, next = 1 ^ now; for(int j = 0; j < n; j++) dp[next][j] = false; for(int j = 0; j < n; j++) if(dp[now][j]){ for(int l = 0; l < m; l++){ if((a[l] == j || b[l] == j) && c[l] == d[i]){ int to = a[l] == j ? b[l] : a[l]; dp[next][to] = true; } } } } int count = 0; for(int i = 0; i < n; i++) if(dp[k % 2][i]) count++; cout << count << endl; for(int i = 0; i < n; i++) if(dp[k % 2][i]) cout << i + 1 << ' '; cout << endl; }