QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#369752#6306. Chase Gameucup-team1191#WA 1ms3620kbC++204.4kb2024-03-28 17:30:002024-03-28 17:30:02

Judging History

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

  • [2024-03-28 17:30:02]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3620kb
  • [2024-03-28 17:30:00]
  • 提交

answer

/*
    author:  Maksim1744
    created: 28.03.2024 12:17:44
*/

#include "bits/stdc++.h"

using namespace std;

using ll = long long;
using ld = long double;

#define mp   make_pair
#define pb   push_back
#define eb   emplace_back

#define sum(a)     ( accumulate ((a).begin(), (a).end(), 0ll))
#define mine(a)    (*min_element((a).begin(), (a).end()))
#define maxe(a)    (*max_element((a).begin(), (a).end()))
#define mini(a)    ( min_element((a).begin(), (a).end()) - (a).begin())
#define maxi(a)    ( max_element((a).begin(), (a).end()) - (a).begin())
#define lowb(a, x) ( lower_bound((a).begin(), (a).end(), (x)) - (a).begin())
#define uppb(a, x) ( upper_bound((a).begin(), (a).end(), (x)) - (a).begin())

template<typename T>             vector<T>& operator--            (vector<T> &v){for (auto& i : v) --i;            return  v;}
template<typename T>             vector<T>& operator++            (vector<T> &v){for (auto& i : v) ++i;            return  v;}
template<typename T>             istream& operator>>(istream& is,  vector<T> &v){for (auto& i : v) is >> i;        return is;}
template<typename T>             ostream& operator<<(ostream& os,  vector<T>  v){for (auto& i : v) os << i << ' '; return os;}
template<typename T, typename U> pair<T,U>& operator--           (pair<T, U> &p){--p.first; --p.second;            return  p;}
template<typename T, typename U> pair<T,U>& operator++           (pair<T, U> &p){++p.first; ++p.second;            return  p;}
template<typename T, typename U> istream& operator>>(istream& is, pair<T, U> &p){is >> p.first >> p.second;        return is;}
template<typename T, typename U> ostream& operator<<(ostream& os, pair<T, U>  p){os << p.first << ' ' << p.second; return os;}
template<typename T, typename U> pair<T,U> operator-(pair<T,U> a, pair<T,U> b){return mp(a.first-b.first, a.second-b.second);}
template<typename T, typename U> pair<T,U> operator+(pair<T,U> a, pair<T,U> b){return mp(a.first+b.first, a.second+b.second);}
template<typename T, typename U> void umin(T& a, U b){if (a > b) a = b;}
template<typename T, typename U> void umax(T& a, U b){if (a < b) a = b;}

#ifdef HOME
#define SHOW_COLORS
#include "/mnt/c/Libs/tools/print.cpp"
#else
#define show(...) void(0)
#define debugf(fun)   fun
#define debugv(var)   var
#define mclock    void(0)
#define shows     void(0)
#define debug  if (false)
#define OSTREAM(...)    ;
#define OSTREAM0(...)   ;
#endif

template<typename T>
using pq = priority_queue<T, vector<T>, greater<T>>;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    int n, m, k, d;
    cin >> n >> m >> k >> d;
    --k;
    vector<vector<int>> g(n);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        --u; --v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    auto bfs = [&](int v) {
        vector<int> d(n, 1e9);
        d[v] = 0;
        queue<int> q;
        q.push(v);
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            for (int k : g[v]) {
                if (d[k] > d[v] + 1) {
                    d[k] = d[v] + 1;
                    q.push(k);
                }
            }
        }
        return d;
    };

    auto cost = bfs(k);
    for (int& x : cost)
        x = max(0, d - x);
    show(cost);
    vector<bool> covered(n);
    covered[0] = true;
    for (int i = 0; i < n; ++i) {
        if (cost[i] > 0)
            covered[i] = true;
    }

    auto fin = bfs(n - 1);
    vector<ll> path_cost(n + 5, 0);
    for (int i = 1; i < path_cost.size(); ++i) {
        path_cost[i] = path_cost[i - 1] + d - (i - 1) % d;
    }
    show(path_cost);

    ll ans = 1e18;
    pq<pair<ll, int>> q;
    vector<ll> dist(n, 1e18);
    q.emplace(cost[0], 0);
    dist[0] = cost[0];

    while (!q.empty()) {
        auto [dd, v] = q.top();
        q.pop();
        if (dd != dist[v]) continue;
        if (!covered[v]) {
            show(v, dd, fin[v]);
            ans = min(ans, dd + path_cost[fin[v] + 1]);
            show(ans);
            continue;
        }
        for (int k : g[v]) {
            if (dist[v] + cost[k] < dist[k]) {
                dist[k] = dist[v] + cost[k];
                q.emplace(dist[k], k);
            }
        }
    }

    if (covered[n - 1])
        ans = min(ans, dist[n - 1]);
    cout << ans << '\n';

    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3620kb

input:

5 5 3 1
1 2
2 4
4 5
1 3
3 5

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3612kb

input:

13 17 12 3
1 2
2 3
3 4
4 13
5 13
7 8
7 9
7 10
7 11
7 6
12 7
1 8
8 9
9 10
10 11
11 6
6 13

output:

7

result:

ok 1 number(s): "7"

Test #3:

score: 0
Accepted
time: 1ms
memory: 3544kb

input:

10 9 4 1
4 3
1 2
7 6
6 5
8 9
9 10
5 4
8 7
3 2

output:

9

result:

ok 1 number(s): "9"

Test #4:

score: 0
Accepted
time: 1ms
memory: 3500kb

input:

10 20 9 1
9 5
2 9
4 5
10 5
7 3
1 8
7 1
7 5
3 4
3 1
7 8
3 8
9 3
10 6
9 1
1 6
8 5
6 2
1 10
2 1

output:

1

result:

ok 1 number(s): "1"

Test #5:

score: 0
Accepted
time: 0ms
memory: 3592kb

input:

10 20 3 1
1 4
6 7
5 4
5 3
2 1
8 1
7 8
2 6
2 4
4 8
9 5
1 10
7 4
5 8
4 10
2 5
6 10
4 6
3 7
1 3

output:

1

result:

ok 1 number(s): "1"

Test #6:

score: 0
Accepted
time: 0ms
memory: 3588kb

input:

10 20 4 1
2 7
6 4
2 3
2 4
6 5
8 5
6 7
10 2
3 10
1 8
3 9
3 7
1 7
5 1
6 1
3 4
2 1
5 2
9 2
9 10

output:

2

result:

ok 1 number(s): "2"

Test #7:

score: -100
Wrong Answer
time: 0ms
memory: 3588kb

input:

10 20 1 10
10 9
2 5
7 8
7 10
10 8
8 9
5 6
3 1
6 4
7 9
2 3
3 6
2 1
8 6
5 8
7 4
4 3
2 4
4 1
9 6

output:

34

result:

wrong answer 1st numbers differ - expected: '24', found: '34'