結果

問題 No.92 逃走経路
ユーザー ty70ty70
提出日時 2015-06-02 13:01:58
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 355 ms / 5,000 ms
コード長 2,660 bytes
コンパイル時間 883 ms
コンパイル使用メモリ 103,572 KB
実行使用メモリ 19,776 KB
最終ジャッジ日時 2023-09-20 18:42:13
合計ジャッジ時間 2,979 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 16 ms
5,288 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,380 KB
testcase_05 AC 61 ms
19,756 KB
testcase_06 AC 2 ms
4,376 KB
testcase_07 AC 3 ms
4,380 KB
testcase_08 AC 2 ms
4,376 KB
testcase_09 AC 22 ms
4,560 KB
testcase_10 AC 201 ms
19,776 KB
testcase_11 AC 216 ms
19,536 KB
testcase_12 AC 355 ms
19,556 KB
testcase_13 AC 8 ms
4,816 KB
testcase_14 AC 16 ms
5,084 KB
testcase_15 AC 23 ms
5,660 KB
testcase_16 AC 15 ms
5,008 KB
testcase_17 AC 15 ms
4,940 KB
testcase_18 AC 8 ms
4,408 KB
testcase_19 AC 5 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <algorithm>	// require sort next_permutation count __gcd reverse etc.
#include <cstdlib>	// require abs exit atof atoi 
#include <cstdio>		// require scanf printf
#include <functional>
#include <numeric>	// require accumulate
#include <cmath>		// require fabs
#include <climits>
#include <limits>
#include <cfloat>
#include <iomanip>	// require setw
#include <sstream>	// require stringstream 
#include <cstring>	// require memset
#include <cctype>		// require tolower, toupper
#include <fstream>	// require freopen
#include <ctime>		// 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<int, int> P;

/*
	No.92 逃走経路

	街 a, b 間の通行料金を c とすると
	multimap<int,pair<int,int> > cost で 通行料金 c とペアの街 (a,b), (b,a ) を保持。
	
	vector<P> cand[k] で 犯人が支払った通行料金と一致するペアの街 を保持。
	
	後は cand[i].second == cand[i+1].first となる経路を深さ優先探索で探索。
	結果を set<int> res に保持。

	計算量：O(M^K) やばい？ 1000^1000

	枝刈りしたら最悪ケースで大丈夫になった。

*/
const int MAX_N = 102;
const int MAX_K = 1005;
vector<P> cand[MAX_K];
bool visited[MAX_K][MAX_N];

set<int> 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<int,P> 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<int> d(K, 0 );
	rep (i, K ) cin >> d[i];

	rep (i, K ) cand[i].clear();
	multimap<int,P>::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<int>::iterator jt = res.begin();
	for (; jt != res.end(); jt++ ){
		cout << (*jt) << ' ';
	} // end for
	if (!res.empty() )
		cout << endl;

	return 0;
}
0