oj.uz

답안 #858870

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
858870 2023-10-09T09:48:50 Z themaver1cks Commuter Pass (JOI18_commuter_pass) C++14
100 / 100
 392 ms 15752 KB 
#include <bits/stdc++.h>

using namespace std;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n, m;
  cin >> n >> m;
  int S, T, U, V;
  cin >> S >> T >> U >> V, S--, T--, U--, V--;
  vector<vector<pair<int, int>>> g(n);
  for (int i = 0; i < m; ++i) {
    int u, v, w;
    cin >> u >> v >> w, u--, v--;
    g[u].emplace_back(v, w);
    g[v].emplace_back(u, w);
  }

  auto dijkstra = [&](int s) {
    vector<long long> dist(n, 1e18);
    priority_queue<pair<long long, int>> pq;
    dist[s] = 0;
    pq.emplace(0, s);
    while (pq.size()) {
      auto d = -pq.top().first;
      auto u = pq.top().second;
      pq.pop();
      if (d > dist[u]) continue;
      for (auto [v, w] : g[u]) {
        if (dist[v] > dist[u] + w) {
          dist[v] = dist[u] + w;
          pq.emplace(-dist[v], v);
        }
      }
    }
    return dist;
  };

  auto solve = [&](int S, int T) {
    auto fromS = dijkstra(S);
    auto fromT = dijkstra(T);
    auto fromU = dijkstra(U);
    auto fromV = dijkstra(V);
    vector<long long> f(n, 1e18);
    // thứ tự quy hoạch động?
    // f[y] cập nhật cho f[x]
    // fromS[y] < fromS[x]
    vector<int> order(n);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int x, int y) {
      return fromS[x] < fromS[y];
    });
    long long ans = fromU[V];
    for (auto u : order) {
      f[u] = min(f[u], fromU[u]);
      for (auto [v, w] : g[u]) {
        if (fromS[u] + w == fromS[v] && fromS[u] + w + fromT[v] == fromS[T]) {
          f[v] = min(f[v], f[u]);
        }
      }
      if (fromS[u] + fromT[u] == fromS[T]) {
        ans = min(ans, f[u] + fromV[u]);
      }
    }
    return ans;
  };

  cout << min(solve(S, T), solve(T, S)) << endl;
  return 0;
}

Compilation message

commuter_pass.cpp: In lambda function:
commuter_pass.cpp:29:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   29 |       for (auto [v, w] : g[u]) {
      |                 ^
commuter_pass.cpp: In lambda function:
commuter_pass.cpp:56:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   56 |       for (auto [v, w] : g[u]) {
      |                 ^

Subtask #1
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 384 ms 15152 KB Output is correct
2 Correct 305 ms 14336 KB Output is correct
3 Correct 324 ms 13864 KB Output is correct
4 Correct 281 ms 15124 KB Output is correct
5 Correct 321 ms 14044 KB Output is correct
6 Correct 363 ms 15452 KB Output is correct
7 Correct 330 ms 14016 KB Output is correct
8 Correct 321 ms 13896 KB Output is correct
9 Correct 314 ms 13956 KB Output is correct
10 Correct 211 ms 13820 KB Output is correct
11 Correct 78 ms 10108 KB Output is correct
12 Correct 357 ms 14056 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 313 ms 14076 KB Output is correct
2 Correct 341 ms 13992 KB Output is correct
3 Correct 378 ms 13968 KB Output is correct
4 Correct 392 ms 14056 KB Output is correct
5 Correct 367 ms 13900 KB Output is correct
6 Correct 306 ms 14100 KB Output is correct
7 Correct 319 ms 14004 KB Output is correct
8 Correct 373 ms 14008 KB Output is correct
9 Correct 363 ms 13968 KB Output is correct
10 Correct 369 ms 14000 KB Output is correct
11 Correct 92 ms 10128 KB Output is correct
12 Correct 314 ms 13840 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 1116 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 10 ms 1628 KB Output is correct
5 Correct 5 ms 1112 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 2 ms 388 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 5 ms 1068 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct

Subtask #4
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 384 ms 15152 KB Output is correct
2 Correct 305 ms 14336 KB Output is correct
3 Correct 324 ms 13864 KB Output is correct
4 Correct 281 ms 15124 KB Output is correct
5 Correct 321 ms 14044 KB Output is correct
6 Correct 363 ms 15452 KB Output is correct
7 Correct 330 ms 14016 KB Output is correct
8 Correct 321 ms 13896 KB Output is correct
9 Correct 314 ms 13956 KB Output is correct
10 Correct 211 ms 13820 KB Output is correct
11 Correct 78 ms 10108 KB Output is correct
12 Correct 357 ms 14056 KB Output is correct
13 Correct 313 ms 14076 KB Output is correct
14 Correct 341 ms 13992 KB Output is correct
15 Correct 378 ms 13968 KB Output is correct
16 Correct 392 ms 14056 KB Output is correct
17 Correct 367 ms 13900 KB Output is correct
18 Correct 306 ms 14100 KB Output is correct
19 Correct 319 ms 14004 KB Output is correct
20 Correct 373 ms 14008 KB Output is correct
21 Correct 363 ms 13968 KB Output is correct
22 Correct 369 ms 14000 KB Output is correct
23 Correct 92 ms 10128 KB Output is correct
24 Correct 314 ms 13840 KB Output is correct
25 Correct 6 ms 1116 KB Output is correct
26 Correct 1 ms 344 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 10 ms 1628 KB Output is correct
29 Correct 5 ms 1112 KB Output is correct
30 Correct 1 ms 344 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Correct 2 ms 388 KB Output is correct
33 Correct 1 ms 348 KB Output is correct
34 Correct 5 ms 1068 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 1 ms 348 KB Output is correct
37 Correct 1 ms 348 KB Output is correct
38 Correct 1 ms 348 KB Output is correct
39 Correct 1 ms 348 KB Output is correct
40 Correct 284 ms 15752 KB Output is correct
41 Correct 275 ms 13948 KB Output is correct
42 Correct 326 ms 14076 KB Output is correct
43 Correct 88 ms 10112 KB Output is correct
44 Correct 87 ms 10104 KB Output is correct
45 Correct 244 ms 13332 KB Output is correct
46 Correct 251 ms 13800 KB Output is correct
47 Correct 315 ms 15180 KB Output is correct
48 Correct 102 ms 10108 KB Output is correct
49 Correct 246 ms 15312 KB Output is correct
50 Correct 268 ms 13728 KB Output is correct
51 Correct 257 ms 13516 KB Output is correct