結果
| 問題 | No.1069 電柱 / Pole (Hard) |
| ユーザー |
 hitonanode
|
| 提出日時 | 2020-05-29 23:21:00 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 9,219 bytes |
| コンパイル時間 | 3,304 ms |
| コンパイル使用メモリ | 242,004 KB |
| 実行使用メモリ | 13,768 KB |
| 最終ジャッジ日時 | 2024-11-06 12:12:44 |
| 合計ジャッジ時間 | 6,923 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
13,768 KB |
| testcase_01 | AC | 2 ms
6,816 KB |
| testcase_02 | AC | 2 ms
6,816 KB |
| testcase_03 | AC | 2 ms
6,816 KB |
| testcase_04 | TLE | - |
| 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 | -- | - |
ソースコード
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(6); }; } fast_ios_;
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
template<typename T> void ndarray(vector<T> &vec, int len) { vec.resize(len); }
template<typename T, typename... Args> void ndarray(vector<T> &vec, int len, Args... args) { vec.resize(len); for (auto &v : vec) ndarray(v, args...); }
template<typename T> bool chmax(T &m, const T q) { if (m < q) {m = q; return true;} else return false; }
template<typename T> bool chmin(T &m, const T q) { if (m > q) {m = q; return true;} else return false; }
template<typename T1, typename T2> pair<T1, T2> operator+(const pair<T1, T2> &l, const pair<T1, T2> &r) { return make_pair(l.first + r.first, l.second + r.second); }
template<typename T1, typename T2> pair<T1, T2> operator-(const pair<T1, T2> &l, const pair<T1, T2> &r) { return make_pair(l.first - r.first, l.second - r.second); }
template<typename T> istream &operator>>(istream &is, vector<T> &vec){ for (auto &v : vec) is >> v; return is; }
template<typename T> ostream &operator<<(ostream &os, const vector<T> &vec){ os << "["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template<typename T> ostream &operator<<(ostream &os, const deque<T> &vec){ os << "deq["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template<typename T> ostream &operator<<(ostream &os, const set<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T> ostream &operator<<(ostream &os, const unordered_set<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T> ostream &operator<<(ostream &os, const multiset<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T> ostream &operator<<(ostream &os, const unordered_multiset<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &pa){ os << "(" << pa.first << "," << pa.second << ")"; return os; }
template<typename TK, typename TV> ostream &operator<<(ostream &os, const map<TK, TV> &mp){ os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }
template<typename TK, typename TV> ostream &operator<<(ostream &os, const unordered_map<TK, TV> &mp){ os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }
#define dbg(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ") " << __FILE__ << endl;
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/tag_and_trait.hpp>
using namespace __gnu_pbds; // find_by_order(), order_of_key()
template<typename TK> using pbds_set = tree<TK, null_type, less<TK>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename TK, typename TV> using pbds_map = tree<TK, TV, less<TK>, rb_tree_tag, tree_order_statistics_node_update>;
*/
template<typename T>
struct ShortestPath
{
int V, E;
int INVALID = -1;
std::vector<std::vector<std::pair<int, T>>> to;
ShortestPath() = default;
ShortestPath(int V) : V(V), E(0), to(V) {}
void add_edge(int s, int t, T len) {
assert(0 <= s and s < V);
assert(0 <= t and t < V);
to[s].emplace_back(t, len);
E++;
}
std::vector<T> dist;
std::vector<int> prev;
// Dijkstra algorithm
// Complexity: O(E log E)
void Dijkstra(int s) {
assert(0 <= s and s < V);
dist.assign(V, 1e18);
dist[s] = 0;
prev.assign(V, INVALID);
using P = std::pair<T, int>;
std::priority_queue<P, std::vector<P>, std::greater<P>> pq;
pq.emplace(0, s);
while(!pq.empty()) {
T d;
int v;
std::tie(d, v) = pq.top();
pq.pop();
if (dist[v] < d) continue;
for (auto nx : to[v]) {
T dnx = d + nx.second;
if (dist[nx.first] > dnx) {
dist[nx.first] = dnx, prev[nx.first] = v;
pq.emplace(dnx, nx.first);
}
}
}
}
// Bellman-Ford algorithm
// Complexity: O(VE)
bool BellmanFord(int s, int nb_loop) {
assert(0 <= s and s < V);
dist.assign(V, std::numeric_limits<T>::max());
dist[s] = 0;
prev.assign(V, INVALID);
for (int l = 0; l < nb_loop; l++) {
bool upd = false;
for (int v = 0; v < V; v++) {
if (dist[v] == std::numeric_limits<T>::max()) continue;
for (auto nx : to[v]) {
T dnx = dist[v] + nx.second;
if (dist[nx.first] > dnx) {
dist[nx.first] = dnx, prev[nx.first] = v;
upd = true;
}
}
}
if (!upd) return true;
}
return false;
}
// Warshall-Floyd algorithm
// Complexity: O(E + V^3)
std::vector<std::vector<T>> dist2d;
void WarshallFloyd() {
dist2d.assign(V, std::vector<T>(V, std::numeric_limits<T>::max()));
for (int i = 0; i < V; i++) {
dist2d[i][i] = 0;
for (auto p : to[i]) dist2d[i][p.first] = min(dist2d[i][p.first], p.second);
}
for (int k = 0; k < V; k++) {
for (int i = 0; i < V; i++) {
if (dist2d[i][k] = std::numeric_limits<T>::max()) continue;
for (int j = 0; j < V; j++) {
if (dist2d[k][j] = std::numeric_limits<T>::max()) continue;
dist2d[i][j] = min(dist2d[i][j], dist2d[i][k] + dist2d[k][j]);
}
}
}
}
};
using BS = bitset<16>;
int serial;
struct P_
{
double first;
BS second;
BS third;
int id_;
P_() = default;
P_(double a, BS b, BS path) : first(a), second(b), third(path), id_(serial++) {}
// bool operator<(const P_ &x) const { return first < x.first; }
bool operator>(const P_ &x) const {
if (first != x.first) return first > x.first;
return id_ > x.id_;
}
};
int main()
{
int N, M, K;
int X, Y;
cin >> N >> M >> K >> X >> Y;
X--, Y--;
vector<lint> P(N), Q(N);
REP(i, N) cin >> P[i] >> Q[i];
vector<double> e(M * 2);
vector<int> from(M * 2), to(M * 2);
ShortestPath<double> graph(N);
map<pint, int> e2id;
REP(i, M)
{
int s, t;
cin >> s >> t;
s--, t--;
double dx = P[s] - P[t];
double dy = Q[s] - Q[t];
e[i] = e[i + M] = sqrt(dx * dx + dy * dy);
from[i] = to[i + M] = s;
from[i + M] = to[i] = t;
graph.add_edge(s, t, e[i]);
graph.add_edge(t, s, e[i]);
e2id[pint(s, t)] = i;
e2id[pint(t, s)] = i + M;
}
graph.Dijkstra(X);
BS path;
path.reset();
int now = Y;
while (now != X)
{
int prv = graph.prev[now];
path[e2id[pint(prv, now)]] = 1;
now = prv;
}
vector<BS> checked;
priority_queue<P_, vector<P_>, greater<P_>> pq;
vector<BS> alivebs;
vector<BS> pathbs;
vector<double> ret;
BS state_;
REP(i, M * 2) state_[i] = 1;
checked.emplace_back(state_);
alivebs.emplace_back(state_);
pathbs.emplace_back(path);
ret.emplace_back(graph.dist[Y]);
while (ret.size() < K)
{
REP(eban, M * 2) if (pathbs.back()[eban])
{
BS b = alivebs.back();
b[eban] = 0;
ShortestPath<double> graph(N);
REP(i, M * 2) if (b[i])
{
graph.add_edge(from[i], to[i], e[i]);
}
graph.Dijkstra(X);
if (graph.dist[Y] > 1e16) continue;
BS path;
int now = Y;
while (now != X)
{
int prv = graph.prev[now];
path[e2id[pint(prv, now)]] = 1;
now = prv;
}
pq.emplace(graph.dist[Y], b, path);
}
bool flg_conti = true;
while (true)
{
if (pq.empty())
{
flg_conti = false;
break;
}
bool bad = false;
for (auto x : pathbs)
{
if (x == pq.top().third) bad = true;
}
if (!bad)
{
ret.emplace_back(pq.top().first);
}
alivebs.emplace_back(pq.top().second);
pathbs.emplace_back(pq.top().third);
pq.pop();
break;
}
if (!flg_conti) break;
}
if (ret.size() < K) ret.resize(K, -1);
REP(i, K)
{
if (ret[i] >= 0) cout << ret[i] << '\n';
else cout << -1 << '\n';
}
}