結果
問題 | No.92 逃走経路 |
ユーザー | sune232002 |
提出日時 | 2014-12-07 19:29:47 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 5 ms / 5,000 ms |
コード長 | 2,780 bytes |
コンパイル時間 | 1,408 ms |
コンパイル使用メモリ | 151,424 KB |
実行使用メモリ | 4,380 KB |
最終ジャッジ日時 | 2023-09-02 09:21:18 |
合計ジャッジ時間 | 2,433 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 5 ms
4,376 KB |
testcase_01 | AC | 2 ms
4,376 KB |
testcase_02 | AC | 2 ms
4,380 KB |
testcase_03 | AC | 2 ms
4,376 KB |
testcase_04 | AC | 2 ms
4,376 KB |
testcase_05 | AC | 5 ms
4,376 KB |
testcase_06 | AC | 5 ms
4,380 KB |
testcase_07 | AC | 5 ms
4,376 KB |
testcase_08 | AC | 2 ms
4,380 KB |
testcase_09 | AC | 2 ms
4,376 KB |
testcase_10 | AC | 5 ms
4,380 KB |
testcase_11 | AC | 4 ms
4,376 KB |
testcase_12 | AC | 5 ms
4,376 KB |
testcase_13 | AC | 2 ms
4,376 KB |
testcase_14 | AC | 2 ms
4,380 KB |
testcase_15 | AC | 4 ms
4,380 KB |
testcase_16 | AC | 4 ms
4,380 KB |
testcase_17 | AC | 4 ms
4,380 KB |
testcase_18 | AC | 5 ms
4,380 KB |
testcase_19 | AC | 4 ms
4,376 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<(int)(n);++i) #define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i) #define ALL(c) (c).begin(), (c).end() #define valid(y,x,h,w) (0<=y&&y<h&&0<=x&&x<w) #define tpl(...) make_tuple(__VA_ARGS__) const int INF = 0x3f3f3f3f; const double EPS = 1e-8; const double PI = acos(-1); typedef long long ll; typedef pair<int,int> pii; 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 (b<a) { a=b; return 1; } return 0; } template<class T>ostream&operator<<(ostream &o,const vector<T>&t){o<<'[';FOR(i,t){if(i!=t.begin())o<<',';o<<*i;}return o<<']';} template<class S,class T>ostream&operator<<(ostream &o,const pair<S,T>&t){return o<<'('<<t.first<<','<<t.second<<')';} template<int N,class Tp>void output(ostream&,const Tp&){} template<int N,class Tp,class,class ...Ts>void output(ostream &o,const Tp&t){if(N)o<<',';o<<get<N>(t);output<N+1,Tp,Ts...>(o,t);} template<class ...Ts>ostream&operator<<(ostream&o,const tuple<Ts...>&t){o<<'(';output<0,tuple<Ts...>,Ts...>(o,t);return o<<')';} template<class T>void output(T t,char z=10){if(t<0)t=-t,putchar(45);int c[20]; int k=0;while(t)c[k++]=t%10,t/=10;for(k||(c[k++]=0);k;)putchar(c[--k]^48);putchar(z);} template<class T>void outputs(T t){output(t);} template<class S,class ...T>void outputs(S a,T...t){output(a,32);outputs(t...);} template<class T>void output(T *a,int n){REP(i,n)cout<<a[i]<<(i!=n-1?',':'\n');} template<class T>void output(T *a,int n,int m){REP(i,n)output(a[i],m);} template<class T>bool input(T &t){int n=1,c;for(t=0;!isdigit(c=getchar())&&~c&&c-45;); if(!~c)return 0;for(c-45&&(n=0,t=c^48);isdigit(c=getchar());)t=10*t+c-48;t=n?-t:t;return 1;} template<class S,class ...T>bool input(S&a,T&...t){input(a);return input(t...);} template<class T>bool inputs(T *a, int n) { REP(i,n) if(!input(a[i])) return 0; return 1;} int dp[1001][100]; vector<pii> g[100]; int main() { int n,m,k; while(input(n,m,k)){ REP(i,n) g[i].clear(); REP(i,m) { int a,b,c; input(a,b,c); a--;b--; g[a].push_back(pii(b,c)); g[b].push_back(pii(a,c)); } memset(dp,0,sizeof(dp)); REP(i,100) dp[0][i] = 1; vector<int> d(k); REP(i,k) input(d[i]); REP(i,k) { REP(j,n) { if (!dp[i][j]) continue; FOR(it, g[j]) { if (it->second == d[i]) { dp[i+1][it->first] |= 1; } } } } vector<int> ans; REP(i,n) if (dp[k][i]) ans.push_back(i); cout << ans.size() << endl; REP(i,ans.size()) { printf("%d%c", ans[i]+1, i!=(int)ans.size()-1?' ':'\n'); } } }