QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#178009 | #5458. Shortest Path Query | ClHg2 | WA | 42ms | 12080kb | C++14 | 2.4kb | 2023-09-13 17:14:09 | 2023-09-13 17:14:09 |
Judging History
answer
#include <algorithm>
#include <cstdint>
#include <iostream>
#include <stack>
#include <utility>
#include <vector>
namespace {
using std::cin;
using std::cout;
using std::int64_t;
const int kMaxN = 5.0e4 + 5, kInf = 1.0e9 + 5;
int n, m, q;
int deg[kMaxN];
std::vector<std::pair<int, int>> edges[kMaxN];
struct Point {
int x, y;
Point(int x, int y) : x(x), y(y) {}
};
inline bool operator==(const Point &a, const Point &b) {
return a.x == b.x && a.y == b.y;
}
inline bool operator<(const Point &a, const Point &b) {
return a.x == b.x ? a.y < b.y : a.x < b.x;
}
std::vector<Point> paths[kMaxN];
std::vector<Point> ConvexHull(std::vector<Point> polygon) {
std::sort(polygon.begin(), polygon.end());
polygon.erase(std::unique(polygon.begin(), polygon.end()), polygon.end());
std::vector<Point> convex_hull;
auto check = [](const Point &a, const Point &b, const Point &c) {
return int64_t{a.y - b.y} * (c.x - b.x) >= int64_t{b.y - c.y} * (b.x - a.x);
};
for (const Point &a : polygon) {
while (convex_hull.size() >= 2 &&
check(convex_hull.end()[-2], convex_hull.back(), a)) {
convex_hull.pop_back();
}
convex_hull.emplace_back(a);
}
return convex_hull;
}
void Topo() {
std::stack<int, std::vector<int>> stk;
for (int i = 1; i <= n; ++i) {
if (deg[i] == 0) paths[i].emplace_back(0, 0), stk.emplace(i);
}
while (!stk.empty()) {
int u = stk.top();
stk.pop();
paths[u] = ConvexHull(std::move(paths[u]));
for (const auto &edge : edges[u]) {
int v = edge.first, w = edge.second;
if (w == 0) {
for (const Point &path : paths[u]) {
paths[v].emplace_back(path.x + 1, path.y);
}
} else {
for (const Point &path : paths[u]) {
paths[v].emplace_back(path.x, path.y + 1);
}
}
if (--deg[v] == 0) stk.emplace(v);
}
}
}
} // namespace
int main() {
cin.tie(nullptr);
std::ios::sync_with_stdio(false);
cin >> n >> m;
while (m--) {
int u, v, w;
cin >> u >> v >> w, ++deg[v];
edges[u].emplace_back(v, w);
}
Topo();
cin >> q;
while (q--) {
int a, b, u;
cin >> a >> b >> u;
int ans = kInf;
for (const Point &path : paths[u]) {
ans = std::min(ans, a * path.x + b * path.y);
}
cout << ans << "\n";
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5860kb
input:
4 4 1 2 0 1 3 1 2 4 0 3 4 1 3 3 5 2 3 2 4 2 3 4
output:
3 4 4
result:
ok 3 number(s): "3 4 4"
Test #2:
score: -100
Wrong Answer
time: 42ms
memory: 12080kb
input:
50000 100000 1 2 1 2 3 0 3 4 1 4 5 0 5 6 1 6 7 0 7 8 1 8 9 1 9 10 0 10 11 1 11 12 1 12 13 1 13 14 0 14 15 0 15 16 0 16 17 0 17 18 1 18 19 1 19 20 0 20 21 1 21 22 0 22 23 0 23 24 1 24 25 1 25 26 0 26 27 1 27 28 0 28 29 0 29 30 0 30 31 0 31 32 1 32 33 0 33 34 1 34 35 1 35 36 1 36 37 1 37 38 0 38 39 0 ...
output:
171090050 250459598 258589143 259699419 104338880 16685198 59196446 64713954 46949896 245672377 94777502 84753103 267419449 192242757 216482422 147454419 111021650 80187604 247374700 111782626 121405290 249524638 191332392 202049239 343798460 173714177 174899498 97998224 96431009 280559577 164349486...
result:
wrong answer 1st numbers differ - expected: '164602050', found: '171090050'