QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#625635#6306. Chase GameHamed5001WA 3ms8576kbC++142.4kb2024-10-09 20:09:562024-10-09 20:09:56

Judging History

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

  • [2024-10-09 20:09:56]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:8576kb
  • [2024-10-09 20:09:56]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 1, INF = 0x3f3f3f3f;
vector<int> adj[MAXN];
long long DIST[MAXN], BEST[MAXN];
long long DISTN[MAXN];
int N, M, K, D;

void bfs() {
  queue<pair<int, int>> q; 
  q.push({0, K});
  DIST[K] = 0;
  int mx = 1000;
  while (!q.empty() && mx--) {
    auto node = q.front(); q.pop();
    if (DIST[node.second] < node.first) continue;
    for (auto it : adj[node.second]) {
      if (DIST[it] < node.first + 1) continue;
      q.push({node.first + 1, it});
      DIST[it] = node.first + 1;
    }
  }
  q.push({0, N});
  DISTN[N] = 0;
  while (!q.empty() && mx--) {
    auto node = q.front(); q.pop();
    if (DISTN[node.second] < node.first) continue;
    for (auto it : adj[node.second]) {
      if (DISTN[it] < node.first + 1) continue;
      q.push({node.first + 1, it});
      DISTN[it] = node.first + 1;
    }
  }
}

long long range(long long n) {
  if (n < 1) return 0;
  return (n * (n + 1)) >> 1;
}

long long range(int l, int r) {
  return range(r) - range(l - 1);
}

long long calc(int node) {
  long long ret = 0;
  long long full = (DISTN[node] + 1) / D;
  ret += full * range(1, D);
  if ((DISTN[node] + 1) % D)
  ret += range(D - DISTN[node] % D, D);
  return ret;
}

long long dijkstra(int st) {
  priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
  pq.push({0, st});
  BEST[st] = 0;
  long long ans = 0;
  while (!pq.empty()) {
    auto [cost, node] = pq.top(); pq.pop(); 
    assert(cost >= 0);
    if (node == N) return cost;
    if (BEST[node] < cost) continue;
    for (auto it : adj[node]) {
      if (DIST[it] >= D) {
        if (BEST[N] > cost + calc(it)) {
          BEST[N] = cost + calc(it);
          pq.push({cost + calc(it), N});
        }
      }
      else if (BEST[it] > cost + D - DIST[it]) {
        BEST[it] = cost + D - DIST[it];
        pq.push({cost + D - DIST[it], it});
      }
    }
  }
  return -1;
}


int main() {
  cin.tie(0)->sync_with_stdio(false);
  memset(DIST, INF, sizeof DIST);
  memset(DISTN, INF, sizeof DISTN);
  memset(BEST, INF, sizeof BEST);
  cerr << DIST[0] << endl;
  cin >> N >> M >> K >> D;
  for (int i = 0; i < M; ++i) {
    int u, v; cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  bfs();
  cout << dijkstra(1);
  return 0;
}


详细

Test #1:

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

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: 8532kb

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: 0ms
memory: 8296kb

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: 2ms
memory: 8304kb

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: 2ms
memory: 8496kb

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: 8500kb

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: 0
Accepted
time: 0ms
memory: 8336kb

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:

24

result:

ok 1 number(s): "24"

Test #8:

score: 0
Accepted
time: 2ms
memory: 8528kb

input:

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

output:

15

result:

ok 1 number(s): "15"

Test #9:

score: -100
Wrong Answer
time: 3ms
memory: 8576kb

input:

1000 999 387 1
505 506
314 313
410 411
680 681
884 885
491 492
60 59
343 342
396 397
880 881
954 953
833 834
53 54
284 283
794 793
241 240
347 348
89 88
787 786
551 550
673 672
56 57
683 682
168 169
814 813
726 725
877 876
981 982
799 800
228 227
568 569
387 386
211 212
30 29
298 299
514 515
561 562...

output:

-1

result:

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