結果
| 問題 | No.1069 電柱 / Pole (Hard) |
| ユーザー |
 fine
|
| 提出日時 | 2020-05-30 00:13:38 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 2,095 bytes |
| コンパイル時間 | 2,039 ms |
| コンパイル使用メモリ | 181,692 KB |
| 実行使用メモリ | 813,940 KB |
| 最終ジャッジ日時 | 2024-11-06 12:17:09 |
| 合計ジャッジ時間 | 5,497 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
6,820 KB |
| testcase_01 | AC | 2 ms
6,820 KB |
| testcase_02 | AC | 2 ms
6,820 KB |
| testcase_03 | AC | 2 ms
6,820 KB |
| 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 | -- | - |
ソースコード
#include <bits/stdc++.h>
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
using namespace std;
using ll = double;
constexpr char newl = '\n';
struct State {
int at;
ll cost;
bitset<2000> vis;
State(int at, ll cost) : at(at), cost(cost) {}
bool operator>(const State& s) const {
return cost > s.cost;
}
};
struct Edge {
int to;
ll cost;
Edge(int to, ll cost) : to(to), cost(cost) {}
};
using Graph = vector< vector<Edge> >; //隣接リスト
const ll INF = 1e15;
//const int NONE = -1;
//sは始点、mincは最短経路のコスト、prevsは最短経路をたどる際の前の頂点
void dijkstra(int s, int t, const Graph& graph, int K){
const int n = graph.size();
vector< vector<ll> > minc(n);
priority_queue<State, vector<State>, greater<State> > pq;
{
State hoge(s, 0);
hoge.vis.set(s);
pq.push(move(hoge));
}
while(!pq.empty()) {
State cur = pq.top();
pq.pop();
if (minc[cur.at].size() < K) minc[cur.at].push_back(cur.cost);
if (minc[t].size() >= K) break;
for(const Edge& e : graph[cur.at]) {
if (cur.vis[e.to]) continue;
ll cost = cur.cost + e.cost;
State nex(cur);
nex.vis.set(e.to);
nex.at = e.to;
nex.cost = cost;
pq.push(move(nex));
}
}
for (int i = 0; i < K; i++) {
cout << fixed << setprecision(15) << (i >= minc[t].size() ? -1 : minc[t][i]) << newl;
}
}
int main() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
int n, m, K;
cin >> n >> m >> K;
int x, y;
cin >> x >> y;
--x; --y;
vector<int> p(n), q(n);
for (int i = 0; i < n; i++) {
cin >> p[i] >> q[i];
}
Graph g(n);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
--u; --v;
ll cost = hypot(p[u] - p[v], q[u] - q[v]);
g[u].emplace_back(v, cost);
g[v].emplace_back(u, cost);
}
dijkstra(x, y, g, K);
return 0;
}