結果

問題 No.1069 電柱 / Pole (Hard)
コンテスト
ユーザー Nachia
提出日時 2026-01-14 14:46:56
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 109 ms / 2,000 ms
コード長 4,343 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,953 ms
コンパイル使用メモリ 138,388 KB
実行使用メモリ 13,008 KB
最終ジャッジ日時 2026-01-14 14:47:02
合計ジャッジ時間 4,800 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 79
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
const ll INF = 1ll << 60;
#define REP(i,n) for(ll i=0; i<ll(n); i++)
template <class T> using V = vector<T>;
template <class A, class B> void chmax(A& l, const B& r){ if(l < r) l = r; }
template <class A, class B> void chmin(A& l, const B& r){ if(r < l) l = r; }


#include <vector>
#include <queue>
#include <utility>
#include <optional>

struct ShortestPathProblemDirected {
  //using Weight = long long;
  using Weight = double;
  struct Edge { int from, to, id; Weight w; };
  int n;
  Weight inf;
  Weight zero;
  std::vector<Edge> edges;
  std::vector<std::vector<int>> inc;
  int s;
  int t;

  ShortestPathProblemDirected(int _n, Weight _inf, Weight _zero, int _s, int _t)
    : n(_n), inf(_inf), zero(_zero), edges(), inc(_n), s(_s), t(_t) {}

  int addEdge(int from, int to, Weight w){
    int e = edges.size();
    edges.push_back({ from, to, e, w });
    inc[from].push_back(e);
    return e;
  }

  std::vector<int> solve(const std::vector<bool>& edgeMask){
    if(s == t) return {};
    std::vector<Weight> dist(n, inf);
    std::vector<int> parent(n, -1);
    using Node = std::pair<Weight, int>;
    std::priority_queue<Node, std::vector<Node>, std::greater<Node>> que;
    auto check = [&](int v, int p, Weight d) -> void {
      if(!(d < dist[v])) return;
      dist[v] = d;
      parent[v] = p;
      que.push({ d, v });
    };
    check(s, -1, zero);
    while(que.size()){
      auto [d, v] = que.top(); que.pop();
      if(dist[v] < d) continue;
      for(int e : inc[v]) if(edgeMask[e]){
        check(edges[e].to, e, d + edges[e].w);
      }
    }
    if(parent[t] == -1) return {};
    std::vector<int> path;
    for(int v=t; v!=s; v=edges[path.back()].from){
      path.push_back(parent[v]);
    }
    std::reverse(path.begin(), path.end());
    return path;
  }

  struct Instance {
    ShortestPathProblemDirected* data;
    std::vector<bool> edgeMask;
    int rank;
    Weight wt;
    std::vector<int> path;

    Instance(ShortestPathProblemDirected* _data, std::vector<bool> _edgeMask, int _rank)
      : data(_data), edgeMask(_edgeMask), rank(_rank) {}

    bool solve(){
      path = data->solve(edgeMask);
      if(path.empty()) return false;
      wt = data->zero;
      for(int e : path) wt += data->edges[e].w;
      return true;
    }

    std::vector<Instance> split() const {
      std::vector<Instance> res;
      std::vector<bool> nextEdgeMask = edgeMask;
      int v = 0;
      for(int s=rank; s<(int)path.size(); s++){
        nextEdgeMask[path[s]] = false;
        Instance inst(data, nextEdgeMask, s);
        if(inst.solve()) res.push_back(std::move(inst));
        for(int e : data->inc[data->edges[path[s]].from]) nextEdgeMask[e] = false;
        nextEdgeMask[path[s]] = true;
      }
      return res;
    }
  };

  struct CmpWt {
    bool operator()(const Instance& l, const Instance& r){
      return r.wt < l.wt;
    }
  };

  std::priority_queue<Instance, std::vector<Instance>, CmpWt> que;
  bool KthStarted = false;

  std::optional<Weight> getNextSmallest(){
    if(!KthStarted){
      KthStarted = true;
      Instance inst(this, std::vector<bool>(edges.size(), true), 0);
      if(inst.solve()) que.push(std::move(inst));
    }
    else {
      if(que.empty()) return std::nullopt;
      auto h = que.top().split(); que.pop();
      for(auto& nx : h) que.push(std::move(nx));
    }

    if(que.empty()) return std::nullopt;
    return que.top().wt;
  }
};

#include <cmath>

void testcase(){
  std::cout.precision(15);
  std::cout << std::fixed;

  int N, M, K; cin >> N >> M >> K;
  int X, Y; cin >> X >> Y; X--; Y--;
  std::vector<int> posX(N), posY(N);
  for(int i=0; i<N; i++) std::cin >> posX[i] >> posY[i];

  ShortestPathProblemDirected task(N, 1.0e100, 0, X, Y);
  for(int i=0; i<M; i++){
    int u,v; std::cin >> u >> v; u--; v--;
    task.addEdge(u, v, hypot(double(posX[u] - posX[v]), double(posY[u] - posY[v])));
    task.addEdge(v, u, hypot(double(posX[u] - posX[v]), double(posY[u] - posY[v])));
  }

  for(int k=0; k<K; k++){
    auto buf = task.getNextSmallest();
    if(buf.has_value()){
      std::cout << *buf << "\n";
    } else {
      std::cout << "-1\n";
    }
  }
}

int main(){
  cin.tie(0)->sync_with_stdio(0);
  testcase();
  return 0;
}
0