結果

問題 No.92 逃走経路
コンテスト
ユーザー Unbakedbread
提出日時 2026-08-21 01:10:51
言語 C++11
(gcc 15.2.0 + boost 1.90.0)
コンパイル:
g++-15 -O2 -lm -std=gnu++11 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 8 ms / 5,000 ms
+ 29µs
コード長 850 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 500 ms
コンパイル使用メモリ 83,428 KB
実行使用メモリ 5,888 KB
最終ジャッジ日時 2026-08-21 01:10:54
合計ジャッジ時間 2,109 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <utility>
#include <cstring>
#include <vector>
#include <bitset>
using namespace std;

int8_t N; int16_t M, K;
vector<pair<int8_t, int32_t>> G[100];
int32_t D[1000];

bitset<100> dp[1001];

int main() {
	scanf("%hhd%hd%hd", &N, &M, &K);
	while(M--) {
		int8_t A, B; int32_t C;
		scanf("%hhd%hhd%d", &A, &B, &C); --A, --B;
		G[A].emplace_back(B, C);
		G[B].emplace_back(A, C);
	}
	for(int i = 0; i < K; ++i) scanf("%d", &D[i]);
	
	dp[0].set();
	for(int16_t t = 0; t < K; ++t) {
		dp[t + 1].reset();
		for(int8_t v = 0; v < N; ++v) if(dp[t][v]) {
			for(const auto e : G[v]) dp[t + 1][e.first] = dp[t + 1][e.first] | (e.second == D[t]);
		}
	}
	
	vector<int8_t> ans;
	for(int8_t v = 0; v < N; ++v) if(dp[K][v]) ans.push_back(v);
	
	printf("%u\n", ans.size());
	for(const auto x : ans) printf("%d ", x + 1);
	printf("\n");
}
0