結果

問題 No.160 最短経路のうち辞書順最小
コンテスト
ユーザー izuru_matsuura
提出日時 2016-06-21 17:39:38
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
RE  
実行時間 -
コード長 2,425 bytes
コンパイル時間 1,873 ms
コンパイル使用メモリ 178,276 KB
実行使用メモリ 10,144 KB
最終ジャッジ日時 2024-10-11 18:25:11
合計ジャッジ時間 9,128 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3 RE * 1
other RE * 3 TLE * 1 -- * 22
権限があれば一括ダウンロードができます
コンパイルメッセージ
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;
                nstate.v = e.to;
                path.push_back(e.to);
                nstate.cost = make_pair(cost + e.cost, path);
                path.pop_back();
                if (D[nstate.v] > nstate.cost) {
                    D[nstate.v] = nstate.cost;
                    PQ.push(nstate);
                }
            }
        }
        cout << D[G].second << endl;
    }
}

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