QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#675422#7184. Transport PlusesaYi_7WA 7ms7108kbC++233.2kb2024-10-25 18:33:402024-10-25 18:33:41

Judging History

你现在查看的是最新测评结果

  • [2024-10-25 18:33:41]
  • 评测
  • 测评结果:WA
  • 用时:7ms
  • 内存:7108kb
  • [2024-10-25 18:33:40]
  • 提交

answer

#include <bits/stdc++.h>
// #define pii pair<int, int>
#define int long long
// using namespace std;
struct node {
    double dis;
    int x, y;
    int prex, prey;
    // bool tag;  // 是否在线上

    bool operator>(const node& a) const { return dis > a.dis; }
};

void solve() {
    int n, t;
    std::cin >> n >> t;
    int xh, yh, xe, ye;
    std::cin >> xh >> yh >> xe >> ye;

    std::map<std::pair<int, int>, std::set<std::pair<int, int>>> eg;
    std::map<std::pair<int, int>, std::pair<int, int>> rood;
    std::map<std::pair<int, int>, double> dis;
    std::set<int> x, y;
    std::priority_queue<node, std::vector<node>, std::greater<node>> q;

    for (int i = 0; i < n; i++) {
        int a, b;
        std::cin >> a >> b;
        x.insert(a);
        y.insert(b);
        for (int j = 0; j <= 100; j++) {
            for (int k = 0; k <= 100; k++) {
                eg[{a, j}].emplace(k, b);
                eg[{a, j}].emplace(a, k);
            }
        }
        for (int j = 0; j <= 100; j++) {
            for (int k = 0; k <= 100; k++) {
                eg[{j, b}].emplace(k, b);
                eg[{j, b}].emplace(a, k);
            }
        }
        q.emplace(std::abs(a - xh), a, yh, xh, yh);
        q.emplace(std::abs(b - yh), xh, b, xh, yh);
    }

    while (!q.empty()) {
        auto now = q.top();
        q.pop();
        int di = now.dis;
        std::pair<int, int> cur = std::make_pair(now.x, now.y);
        if (dis.count(cur)) continue;
        dis[cur] = di;
        rood[cur] = std::make_pair(now.prex, now.prey);
        for (auto& cur1 : eg[cur]) {
            if (dis.count(cur1)) continue;
            q.emplace(di + t, cur1.first, cur1.second, cur.first, cur.second);
        }
    }

    double ans = std::sqrt((double)(xh - xe) * (double)(xh - xe) +
                           (double)(yh - ye) * (double)(yh - ye));
    double len = 1e8;

    for (auto& [cur, di] : dis) {
        auto& [cx, cy] = cur;
        if (cx != xe || cy != ye) continue;
        double cost = std::max(std::fabs(cx - xe), std::fabs(cy - ye)) + di;
        if (cost < len) {
            len = cost;
            if (cx != xe || cy != ye) rood[{xe, ye}] = cur;
        }
    }

    auto check = [&](int X, int Y) -> bool {
        return x.count(X) || y.count(Y);
    };

    if (ans < len) {
        // std::cout << ans << '\n';
        printf("%.10f\n", ans);
        std::cout << 1 << '\n';
        std::cout << 0 << ' ' << xe << ' ' << ye << '\n';
    } else {
        // std::cout << len << '\n';
        printf("%.10f\n", len);
        std::vector<std::pair<int, int>> ans_rood;
        std::pair<int, int> cur = {xe, ye};
        while (cur.first != xh || cur.second != yh) {
            ans_rood.emplace_back(cur);
            cur = rood[cur];
        }
        std::reverse(ans_rood.begin(), ans_rood.end());
        std::cout << ans_rood.size() << '\n';
        for(int i = 0; i < n; i++) {
            
        }
    }
}

signed main() {
    // std::ios::sync_with_stdio(false);
    // std::cin.tie(nullptr);

    int t = 1;
    // std::cin >> t;
    for (int i = 0; i < t; ++i) {
        solve();
    }

    return 0;
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 7ms
memory: 7108kb

input:

1 2
1 1
5 3
6 2

output:

4.4721359550
1
0 5 3

result:

wrong answer read 4.472136 but expected 4.000000, error = 0.472136