oj.uz

Submission #752224

# Submission time Handle Problem Language Result Execution time Memory
752224 2023-06-02T14:20:25 Z tch1cherin Olympic Bus (JOI20_ho_t4) C++17
26 / 100
 1000 ms 171872 KB 
#include <bits/stdc++.h>
using namespace std;

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

struct edge {
  int from, to, weight, cost, id;

  edge() {}

  edge(int _from, int _to, int _weight, int _cost, int _id) : from(_from), to(_to), weight(_weight), cost(_cost), id(_id) {}
};

struct node {
  int distance, parent;

  node() {
    distance = INT_MAX;
    parent = -1;
  }

  node(int _distance, int _parent) : distance(_distance), parent(_parent) {}
};

struct result {
  int edge;
  vector<int> distances; 
};

vector<node> dijkstra(vector<vector<edge>> graph, int start) {
  int n = (int)graph.size();
  vector<node> answer(n);
  min_heap<pair<int, int>> q;
  q.emplace(0, start);
  answer[start].distance = 0;
  while (!q.empty()) {
    auto [d, u] = q.top();
    q.pop();
    if (answer[u].distance > d) {
      continue;
    }
    for (auto [from, to, weight, cost, id] : graph[u]) {
      if (answer[from].distance + weight < answer[to].distance) {
        answer[to] = node(answer[from].distance + weight, id);
        q.emplace(answer[to].distance, to);
      }
    }
  }
  return answer;
}

vector<vector<edge>> transpose(vector<vector<edge>> graph) {
  int n = (int)graph.size();
  vector<vector<edge>> new_graph(n);
  for (int u = 0; u < n; u++) {
    for (auto [from, to, weight, cost, id] : graph[u]) {
      new_graph[to].emplace_back(to, from, weight, cost, id);
    }
  }
  return new_graph;
}

vector<vector<int>> find_shortest_paths_without_each_edge(vector<vector<edge>> graph, int start) {
  int n = (int)graph.size();
  int m = 0;
  for (int u = 0; u < n; u++) {
    for (auto [from, to, weight, cost, id] : graph[u]) {
      m = max(m, 1 + id);
    }
  }
  vector<node> result = dijkstra(graph, start);
  vector<int> dist(n);
  for (int i = 0; i < n; i++) {
    dist[i] = result[i].distance;
  }
  vector<vector<int>> answer(m, dist);
  for (auto [distance, parent] : result) {
    if (parent != -1) {
      vector<vector<edge>> new_graph = graph;
      for (int u = 0; u < n; u++) {
        for (int i = 0; i < (int)new_graph[u].size(); i++) {
          auto [from, to, weight, cost, id] = new_graph[u][i];
          if (id == parent) {
            new_graph[u].erase(new_graph[u].begin() + i);
            break;
          }  
        }
      }
      vector<node> new_result = dijkstra(new_graph, start);
      for (int i = 0; i < n; i++) {
        answer[parent][i] = new_result[i].distance;  
      }
    }
  }
  return answer;
}

void solve() {
  int n, m;
  cin >> n >> m;
  vector<vector<edge>> graph(n);
  for (int i = 0; i < m; i++) {
    int from, to, weight, cost;
    cin >> from >> to >> weight >> cost;
    from--, to--;
    graph[from].emplace_back(from, to, weight, cost, i);
  }
  vector<vector<edge>> rev_graph = transpose(graph);
  vector<vector<int>> result_a = find_shortest_paths_without_each_edge(graph, 0);
  vector<vector<int>> result_b = find_shortest_paths_without_each_edge(graph, n - 1);
  vector<vector<int>> rev_result_a = find_shortest_paths_without_each_edge(rev_graph, 0);
  vector<vector<int>> rev_result_b = find_shortest_paths_without_each_edge(rev_graph, n - 1);
  int ans = INT_MAX;
  int ab = dijkstra(graph, 0)[n - 1].distance;
  int ba = dijkstra(graph, n - 1)[0].distance;
  if (ab != INT_MAX && ba != INT_MAX) {
    ans = min(ans, ab + ba);
  }
  for (int u = 0; u < n; u++) {
    for (auto [from, to, weight, cost, id] : graph[u]) {
      int AB = INT_MAX, BA = INT_MAX;
      AB = min(AB, result_a[id][n - 1]);
      if (result_a[id][to] != INT_MAX && rev_result_b[id][from] != INT_MAX) {
        AB = min(AB, result_a[id][to] + rev_result_b[id][from] + weight);
      }
      BA = min(BA, result_b[id][0]);
      if (result_b[id][to] != INT_MAX && rev_result_a[id][from] != INT_MAX) {
        BA = min(BA, result_b[id][to] + rev_result_a[id][from] + weight); 
      }
      if (AB == INT_MAX || BA == INT_MAX) {
        continue;
      }
      ans = min(ans, AB + BA + cost);
    }
  }
  cout << (ans == INT_MAX ? -1 : ans) << "\n";
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  solve();
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 3660 KB Output is correct
2 Correct 5 ms 1216 KB Output is correct
3 Correct 49 ms 3772 KB Output is correct
4 Correct 51 ms 3864 KB Output is correct
5 Correct 4 ms 1108 KB Output is correct
6 Correct 6 ms 1140 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 324 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 59 ms 3660 KB Output is correct
11 Correct 58 ms 3752 KB Output is correct
12 Correct 53 ms 3672 KB Output is correct
13 Correct 18 ms 3668 KB Output is correct
14 Correct 31 ms 3720 KB Output is correct
15 Correct 30 ms 3676 KB Output is correct
16 Correct 32 ms 3668 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1062 ms 171724 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 3668 KB Output is correct
2 Correct 10 ms 1108 KB Output is correct
3 Correct 585 ms 133936 KB Output is correct
4 Correct 8 ms 1108 KB Output is correct
5 Correct 757 ms 171476 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 451 ms 171872 KB Output is correct
9 Correct 476 ms 171828 KB Output is correct
10 Correct 581 ms 171496 KB Output is correct
11 Correct 598 ms 171328 KB Output is correct
12 Correct 566 ms 171764 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 584 ms 171816 KB Output is correct
20 Correct 600 ms 171524 KB Output is correct
21 Correct 566 ms 171476 KB Output is correct
22 Correct 567 ms 171692 KB Output is correct

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 3660 KB Output is correct
2 Correct 5 ms 1216 KB Output is correct
3 Correct 49 ms 3772 KB Output is correct
4 Correct 51 ms 3864 KB Output is correct
5 Correct 4 ms 1108 KB Output is correct
6 Correct 6 ms 1140 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 324 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 59 ms 3660 KB Output is correct
11 Correct 58 ms 3752 KB Output is correct
12 Correct 53 ms 3672 KB Output is correct
13 Correct 18 ms 3668 KB Output is correct
14 Correct 31 ms 3720 KB Output is correct
15 Correct 30 ms 3676 KB Output is correct
16 Correct 32 ms 3668 KB Output is correct
17 Execution timed out 1062 ms 171724 KB Time limit exceeded
18 Halted 0 ms 0 KB -