結果

問題 No.92 逃走経路
コンテスト
ユーザー wunderkammer2
提出日時 2020-01-02 00:23:15
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 1,830 bytes
コンパイル時間 1,372 ms
コンパイル使用メモリ 116,760 KB
実行使用メモリ 814,864 KB
最終ジャッジ日時 2024-11-22 17:30:11
合計ジャッジ時間 35,820 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 6 MLE * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<algorithm>
#include<cmath>
#include<cstdio>
#include<functional>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<string>
#include<utility>
#include<vector>

using namespace std;
typedef long long ll;
const ll mod = 1000000007;
#define rep(i,n) for(int i=0;i<n;i++)
#define repl(i,s,e) for(int i=s;i<e;i++)
#define reple(i,s,e) for(int i=s;i<=e;i++)
#define revrep(i,n) for(int i=n-1;i>=0;i--)
#define all(x) (x).begin(),(x).end()


class Pop
{
public:
	int end;
	int p;
	int count;

	Pop(int end, int p, int count)
	{
		this->end = end;
		this->p = p;
		this->count = count;
	}
};

int main()
{	
	int N, M, K;
	cin >> N >> M >> K;

	

	
	//nodes[i][j] := 町iから料金jの道路を通って行くことのできる町
	vector<map<int, vector<int>>> nodes(N);


	rep(i, M)
	{
		int a, b, c;
		cin >> a >> b >> c;

		--a;
		--b;

		if (nodes[a].count(c) == 0)
		{
			nodes[a][c] = {};
		}

		nodes[a][c].push_back(b);

		if (nodes[b].count(c) == 0)
		{
			nodes[b][c] = {};
		}

		nodes[b][c].push_back(a);
	}

	vector<int> ds(K);
	rep(i, K)
	{
		cin >> ds[i];
	}


	//キューを使用して求める
	queue<Pop> q;

	//初期化
	rep(i, N)
	{
		//全ての町をセット
		q.emplace(i, i, 0);
	}

	//条件を満たす町を格納するためのset
	set<int> goals;

	while (!q.empty())
	{
		auto p = q.front(); q.pop();

		//K個の道路をたどることができた場合は、終了地点を答えに格納
		if (p.count == K)
		{
			goals.insert(p.p);
			continue;
		}
		
		//p.pに接続する料金がds[p.count]の道路に接続する町を、nodesから取得
		for (auto e : nodes[p.p][ds[p.count]])
		{
			q.emplace(p.end, e, p.count + 1);
		}
	}


	//結果表示
	cout << goals.size() << endl;

	for (auto g : goals)
	{
		cout << ++g << " ";
	}


	return 0;
}
0