結果

問題 No.1065 電柱 / Pole (Easy)
ユーザー rokahikou1rokahikou1
提出日時 2020-08-13 05:09:08
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,975 bytes
コンパイル時間 837 ms
コンパイル使用メモリ 95,044 KB
最終ジャッジ日時 2024-11-14 22:55:27
合計ジャッジ時間 3,159 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp: In function 'void dijkstra(int, std::vector<_Tp>&, Graph<T>&)':
main.cpp:37:22: error: 'numeric_limits' was not declared in this scope
   37 |     const auto INF = numeric_limits<T>::max();
      |                      ^~~~~~~~~~~~~~
main.cpp:37:38: error: expected primary-expression before '>' token
   37 |     const auto INF = numeric_limits<T>::max();
      |                                      ^
main.cpp:37:44: error: no matching function for call to 'max()'
   37 |     const auto 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:37:44: note:   candidate expects 2 arguments, 0 provided
   37 |     const auto 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:37:44: note:   candidate expects 3 arguments, 0 provided
   37 |     const auto INF = numeric_limits<T>::max();
      |                                       ~~~~~^~
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/algorithm:61:

ソースコード

diff # 

#include <algorithm>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define rep(i, n) for(int(i) = 0; (i) < (n); (i)++)
#define FOR(i, m, n) for(int(i) = (m); (i) < (n); (i)++)
#define All(v) (v).begin(), (v).end()
#define pb push_back
#define MP(a, b) make_pair((a), (b))
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int INF = 1 << 30;
const ll LINF = 1LL << 60;
const int MOD = 1e9 + 7;

template <typename T> struct edge {
    int to;
    T cost;
    edge(int t, T c) : to(t), cost(c) {}
};

template <typename T> using Graph = vector<vector<edge<T>>>;

template <typename T> void dijkstra(int s, vector<T> &d, Graph<T> &G) {
    priority_queue<pair<int, T>, vector<pair<int, T>>, greater<pair<int, T>>>
        que;
    const auto INF = numeric_limits<T>::max();
    fill(All(d), INF);
    d[s] = 0;
    que.push(make_pair(0, s));
    while(!que.empty()) {
        pair<int, T> p = que.top();
        que.pop();
        int v = p.second;
        if(d[v] < p.first)
            continue;
        for(auto e : G[v]) {
            if(d[e.to] > d[v] + e.cost) {
                d[e.to] = d[v] + e.cost;
                que.push(make_pair(d[e.to], e.to));
            }
        }
    }
}

int main() {
    int N, M;
    cin >> N >> M;
    int X, Y;
    cin >> X >> Y;
    X--, Y--;
    vector<int> p(N), q(N);
    Graph<double> G(N);
    rep(i, N) { cin >> p[i] >> q[i]; }
    rep(i, M) {
        int P, Q;
        cin >> P >> Q;
        P--, Q--;
        double cost =
            sqrt((p[P] - p[Q]) * (p[P] - p[Q]) + (q[P] - q[Q]) * (q[P] - q[Q]));
        G[P].pb(edge<double>(Q, cost));
        G[Q].pb(edge<double>(P, cost));
    }
    vector<double> dist(N);
    dijkstra<double>(X, dist, G);
    cout << fixed << setprecision(10) << dist[Y] << endl;
    return 0;
}
0