QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#178010#5458. Shortest Path QueryClHg2TL 1ms5944kbC++142.4kb2023-09-13 17:14:342023-09-13 17:14:35

Judging History

你现在查看的是测评时间为 2023-09-13 17:14:35 的历史记录

  • [2024-06-21 12:38:18]
  • 管理员手动重测本题所有提交记录
  • 测评结果:TL
  • 用时:0ms
  • 内存:5900kb
  • [2023-09-13 17:14:35]
  • 评测
  • 测评结果:0
  • 用时:1ms
  • 内存:5944kb
  • [2023-09-13 17:14:34]
  • 提交

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
...

output:


result: