結果
| 問題 |
No.2909 Imaginary Summer
|
| ユーザー |
👑  ArcAki
|
| 提出日時 | 2025-02-01 19:19:02 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 341 ms / 6,000 ms |
| コード長 | 7,721 bytes |
| コンパイル時間 | 4,895 ms |
| コンパイル使用メモリ | 297,912 KB |
| 実行使用メモリ | 28,392 KB |
| 最終ジャッジ日時 | 2025-02-01 19:19:22 |
| 合計ジャッジ時間 | 18,395 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 37 |
ソースコード
// GPTo3-mini-highによる生成コードです。
#include <bits/stdc++.h>
using namespace std;
// 構造体 Station：各駅の座標とホテルからの最短到達時間 D を保持
struct Station {
double x, y;
double d; // ホテルから駅までの最短時間
};
// kd-tree のノード
struct KdNode {
double x, y, d; // 点の座標と，その点に対応する D 値
double minX, maxX, minY, maxY; // この部分木に含まれる点のバウンディングボックス
double subMinD; // 部分木中の最小 D 値
KdNode *left, *right;
};
// kd-tree を再帰的に構築する関数
// pts の [l, r) の区間から構築．分割軸は depth % 2 (0: x軸，1: y軸)
KdNode* buildKdTree(vector<Station> &pts, int l, int r, int depth) {
if(l >= r) return nullptr;
int axis = depth & 1; // 0: x軸，1: y軸
int mid = (l + r) / 2;
if(axis == 0) {
nth_element(pts.begin() + l, pts.begin() + mid, pts.begin() + r, [](const Station &a, const Station &b){
return a.x < b.x;
});
} else {
nth_element(pts.begin() + l, pts.begin() + mid, pts.begin() + r, [](const Station &a, const Station &b){
return a.y < b.y;
});
}
KdNode* node = new KdNode();
node->x = pts[mid].x;
node->y = pts[mid].y;
node->d = pts[mid].d;
node->left = buildKdTree(pts, l, mid, depth+1);
node->right = buildKdTree(pts, mid+1, r, depth+1);
// 自身の点でバウンディングボックスを初期化
node->minX = node->maxX = node->x;
node->minY = node->maxY = node->y;
node->subMinD = node->d;
if(node->left){
node->minX = min(node->minX, node->left->minX);
node->maxX = max(node->maxX, node->left->maxX);
node->minY = min(node->minY, node->left->minY);
node->maxY = max(node->maxY, node->left->maxY);
node->subMinD = min(node->subMinD, node->left->subMinD);
}
if(node->right){
node->minX = min(node->minX, node->right->minX);
node->maxX = max(node->maxX, node->right->maxX);
node->minY = min(node->minY, node->right->minY);
node->maxY = max(node->maxY, node->right->maxY);
node->subMinD = min(node->subMinD, node->right->subMinD);
}
return node;
}
// ユークリッド距離を計算する補助関数
inline double distPoint(double ax, double ay, double bx, double by) {
double dx = ax - bx, dy = ay - by;
return sqrt(dx*dx + dy*dy);
}
// kd-tree のノードのバウンディングボックスとクエリ点 (qx,qy) との最小距離を返す．
double boxDistance(KdNode* node, double qx, double qy) {
double dx = 0.0, dy = 0.0;
if(qx < node->minX) dx = node->minX - qx;
else if(qx > node->maxX) dx = qx - node->maxX;
if(qy < node->minY) dy = node->minY - qy;
else if(qy > node->maxY) dy = qy - node->maxY;
return sqrt(dx*dx + dy*dy);
}
// kd-tree探索の際のグローバル変数：現在の最良候補値
double bestCandidate;
// kd-tree を用いて，関数 f(p) = (p.d + distance(query, p)) の最小値を求める．
void queryKdTree(KdNode* node, double qx, double qy) {
if(!node) return;
// このノードの部分木内のどの点についても， f >= (subMinD + バウンディングボックスまでの距離) となる
double lowerBound = node->subMinD + boxDistance(node, qx, qy);
if(lowerBound >= bestCandidate) return;
// 現在のノードの点について計算
double curVal = node->d + distPoint(node->x, node->y, qx, qy);
bestCandidate = min(bestCandidate, curVal);
double leftLB = node->left ? (node->left->subMinD + boxDistance(node->left, qx, qy)) : numeric_limits<double>::infinity();
double rightLB = node->right ? (node->right->subMinD + boxDistance(node->right, qx, qy)) : numeric_limits<double>::infinity();
if(leftLB < rightLB){
if(leftLB < bestCandidate) queryKdTree(node->left, qx, qy);
if(rightLB < bestCandidate) queryKdTree(node->right, qx, qy);
} else {
if(rightLB < bestCandidate) queryKdTree(node->right, qx, qy);
if(leftLB < bestCandidate) queryKdTree(node->left, qx, qy);
}
}
// メイン関数
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, M, K;
cin >> N >> M >> K;
double P, Q;
cin >> P >> Q;
// 駅の座標を入力 (N 個)
vector<pair<double,double>> stationCoords(N);
for (int i = 0; i < N; i++){
double x, y;
cin >> x >> y;
stationCoords[i] = {x, y};
}
// 目的地の座標を入力 (K 個)
vector<pair<double,double>> destinations(K);
for (int i = 0; i < K; i++){
double a, b;
cin >> a >> b;
destinations[i] = {a, b};
}
// V の値を入力（ほぼ 10^18）
long long V_ll;
cin >> V_ll;
double V = (double) V_ll;
// 駅間を結ぶ鉄道路線 (M 本) のグラフを作成．
// 各路線は駅 u と v を結び，重みは (ユークリッド距離) ÷ V となる．
vector<vector<pair<int,double>>> graph(N);
for (int i = 0; i < M; i++){
int u, v;
cin >> u >> v;
u--; v--; // 0-indexed に変換
double dx = stationCoords[u].first - stationCoords[v].first;
double dy = stationCoords[u].second - stationCoords[v].second;
double segLen = sqrt(dx*dx + dy*dy);
double w = segLen / V;
graph[u].push_back({v, w});
graph[v].push_back({u, w});
}
// 各駅 j について，
// ホテルから駅 j へ徒歩で向かった場合の時間を初期値とし，
// 鉄道を使った場合の最短到達時間 D[j] をマルチソース Dijkstra で計算する．
vector<double> D(N, numeric_limits<double>::infinity());
priority_queue<pair<double,int>, vector<pair<double,int>>, greater<pair<double,int>>> pq;
for (int j = 0; j < N; j++){
double dx = stationCoords[j].first - P;
double dy = stationCoords[j].second - Q;
double d0 = sqrt(dx*dx + dy*dy);
D[j] = d0;
pq.push({d0, j});
}
while(!pq.empty()){
auto cur = pq.top();
pq.pop();
double curD = cur.first;
int u = cur.second;
if(curD > D[u] + 1e-12) continue;
for(auto &edge : graph[u]){
int v = edge.first;
double nd = curD + edge.second;
if(nd < D[v] - 1e-12){
D[v] = nd;
pq.push({nd, v});
}
}
}
// kd-tree のために，各駅を Station 型としてまとめる．
vector<Station> pts(N);
for (int j = 0; j < N; j++){
pts[j].x = stationCoords[j].first;
pts[j].y = stationCoords[j].second;
pts[j].d = D[j];
}
KdNode* kdRoot = buildKdTree(pts, 0, N, 0);
// 各目的地について，
// 片道の最短時間は，直接徒歩の場合と
// 「ホテル→(徒歩+鉄道)→ある駅→徒歩→目的地」のどちらか短い方で，
// 往復なので 2 倍して総和を求める．
double totalTime = 0.0;
for (int i = 0; i < K; i++){
double ax = destinations[i].first, ay = destinations[i].second;
double direct = distPoint(P, Q, ax, ay); // ホテルから目的地まで直接徒歩の場合の時間
bestCandidate = numeric_limits<double>::infinity();
// kd-tree を用いて，min_{j} { D[j] + distance( (X[j],Y[j]), (ax,ay) ) } を求める
queryKdTree(kdRoot, ax, ay);
double bestRoute = min(direct, bestCandidate);
totalTime += 2.0 * bestRoute;
}
cout << fixed << setprecision(10) << totalTime << "\n";
return 0;
}