結果

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

ソースコード

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, vector<vector<Edge>>& P) {
        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));
                    P[e.to].clear();
                    P[e.to].push_back(e);
                }
                if (D[e.to] == cost + e.cost) {
                    P[e.to].push_back(e);
                }
            }
        }
    }

    vector<int> D;
    vector<vector<Edge>> P;
    ostream& operator<<(ostream& os, const Edge& e) {
        return os << "(" << e.from << "->" << e.to << ")";
    }

    vector<vector<int>> memo;
    vector<int> dfs(int v) {
        if (v == S) return vector<int>(1, S);
        if (memo[v][0] >= 0) return memo[v];
        vector<int> ret;
        ret.push_back(INF);
        for (int i = 0; i < P[v].size(); i++) {
            // e.to縺後＞縺ｾ縺ｿ縺ｦ繧久
            // e.from縺後″縺溘∪縺｡
            const Edge& e = P[v][i];
            auto p = dfs(e.from);
            p.push_back(v);
            ret = min(ret, p);
        }
        return memo[v] = ret;
    }

    void solve() {
        D.clear(); D.resize(N, INF);
        P.clear(); P.resize(N);
        calc(D, P);
        /*
        for (int i = 0; i < N; i++) {
            cout << i << " -> " << P[i] << endl;
        }
        cout << endl;
        */
        memo.clear(); memo.resize(N, vector<int>(1, -1));
        cout << dfs(G) << endl;
    }
}

int main() {
    vector<int> a = {4, 1};
    vector<int> b = {4, 3};
    input(); solve();
    return 0;
}
0