結果

問題 No.160 最短経路のうち辞書順最小
コンテスト
ユーザー kyuna
提出日時 2019-07-28 02:30:52
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,635 bytes
コンパイル時間 695 ms
コンパイル使用メモリ 77,732 KB
最終ジャッジ日時 2024-11-14 21:31:09
合計ジャッジ時間 1,066 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp:20:19: error: 'numeric_limits' was not declared in this scope
   20 |     const T INF = numeric_limits<T>::max();
      |                   ^~~~~~~~~~~~~~
main.cpp:20:35: error: expected primary-expression before '>' token
   20 |     const T INF = numeric_limits<T>::max();
      |                                   ^
main.cpp:20:41: error: no matching function for call to 'max()'
   20 |     const T INF = numeric_limits<T>::max();
      |                                    ~~~~~^~
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/algorithm:60,
                 from main.cpp:1:
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
main.cpp:20:41: note:   candidate expects 2 arguments, 0 provided
   20 |     const T INF = numeric_limits<T>::max();
      |                                    ~~~~~^~
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
main.cpp:20:41: note:   candidate expects 3 arguments, 0 provided
   20 |     const T INF = numeric_limits<T>::max();
      |                                    ~~~~~^~
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/algorithm:61:
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/stl_algo.h:5746:5: note: candidate:

ソースコード

diff # 

#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <ostream>
using namespace std;

template <typename T>
struct Edge { int src, dst; T cost;
    Edge(int dst, T cost) : src(-1), dst(dst), cost(cost) { }
    Edge(int src, int dst, T cost) : src(src), dst(dst), cost(cost) { }
};
template <typename T> using Edges = vector<Edge<T>>;
template <typename T> using WeightedGraph = vector<Edges<T>>;
template <typename T> using Matrix = vector<vector<T>>;

template <typename T>
struct Dijkstra {
    const T INF = numeric_limits<T>::max();
    const WeightedGraph<T> &g;
    int V, s; vector<T> dist; vector<int> prev; Matrix<T> mat;
    Dijkstra(const WeightedGraph<T> &g, int s) : g(g), V(g.size()), s(s) {
        mat.assign(V, vector<int>(V));  // MLE に注意
        for (int u = 0; u < V; u++) for (auto e: g[u]) mat[u][e.dst] = e.cost;
        dist.assign(V, INF); prev.assign(V, -1);
        using Pi = pair<T, int>;
        priority_queue<Pi, vector<Pi>, greater<Pi>> que;
        dist[s] = 0; que.emplace(dist[s], s);
        while (!que.empty()) {
            T cost; int u; tie(cost, u) = que.top(); que.pop();
            if (dist[u] < cost) continue;
            for (auto &e: g[u]) {
                int v = e.dst; T nc = e.cost;
                if (dist[v] > dist[u] + nc) {
                    dist[v] = dist[u] + nc;
                    prev[v] = u;
                    que.emplace(dist[v], v);
                } else if (dist[v] == dist[u] + nc) {
                    prev[v] = min(prev[v], u);
                }
            }
        }
    }
    vector<int> build_path(int t) {
        vector<int> path;
        for (int u = t; u >= 0; u = prev[u]) path.emplace_back(u);
        //reverse(path.begin(), path.end());
        return path;
    }
    void dump_path(int t) { dump_path(build_path(t)); }
    void dump_path(const vector<int> &path) { int t = path.back();
        cerr << s << " -> " << t << " (d = ";
        if (dist[t] == INF) cerr << "∞): "; else cerr << dist[t] << "): ";
        for (auto it = path.begin(); it != path.end() - 1; it++)
            cerr << *it << " -[" << mat[*it][*(it + 1)] << "]-> ";
        if (s == path.front()) cerr << t; cerr << endl;
    }
};

int main() {
    int N, M, S, G; cin >> N >> M >> S >> G;
    WeightedGraph<int> g(N);
    while (M--) {
        int a, b, c; cin >> a >> b >> c;
        g[a].emplace_back(b, c);
        g[b].emplace_back(a, c);
    }
    Dijkstra<int> sssp(g, G);
    int i = 0;
    for (int x: sssp.build_path(S)) {
        if (i++) cout << " "; cout << x;
    }
    cout << endl;
    return 0;
}
0