結果

問題 No.160 最短経路のうち辞書順最小
ユーザー izuru_matsuuraizuru_matsuura
提出日時 2016-06-21 17:43:21
言語 C++11
(gcc 11.4.0)
結果
RE  
実行時間 -
コード長 2,553 bytes
コンパイル時間 1,643 ms
コンパイル使用メモリ 178,400 KB
実行使用メモリ 8,448 KB
最終ジャッジ日時 2024-10-11 18:25:24
合計ジャッジ時間 8,813 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 RE -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 TLE -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘bool {anonymous}::operator<(const {anonymous}::State&, const {anonymous}::State&)’:
main.cpp:56:5: warning: no return statement in function returning non-void [-Wreturn-type]
   56 |     }
      |     ^

ソースコード

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, S, G;
    vector<vector<Edge>> Graph;
    void input() {
        cin >> N >> M >> S >> G;
        Graph.clear(); Graph.resize(N);
        for (int i = 0; i < M; i++) {
            int a, b, c;
            cin >> a >> b >> c;
            Graph[a].push_back(Edge(a, b, c));
            Graph[b].push_back(Edge(b, a, c));
        }
    }

    typedef pair<int, vector<int>> C;

    const int INF = 1<<28;
    const C INF_C = make_pair(INF, vector<int>(1, 1000));

    struct State {
        int v;
        C cost;
        State() {}
        State(int v, C cost) : v(v), cost(cost) {}
    };
    bool operator<(const State& a, const State& b) {
        if (a.cost.first == b.cost.first) {
            a.cost.second > b.cost.second;
        } else {
            a.cost.first > b.cost.first;
        }
    }

    void solve() {
        priority_queue<State> PQ;
        vector<C> D(N, INF_C);
        D[S] = make_pair(0, vector<int>(1, S));
        PQ.push(State(S, D[S]));
        while (not PQ.empty()) {
            State s = PQ.top(); PQ.pop();
            int v = s.v;
            int cost = s.cost.first;
            //cout << v << " " << cost << endl;
            vector<int>& path = s.cost.second;
            for (int i = 0; i < Graph[v].size(); i++) {
                const Edge& e = Graph[v][i];
                State nstate;
                path.push_back(e.to);
                if (D[e.to].first > cost + e.cost || 
                        (D[e.to].first == cost + e.cost && D[e.to].second > path)) {
                    State nstate;
                    nstate.v = e.to;
                    nstate.cost = make_pair(cost + e.cost, path);
                    D[e.to] = nstate.cost;
                    PQ.push(nstate);
                }
                path.pop_back();
            }
        }
        cout << D[G].second << endl;
    }
}

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