結果

問題 No.160 最短経路のうち辞書順最小
ユーザー izuru_matsuura
提出日時 2016-06-21 17:50:11
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
RE  
実行時間 -
コード長 3,414 bytes
コンパイル時間 1,594 ms
コンパイル使用メモリ 179,688 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-10-11 18:26:00
合計ジャッジ時間 6,138 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 4
other RE * 26
権限があれば一括ダウンロードができます
コンパイルメッセージ
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 |     }
      |     ^
main.cpp: In function ‘int {anonymous}::calc(std::vector<int>&)’:
main.cpp:81:5: warning: no return statement in function returning non-void [-Wreturn-type]
   81 |     }
      |     ^

ソースコード

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;
        }
    }

    struct State0 {
        int v, cost;
        State0(int v, int cost) : v(v), cost(cost) {}
    };
    bool operator<(const State0& a, const State0& b) {
        return a.cost > b.cost;
    }
    int calc(vector<int>& D) {
        priority_queue<State0> PQ;
        D[S] = 0;
        PQ.push(State0(S, D[S]));
        while (not PQ.empty()) {
            State0 s = PQ.top(); PQ.pop();
            int v = s.v;
            int cost = s.cost;
            for (int i = 0; i < Graph[v].size(); i++) {
                const Edge& e = Graph[v][i];
                if (D[e.to] > cost + e.cost) {
                    D[e.to] = cost + e.cost;
                    PQ.push(State0(e.to, cost + e.cost));
                }
            }
        }
    }

    void solve() {
        vector<int> D0(N, INF);
        int LIM = calc(D0);
        priority_queue<State> PQ;
        vector<C> D(N, INF_C);
        D[S] = make_pair(0, vector<int>(1, S));
        for (int i = 0; i < N; i++) D[i].first = D0[i];
        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