結果
| 問題 | No.1069 電柱 / Pole (Hard) |
| ユーザー |
 tkr987
|
| 提出日時 | 2021-03-25 02:50:46 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 8,550 bytes |
| コンパイル時間 | 3,072 ms |
| コンパイル使用メモリ | 233,272 KB |
| 実行使用メモリ | 539,448 KB |
| 最終ジャッジ日時 | 2023-08-17 22:54:22 |
| 合計ジャッジ時間 | 8,428 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge12 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | MLE | - |
| testcase_01 | WA | - |
| testcase_02 | WA | - |
| testcase_03 | WA | - |
| testcase_04 | MLE | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
| testcase_47 | -- | - |
| testcase_48 | -- | - |
| testcase_49 | -- | - |
| testcase_50 | -- | - |
| testcase_51 | -- | - |
| testcase_52 | -- | - |
| testcase_53 | -- | - |
| testcase_54 | -- | - |
| testcase_55 | -- | - |
| testcase_56 | -- | - |
| testcase_57 | -- | - |
| testcase_58 | -- | - |
| testcase_59 | -- | - |
| testcase_60 | -- | - |
| testcase_61 | -- | - |
| testcase_62 | -- | - |
| testcase_63 | -- | - |
| testcase_64 | -- | - |
| testcase_65 | -- | - |
| testcase_66 | -- | - |
| testcase_67 | -- | - |
| testcase_68 | -- | - |
| testcase_69 | -- | - |
| testcase_70 | -- | - |
| testcase_71 | -- | - |
| testcase_72 | -- | - |
| testcase_73 | -- | - |
| testcase_74 | -- | - |
| testcase_75 | -- | - |
| testcase_76 | -- | - |
| testcase_77 | -- | - |
| testcase_78 | -- | - |
| testcase_79 | -- | - |
| testcase_80 | -- | - |
| testcase_81 | -- | - |
| testcase_82 | -- | - |
ソースコード
#pragma GCC diagnostic ignored "-Wunused-variable"
#pragma GCC diagnostic ignored "-Wunused-parameter"
#include <bits/stdc++.h>
using namespace std;
//#include <atcoder/all>
//using namespace atcoder;
//#define BOOST
#ifdef BOOST
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
using ml = boost::multiprecision::cpp_int;
using md = boost::multiprecision::cpp_dec_float_100;
#endif
//#define LONG_LONG_INT
#ifdef LONG_LONG_INT
using ll = int; using ld = long double;
const ll inf = 1000000000;
#else
using ll = long long; using ld = long double;
const ll inf = 4000000000000000000;
#endif
/***** type *****/
using pll = pair<ll, ll>; using pld = pair<ld, ld>;
template <class T> using vt = vector<T>;
template <class T> using vvt = vector<vector<T>>;
using vll = vt<ll>; using vvll = vvt<ll>;
using vld = vt<ld>; using vvld = vvt<ld>;
using vch = vt<char>; using vvch = vvt<char>;
using vstr = vt<string>; using vvstr = vvt<string>;
using vpll = vt<pll>; using vvpll = vvt<pll>;
using vpld = vt<pld>; using vvpld = vvt<pld>;
using setll = set<ll>; using setpll = set<pll>;
using setch = set<char>; using setstr = set<string>;
using msetll = multiset<ll>; using msetld = multiset<ld>;
using msetch = multiset<char>; using msetstr = multiset<string>;
using mg = vt<vll>; using lg = vt<vll>; using wlg = vt<vpll>;
/***** define *****/
#define all(c) (c).begin(), (c).end() // begin to end
#define allr(c) (c).rbegin(), (c).rend() // rbegin to rend
#define coutld cout << fixed << setprecision(10) // cout double
#define output(x) do { cout << x << endl; exit(0); } while(0)
#define rep(i, b, e) for (ll i = b; i < e; i++) // repeat
#define repr(i, b, e) for (ll i = b; e < i; i--) // repeat reverse
#define fori(i, ...) if (ll i = -1) for(__VA_ARGS__) if (i++, 1)
#define each(i, e, c) fori (i, auto&& e: c) // for each
/***** const value *****/
const long long llong_max = 9223372036854775807; // 9 * 10^18
const long double pi = 3.1415926535897932; // 3.14 ...
const long double eps = LDBL_EPSILON; // 2.22e-016
const size_t not_find = string::npos; // string::find()
/***** lambda *****/
auto Bit = [] // bit test
(auto x, auto i) { return ((x & (1LL << i)) != 0); };
auto Ceil = [] // if (a % b != 0) return a / b + 1;
(auto x) { return (ll)ceil(x); };
auto Count = [] // long long count value
(auto b, auto e, auto x) { return (ll)count(b, e, x); };
auto CtoL = [] // char to number
(auto c) { return (ll)c - (ll)'0'; };
auto EQLD = [] // long double equal
(auto a, auto b) { return fabsl(a - b) < eps; };
auto LtoC = [] // number to char
(auto n) { return (char)('0' + n); };
auto Pow2 = [] // long long pow2
(auto n) { return (1LL << n); };
auto Size = [] // long long collection size
(auto& c) { return (ll)(c).size(); };
/***** function *****/
template <class T, class S> pair<T, S> operator +
(pair<T, S> l, pair<T, S> r)
{ // pair<T, S> + pair<T, S>
return { l.first + r.first, l.second + r.second };
}
template <class T, class S> pair<T, S> operator -
(pair<T, S> l, pair<T, S> r)
{ // pair<T, S> - pair<T, S>
return { l.first - r.first, l.second - r.second };
}
template <class T> void MakeV2
(ll zs, ll ys, vvt<T>& v, T fill = T())
{ // vector<vector<T>> resize + fill
v.resize(zs); rep(z, 0, zs) v[z].resize(ys, fill);
}
template <class T> void InputV2
(ll ys, ll xs, vvt<T>& v, T fix = T())
{ // input vector<vector<T>> (T != struct) + fix
MakeV2(ys, xs, v, fix);
rep(y, 0, ys) rep(x, 0, xs) cin >> v[y][x], v[y][x] += fix;
}
void InputGraph(ll v, mg& g, ll vfix)
{ // input adjacency matrix
MakeV2(v, v, g, inf);
rep(i, 0, v) rep(j, 0, v) cin >> g[i][j];
}
void InputGraph(ll v, ll e, lg& g, ll vfix)
{ // input adjacency list
g.resize(v);
rep(i, 0, e)
{
ll a, b; cin >> a >> b; a += vfix, b += vfix;
g[a].push_back(b), g[b].push_back(a);
}
}
void InputGraph(ll v, ll e, wlg& g, ll vfix)
{ // input weighted adjacency list
g.resize(v);
rep(i, 0, e)
{
ll a, b, w; cin >> a >> b >> w; a += vfix, b += vfix;
g[a].push_back({ b,w }), g[b].push_back({ a,w });
}
}
void InputDigraph(ll v, ll e, lg& g, ll vfix)
{ // input directed adjacency list
g.resize(v);
rep(i, 0, e)
{
ll a, b; cin >> a >> b;
a += vfix, b += vfix; g[a].push_back(b);
}
}
void InputDigraph(ll v, ll e, wlg& g, ll vfix)
{ // input weighted directed adjacency list
g.resize(v);
rep(i, 0, e)
{
ll a, b, w; cin >> a >> b >> w;
a += vfix, b += vfix; g[a].push_back({ b,w });
}
}
template <class T> bool Range(ll x, T& v)
{ // x range size
if (x < 0 || ll(v.size()) <= x) return false;
return true;
}
template <class T> bool Range(ll y, ll x, T& v)
{ // yx range size
if (y < 0 || ll(v.size()) <= y) return false;
if (x < 0 || ll(v[y].size()) <= x) return false;
return true;
}
template <class T> T Pow(T x, T n, bool over = false)
{ // template Pow(x, n)
T res = 1;
if (0 < n)
{
res = Pow(x, n / 2);
res = res * res;
if (n % 2 != 0) res *= x;
if (over && inf < res) return inf;
}
return res;
}
ll Powll(ll x, ll n, bool over = false)
{ // long long Pow(x, n)
ll res = 1;
if (0 < n)
{
res = Pow(x, n / 2);
res = res * res;
if (n % 2 != 0) res *= x;
if (over && inf < res) return inf;
}
return res;
}
/***************************************/
/********** BEGIN OF NYAA LIB **********/
/***************************************/
namespace NyaaGadget {}
namespace NyaaGadget
{
/*** K-th ダイクストラ法ライブラリ O((V+E)logV) ***/
struct DijkstraResult
{
using ll = long long;
using ld = long double;
std::vector<ll> prev_vtx; // v->t遷移 pre_vtx[t] = v
//std::vector<ll> min_cost; // s->v最短経路コスト min_cost[v] = c
std::vector<ld> min_cost; // s->v最短経路コスト min_cost[v] = c
std::vector<ll> GetPath(ll s, ll t)
{ // s-t最短経路の復元、復元不能なら空のvectorを返す
std::vector<ll> path;
for (ll v = t; v != -1 && v != s; v = prev_vtx[v])
{
path.push_back(v);
if (prev_vtx[v] == -1) path.clear();
if (prev_vtx[v] == s) path.push_back(s);
}
std::reverse(path.begin(), path.end());
return path;
}
};
struct GT_NyaaKthDijkstra
{ // 重み付き隣接リストを入力とする
using ll = long long;
//using pll = std::pair<ll, ll>;
using pld = std::pair<ld, ll>;
//using GRAPH = std::vector<std::vector<pll>>;
using GRAPH = std::vector<std::vector<std::pair<ll, ld>>>;
ll k;
ll inf;
GRAPH g;
std::vector<DijkstraResult> res;
GT_NyaaKthDijkstra(GRAPH& g, ll inf, ll k) : k(k), inf(inf), g(g)
{ // 存在しない最短コストはinfで返す
res.resize(k);
for (ll i = 0; i < k; i++)
{
res[i].prev_vtx.resize(g.size(), -1);
res[i].min_cost.resize(g.size(), inf);
}
}
decltype(res)& Run(ll s, ll init)
{ // sからの最短経路を処理
//std::priority_queue<pll, std::vector<pll>, std::greater<pll>> pq;
std::priority_queue<pld, std::vector<pld>, std::greater<pld>> pq;
res[0].min_cost[s] = init, pq.push({ 0, s });
while (!pq.empty())
{ // priority_queueで小さいコストから優先して取り出す
auto [vcost, v] = pq.top(); pq.pop();
if (res.back().min_cost[v] < vcost) continue;
for (auto [t, ecost] : g[v])
{
//ll dk = vcost + ecost;
ld dk = vcost + ecost;
if (res[0].min_cost[t] > dk)
{
swap(res[0].min_cost[t], dk);
res[0].prev_vtx[t] = v;
pq.push({ res[0].min_cost[t], t });
}
for (ll i = 0; i < k - 1; i++)
{
if (dk < res[i + 1].min_cost[v] && res[i].min_cost[v] < dk)
{
swap(res[i + 1].min_cost[t], dk);
res[i + 1].prev_vtx[t] = v;
pq.push({ res[i + 1].min_cost[t], t });
}
}
}
}
return res;
}
};
}
/***************************************/
/*********** END OF NYAA LIB ***********/
/***************************************/
using namespace NyaaGadget;
//using mll = NT_NyaaModLL< 1000000007 >;
//using mll = NT_NyaaModLL< 998244353 >;
int main()
{
ll N, M, K; cin >> N >> M >> K;
ll X, Y; cin >> X >> Y, X--, Y--;
vpll pq(N); each(i, e, pq) cin >> e.first >> e.second;
vpll PQ(M); each(i, e, PQ) cin >> e.first >> e.second, e.first--, e.second--;
using G = std::vector<std::vector<std::pair<ll, ld>>>;
G g(N);
each(i, e, PQ) g[e.first].push_back({ e.second, hypot(pq[e.second].first - pq[e.first].first, pq[e.second].second - pq[e.first].first) });
GT_NyaaKthDijkstra kd(g, inf, K);
auto res = kd.Run(X, 0);
rep(i, 0, K) coutld << res[i].min_cost[Y] << endl;
return 0;
}