QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#80343#5458. Shortest Path QueryRainybunnyTL 3ms7880kbC++142.8kb2023-02-23 14:51:112023-02-23 14:51:12

Judging History

你现在查看的是测评时间为 2023-02-23 14:51:12 的历史记录

  • [2024-06-21 12:37:43]
  • 管理员手动重测本题所有提交记录
  • 测评结果:TL
  • 用时:1ms
  • 内存:7968kb
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-23 14:51:12]
  • 评测
  • 测评结果:0
  • 用时:3ms
  • 内存:7880kb
  • [2023-02-23 14:51:11]
  • 提交

answer

/*+Rainybunny+*/

#include <bits/stdc++.h>

#define rep(i, l, r) for (int i = l, rep##i = r; i <= rep##i; ++i)
#define per(i, r, l) for (int i = r, per##i = l; i >= per##i; --i)

typedef std::pair<int, int> PII;
#define fi first
#define se second

inline char fgc() {
    static char buf[1 << 17], *p = buf, *q = buf;
    return p == q && (q = buf + fread(p = buf, 1, 1 << 17, stdin), p == q) ?
      EOF : *p++;
}

template <typename Tp = int>
inline Tp rint() {
    Tp x = 0, s = fgc(), f = 1;
    for (; s < '0' || '9' < s; s = fgc()) f = s == '-' ? -f : f;
    for (; '0' <= s && s <= '9'; s = fgc()) x = x * 10 + (s ^ '0');
    return x * f;
}

template <typename Tp>
inline void wint(Tp x) {
    if (x < 0) putchar('-'), x = -x;
    if (9 < x) wint(x / 10);
    putchar(x % 10 ^ '0');
}

inline void chkmin(int& u, const int v) { v < u && (u = v, 0); }

const int MAXN = 5e4, IINF = 0x3f3f3f3f;
int n, m, q, qa[MAXN + 5], qb[MAXN + 5], qt[MAXN + 5];
std::vector<PII> adj[MAXN + 5];

namespace Subtask2 {

int dis[MAXN + 5];

inline void main() {
    rep (i, 2, n) {
        dis[i] = IINF;
        for (const PII& e: adj[i]) chkmin(dis[i], dis[e.fi] + 1);
    }
    rep (i, 1, q) wint(dis[qt[i]] * qa[i]), putchar('\n');
}

} // namespace Subtask2

namespace ShuodeDaoli {

std::map<int, int> dis[MAXN + 5];

inline void init() {
    dis[1][0] = 0;
    rep (i, 2, n) {
        auto touch = [&](const int v)->int& {
            auto&& it = dis[i].lower_bound(v);
            if (it != dis[i].end() && it->fi == v) return it->se;
            else return dis[i].emplace_hint(it, v, IINF)->se;
        };

        for (const PII& e: adj[i]) {
            for (auto&& it = dis[e.fi].begin(); it != dis[e.fi].end(); ++it) {
                chkmin(touch(it->fi + !e.se), it->se + e.se);
            }
        }

        for (auto&& it = dis[i].begin(); it != dis[i].end();) {
            auto&& nx = std::next(it);
            if (nx == dis[i].end()) break;
            if (nx->se >= it->se) dis[i].erase(nx);
            else it = nx;
        }
    }
}

inline void main() {
    init();
    rep (i, 1, q) {
        int ans = IINF;
        for (auto&& it = dis[qt[i]].begin(); it != dis[qt[i]].end(); ++it) {
            chkmin(ans, qa[i] * it->fi + qb[i] * it->se);
        }
        printf("%d\n", ans);
    }
}

} // namespace ShuodeDaoli

int main() {
    // freopen("gray.in", "r", stdin);
    // freopen("gray.out", "w", stdout);

    n = rint(), m = rint();
    rep (i, 1, m) {
        int u = rint(), v = rint(), c = rint();
        adj[v].emplace_back(u, c);
    }
    q = rint();
    rep (i, 1, q) qa[i] = rint(), qb[i] = rint(), qt[i] = rint();

    bool proA = true;
    rep (i, 1, q) proA &= qa[i] == qb[i];
    if (proA) return Subtask2::main(), 0;

    ShuodeDaoli::main();
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 7880kb

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: