제출 #387610

#	제출 시각UTC-0	아이디	문제	언어	결과	실행 시간	메모리
387610	2021-04-09 03:55:42	rama_pang	Escape Route (JOI21_escape_route)	C++17	70 / 100	9023 ms	197148 KiB

escape_route

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "escape_route.h"
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const lint inf = 1e18;
vector<lint> calculate_necessary_time(
    int N, int M, lint S, int Q,
    vector<int> A, vector<int> B,
    vector<lint> L, vector<lint> C,
    vector<int> U, vector<int> V, vector<lint> T) {
  // Solution:
  //
  // First, we compute the minimum time between any 2 cities
  // x and y, if we start from city x at time 0. We can
  // compute this in O(N^3) with Dijkstra.
  //
  // Next, process each starting city independently.
  // Generate the shortest path, assuming there is no restriction
  // on roads, and day is indefinitely long. Then, there is an
  // edge which is the "bottleneck" - the maximum time we can start
  // at source to generate this particular shortest path tree.
  // The bottleneck is the minimum C[i] - L[i] - dist[A[i]] if we
  // use the i-th edge in shortest path tree to go from A[i] to B[i].
  //
  // After identifying the bottleneck, if we start at any time before
  // the bottleneck, we can go to the other cities in time dist[v].
  // After arriving at city v, we will have to wait until the next day,
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 5 / 5
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 35 / 35
• Subtask 5: 0 / 30