結果

問題 No.92 逃走経路
ユーザー Mcpu3
提出日時 2020-02-19 15:31:22
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 991 bytes
コンパイル時間 1,038 ms
コンパイル使用メモリ 87,868 KB
実行使用メモリ 814,640 KB
最終ジャッジ日時 2024-10-08 01:52:19
合計ジャッジ時間 6,980 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other MLE * 1 -- * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
using namespace std;

int main() {
	int N, M, K, a, b;
	cin >> N >> M >> K;
	vector<vector<pair<int, long>>> e(N);
	for (int i = 0; i < M; i++) {
		long c;
		cin >> a >> b >> c;
		e[a - 1].emplace_back(b - 1, c);
		e[b - 1].emplace_back(a - 1, c);
	}
	vector<long> d(K);
	for (long& i : d) cin >> i;
	reverse(d.begin(), d.end());
	vector<int> ans;
	for (int i = 0; i < N; i++) {
		queue<pair<int, vector<long>::iterator>> f;
		for (pair<int, long>& j : e[i]) {
			if (d.front() == j.second) f.emplace(j.first, d.begin() + 1);
		}
		while (!f.empty()) {
			if (f.front().second == d.end()) {
				ans.push_back(i + 1);
				break;
			}
			for (pair<int, long>& j : e[f.front().first]) {
				if (*f.front().second == j.second) f.emplace(j.first, f.front().second + 1);
			}
			f.pop();
		}
	}
	cout << ans.size() << endl;
	for (int& i : ans) cout << i << ' ';
}
0