結果

問題 No.92 逃走経路
ユーザー TatamoTatamo
提出日時 2016-06-22 11:54:56
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 897 ms / 5,000 ms
コード長 1,846 bytes
コンパイル時間 856 ms
コンパイル使用メモリ 82,844 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-11 19:17:09
合計ジャッジ時間 3,360 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 21 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 1 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 897 ms
5,248 KB
testcase_06 AC 7 ms
5,248 KB
testcase_07 AC 7 ms
5,248 KB
testcase_08 AC 2 ms
5,248 KB
testcase_09 AC 13 ms
5,248 KB
testcase_10 AC 125 ms
5,248 KB
testcase_11 AC 102 ms
5,248 KB
testcase_12 AC 502 ms
5,248 KB
testcase_13 AC 7 ms
5,248 KB
testcase_14 AC 16 ms
5,248 KB
testcase_15 AC 22 ms
5,248 KB
testcase_16 AC 16 ms
5,248 KB
testcase_17 AC 18 ms
5,248 KB
testcase_18 AC 12 ms
5,248 KB
testcase_19 AC 9 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>

#define DBG(x) cerr << x << endl

using namespace std;

class Graph{
    public:
        vector<pair<int, int> >edges;
        Graph(){
        }
        void setEdge(int id, int cost){
            edges.push_back(make_pair(id, cost));
        }
};

vector<Graph> g;
vector<int> d;

map<int, Graph> search(){
    int count = 0;
    map<int, Graph> s;
    for(int i=1; i<g.size(); i++){
        s.insert(map<int, Graph>::value_type(i, g[i]));
    }
    map<int, Graph> s_next;
    for(int c=0; c<d.size(); c++){
        for(auto itr = s.begin(); itr!=s.end(); itr++){
            for(int i=0; i < itr->second.edges.size(); i++){
                int cost = itr->second.edges[i].second;
                if(cost == d[count]){
                    int index = itr->second.edges[i].first;
                    s_next.insert(map<int, Graph>::value_type(index, g[index]));
                }
            }
        }
        s = s_next;
        s_next.clear();
        count += 1;
    }
    return s;
}

int main(){
    int n,m,k;
    cin >> n >> m >> k;

    for(int i=0; i<=n; i++){
        g.push_back(Graph());
    }
    for(int i=0; i<m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        g[a].setEdge(b, c);
        g[b].setEdge(a, c);
    }

    for(int i=0; i<k; i++){
        int tmp;
        cin >> tmp;
        d.push_back(tmp);
    }

/*
    for(int i=0; i<g.size(); i++){
        for(int ii=0; ii<g[i].edges.size(); ii++){
            DBG(g[i].edges[ii].first);
            DBG(g[i].edges[ii].second);
            DBG("");
        }
    }
*/

    map<int, Graph> result = search();
    cout << result.size() << endl;
    for(auto itr=result.begin(); itr!=result.end(); itr++){
        cout << itr->first << " ";
    }
    cout << endl;

}
0