#include #include #include #include #include #include #include #include #include // require sort next_permutation count __gcd reverse etc. #include // require abs exit atof atoi #include // require scanf printf #include #include // require accumulate #include // require fabs #include #include #include #include // require setw #include // require stringstream #include // require memset #include // require tolower, toupper #include // require freopen #include // require srand #define rep(i,n) for(int i=0;i<(n);i++) #define ALL(A) A.begin(), A.end() using namespace std; typedef long long ll; typedef pair P; /* No.92 逃走経路 街 a, b 間の通行料金を c とすると multimap > cost で 通行料金 c とペアの街 (a,b), (b,a ) を保持。 vector

cand[k] で 犯人が支払った通行料金と一致するペアの街 を保持。 後は cand[i].second == cand[i+1].first となる経路を深さ優先探索で探索。 結果を set res に保持。 計算量:O(M^K) やばい? 1000^1000 枝刈りしたら最悪ケースで大丈夫になった。 */ const int MAX_N = 102; const int MAX_K = 1005; vector

cand[MAX_K]; bool visited[MAX_K][MAX_N]; set res; int N, M, K; void dfs (int from, int depth ){ if (depth == K ){ res.insert (from ); return; } // end if if (visited[depth][from] ) return; visited[depth][from] |= true; rep (j, cand[depth].size() ){ P next = cand[depth][j]; if (from == next.first ){ dfs (next.second, depth + 1 ); } // end if } // end rep } int main() { memset (visited, false, sizeof (visited ) ); ios_base::sync_with_stdio(0); cin >> N >> M >> K; multimap cost; cost.clear(); rep (i, M ){ int a, b, c; cin >> a >> b >> c; cost.insert (make_pair(c, P (a, b ) ) ); cost.insert (make_pair(c, P (b, a ) ) ); } // end rep vector d(K, 0 ); rep (i, K ) cin >> d[i]; rep (i, K ) cand[i].clear(); multimap::iterator it; rep (i, K ){ int n = cost.count (d[i] ); it = cost.find (d[i] ); rep (j, n ){ cand[i].push_back (it->second ); it++; } // end rep } // end rep res.clear(); rep (i, cand[0].size() ){ int to = cand[0][i].second; dfs (to, 1 ); } // end if cout << (int)res.size() << endl; set::iterator jt = res.begin(); for (; jt != res.end(); jt++ ){ cout << (*jt) << ' '; } // end for if (!res.empty() ) cout << endl; return 0; }