oj.uz

답안 #954563

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
954563 2024-03-28T07:06:34 Z abczz Commuter Pass (JOI18_commuter_pass) C++14
100 / 100
 324 ms 26472 KB 
#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#include <queue>
#define ll long long
#define ld long double

using namespace std;

priority_queue<array<ll, 2>, vector<array<ll, 2>>, greater<array<ll,2>>> pq;
vector <array<ll, 2>> adj[100000];
array <ll, 3> rt;
bool visited[100000];
queue <ll> Q;
array <ll, 2> dp[100000];
ll n, m, s, t, x, y, a, b, c, f, dist[3][100000], in[100000];

void dfs(ll u) {
  visited[u] = 1;
  for (auto [v, x] : adj[u]) {
    if (dist[0][v] + x == dist[0][u]) {
      ++in[v];
      if (!visited[v]) dfs(v);
    }
  }
}

int main() {
  cin >> n >> m >> s >> t >> x >> y;
  --s, --t, --x, --y;
  for (int i=0; i<m; ++i) {
    cin >> a >> b >> c;
    --a, --b;
    adj[a].push_back({b, c});
    adj[b].push_back({a, c});
  }
  for (int i=0; i<n; ++i) {
    for (int j=0; j<3; ++j) {
      dist[j][i] = 1e18;
    }
  }
  rt = {s, x, y};
  for (int i=0; i<3; ++i) {
    dist[i][rt[i]] = 0;
    pq.push({0, rt[i]});
    while (!pq.empty()) {
      auto [w, u] = pq.top();
      pq.pop();
      if (dist[i][u] != w) continue;
      for (auto [v, x] : adj[u]) {
        if (dist[i][v] > w+x) {
          dist[i][v] = w+x;
          pq.push({dist[i][v], v});
        }
      }
    }
  }
  dfs(t);
  for (int i=0; i<n; ++i) {
    dp[i] = {dist[1][i], dist[2][i]};
  }
  f = dist[1][y];
  Q.push(t);
  while (!Q.empty()) {
    auto u = Q.front();
    Q.pop();
    f = min(f, dist[1][u] + dp[u][1]);
    f = min(f, dist[2][u] + dp[u][0]);
    for (auto [v, x] : adj[u]) {
      if (dist[0][v] + x == dist[0][u]) {
        --in[v];
        dp[v][0] = min(dp[v][0], dp[u][0]);
        dp[v][1] = min(dp[v][1], dp[u][1]);
        if (!in[v]) Q.push(v);
      }
    }
  }
  cout << f << '\n';
}

Compilation message

