結果

問題 No.92 逃走経路
コンテスト
ユーザー izuru_matsuura
提出日時 2016-06-21 17:23:05
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 9 ms / 5,000 ms
コード長 1,784 bytes
コンパイル時間 1,504 ms
コンパイル使用メモリ 168,168 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-11 18:24:05
合計ジャッジ時間 2,581 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

namespace {

    typedef double real;
    typedef long long ll;

    template<class T> ostream& operator<<(ostream& os, const vector<T>& vs) {
        if (vs.empty()) return os << "[]";
        os << vs[0];
        for (int i = 1; i < vs.size(); i++) os << " " << vs[i];
        return os;
    }
    template<class T> istream& operator>>(istream& is, vector<T>& vs) {
        for (auto it = vs.begin(); it != vs.end(); it++) is >> *it;
        return is;
    }

    struct Edge {
        int from, to, cost;
        Edge(int from, int to, int cost) : from(from), to(to), cost(cost) {}
    };

    int N, M, K;
    vector<Edge> E;
    vector<int> D;
    void input() {
        cin >> N >> M >> K;
        E.clear();
        for (int i = 0; i < M; i++) {
            int a, b, c; cin >> a >> b >> c;
            a--; b--;
            E.push_back(Edge(a, b, c));
        }
        D.clear(); D.resize(K); cin >> D;
    }

    void solve() {
        vector<bool> P[2];
        P[0] = vector<bool>(N, true);
        P[1] = vector<bool>(N, false);
        for (int k = 0; k < K; k++) {
            int d = D[k];
            for (int i = 0; i < M; i++) {
                const Edge& e = E[i];
                if (e.cost == d) {
                    if (P[0][e.from]) P[1][e.to] = true;
                    if (P[0][e.to]) P[1][e.from] = true;
                }
            }
            swap(P[0], P[1]);
            fill(P[1].begin(), P[1].end(), false);
        }
        vector<int> ans;
        for (int i = 0; i < N; i++) {
            if (P[0][i]) {
                ans.push_back(i + 1);
            }
        }
        cout << ans.size() << endl;
        cout << ans << endl;
    }
}

int main() {
    input(); solve();
    return 0;
}
0