結果

問題 No.92 逃走経路
ユーザー noynotenoynote
提出日時 2017-04-23 11:46:00
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 2,041 bytes
コンパイル時間 4,260 ms
コンパイル使用メモリ 162,160 KB
実行使用メモリ 813,584 KB
最終ジャッジ日時 2023-09-29 01:24:32
合計ジャッジ時間 5,320 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 WA -
testcase_04 WA -
testcase_05 MLE -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
using namespace std;
const int INF = 2000000000;

int d[1005];
set<pair<int, int>> table; //同じ時間かつ同じ位置にいる場合の重複をはじく
vector<int> visit;

class Edge{
    public:
        int to, cost;
        Edge(int to, int cost) : to(to) ,cost(cost) {}
};

class Node{
    public:
        int dis;
        bool isUsed;
        Node(){
            this->dis = INF;
            this->isUsed = 0;
        }
};

typedef vector<vector<Edge>> AdjList;

void dijkstra(AdjList g, int start, int n, int k){
    vector<Node> node(n);
    queue<int> q;

    q.push(start);
    node[start].dis = 0;

    while(not q.empty()){
        int current = q.front(); q.pop();
        if(k == node[current].dis){
            visit.emplace_back(current);
            break;
        }
        table.insert(make_pair(current, node[current].dis));
        rep(i,g[current].size()){
            int next = g[current][i].to;
            if(node[next].isUsed == 0 && d[node[current].dis] == g[current][i].cost){
                node[next].dis = node[current].dis + 1;
                if(table.find(make_pair(next, node[next].dis)) != table.end()) continue;
                q.push(next);
            }
        }
    }
    return;
}

int main(){
    int n, m, k;
    cin >> n >> m >> k;
    AdjList g(n);
    rep(i,m){
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        g[a].emplace_back(Edge{b,c});
        g[b].emplace_back(Edge{a,c});
    }
    rep(i,k) cin >> d[i];
    rep(i,n){
        dijkstra(g,i,n,k);
    }

    cout << visit.size() << endl;
    for(auto it = visit.begin(); it != visit.end(); it++){
        if(it != visit.begin()) cout << ' ';
        cout << *it + 1;
    }
    cout << endl;
}
0