commuter_pass.cpp: In function 'void dfs(long long int)':
commuter_pass.cpp:21:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   21 |   for (auto [v, x] : adj[u]) {
      |             ^
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:48:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   48 |       auto [w, u] = pq.top();
      |            ^
commuter_pass.cpp:51:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   51 |       for (auto [v, x] : adj[u]) {
      |                 ^
commuter_pass.cpp:70:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   70 |     for (auto [v, x] : adj[u]) {
      |               ^

Subtask #1
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 246 ms 19764 KB Output is correct
2 Correct 282 ms 22540 KB Output is correct
3 Correct 277 ms 26444 KB Output is correct
4 Correct 250 ms 23744 KB Output is correct
5 Correct 267 ms 22372 KB Output is correct
6 Correct 268 ms 23752 KB Output is correct
7 Correct 256 ms 22584 KB Output is correct
8 Correct 324 ms 22568 KB Output is correct
9 Correct 252 ms 23116 KB Output is correct
10 Correct 227 ms 23244 KB Output is correct
11 Correct 108 ms 17240 KB Output is correct
12 Correct 258 ms 23028 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 287 ms 20740 KB Output is correct
2 Correct 265 ms 24332 KB Output is correct
3 Correct 265 ms 24072 KB Output is correct
4 Correct 290 ms 24596 KB Output is correct
5 Correct 259 ms 24660 KB Output is correct
6 Correct 291 ms 26216 KB Output is correct
7 Correct 268 ms 26376 KB Output is correct
8 Correct 280 ms 24328 KB Output is correct
9 Correct 279 ms 24528 KB Output is correct
10 Correct 279 ms 24008 KB Output is correct
11 Correct 130 ms 18864 KB Output is correct
12 Correct 260 ms 26472 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 8796 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 2 ms 7260 KB Output is correct
4 Correct 27 ms 10064 KB Output is correct
5 Correct 14 ms 8540 KB Output is correct
6 Correct 3 ms 7348 KB Output is correct
7 Correct 3 ms 7516 KB Output is correct
8 Correct 4 ms 7516 KB Output is correct
9 Correct 3 ms 7504 KB Output is correct
10 Correct 15 ms 8796 KB Output is correct
11 Correct 2 ms 7260 KB Output is correct
12 Correct 2 ms 7260 KB Output is correct
13 Correct 2 ms 7260 KB Output is correct
14 Correct 2 ms 7260 KB Output is correct
15 Correct 3 ms 7392 KB Output is correct

Subtask #4
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 246 ms 19764 KB Output is correct
2 Correct 282 ms 22540 KB Output is correct
3 Correct 277 ms 26444 KB Output is correct
4 Correct 250 ms 23744 KB Output is correct
5 Correct 267 ms 22372 KB Output is correct
6 Correct 268 ms 23752 KB Output is correct
7 Correct 256 ms 22584 KB Output is correct
8 Correct 324 ms 22568 KB Output is correct
9 Correct 252 ms 23116 KB Output is correct
10 Correct 227 ms 23244 KB Output is correct
11 Correct 108 ms 17240 KB Output is correct
12 Correct 258 ms 23028 KB Output is correct
13 Correct 287 ms 20740 KB Output is correct
14 Correct 265 ms 24332 KB Output is correct
15 Correct 265 ms 24072 KB Output is correct
16 Correct 290 ms 24596 KB Output is correct
17 Correct 259 ms 24660 KB Output is correct
18 Correct 291 ms 26216 KB Output is correct
19 Correct 268 ms 26376 KB Output is correct
20 Correct 280 ms 24328 KB Output is correct
21 Correct 279 ms 24528 KB Output is correct
22 Correct 279 ms 24008 KB Output is correct
23 Correct 130 ms 18864 KB Output is correct
24 Correct 260 ms 26472 KB Output is correct
25 Correct 15 ms 8796 KB Output is correct
26 Correct 2 ms 7260 KB Output is correct
27 Correct 2 ms 7260 KB Output is correct
28 Correct 27 ms 10064 KB Output is correct
29 Correct 14 ms 8540 KB Output is correct
30 Correct 3 ms 7348 KB Output is correct
31 Correct 3 ms 7516 KB Output is correct
32 Correct 4 ms 7516 KB Output is correct
33 Correct 3 ms 7504 KB Output is correct
34 Correct 15 ms 8796 KB Output is correct
35 Correct 2 ms 7260 KB Output is correct
36 Correct 2 ms 7260 KB Output is correct
37 Correct 2 ms 7260 KB Output is correct
38 Correct 2 ms 7260 KB Output is correct
39 Correct 3 ms 7392 KB Output is correct
40 Correct 249 ms 23996 KB Output is correct
41 Correct 248 ms 22876 KB Output is correct
42 Correct 303 ms 23212 KB Output is correct
43 Correct 145 ms 18004 KB Output is correct
44 Correct 112 ms 17960 KB Output is correct
45 Correct 286 ms 22216 KB Output is correct
46 Correct 234 ms 21904 KB Output is correct
47 Correct 237 ms 23496 KB Output is correct
48 Correct 107 ms 15452 KB Output is correct
49 Correct 215 ms 23624 KB Output is correct
50 Correct 241 ms 22168 KB Output is correct
51 Correct 281 ms 22300 KB Output is correct