QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#178010 | #5458. Shortest Path Query | ClHg2 | TL | 1ms | 5944kb | C++14 | 2.4kb | 2023-09-13 17:14:34 | 2023-09-13 17:14:35 |
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: 5944kb
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
Time Limit Exceeded
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 ...