結果

問題 No.1069 電柱 / Pole (Hard)
コンテスト
ユーザー tkr987
提出日時 2021-03-25 02:59:26
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 8,684 bytes
コンパイル時間 5,351 ms
コンパイル使用メモリ 226,940 KB
最終ジャッジ日時 2025-01-19 21:37:03
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 1 TLE * 2
other WA * 19 TLE * 25 MLE * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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) });
		g[e.second].push_back({ e.first, 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;
}
0