Submission #421936

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
421936	2021-06-09 13:57:44	shenxy	Escape Route (JOI21_escape_route)	C++17	5 / 100	9075 ms	112068 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 <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef pair<long long, long long> ii;
typedef pair<ii, int> iii;
vector<long long> calculate_necessary_time(int N, int M, long long S, int Q, vector<int> A, vector<int> B, vector<long long> L, vector<long long> C, vector<int> U, vector<int> V, vector<long long> T) {
  vector<iii> adjlist[N];
  vector<long long> ans;
  for (int i = 0; i < M; ++i) {
    adjlist[A[i]].push_back(iii(ii(L[i], C[i]), B[i]));
    adjlist[B[i]].push_back(iii(ii(L[i], C[i]), A[i]));
  }
  for (int i = 0; i < Q; ++i) {
    ii dist[N];
    for (int i = 0; i < N; ++i) dist[i] = ii(100, 0);
    dist[U[i]] = ii(0, T[i]);
    priority_queue< iii, vector<iii>, greater<iii> > pq;
    pq.push(iii(dist[U[i]], U[i]));
    while (!pq.empty()) {
      iii x = pq.top();
      pq.pop();
      if (x.first != dist[x.second]) continue;
      if (x.second == V[i]) break;
      for (iii i: adjlist[x.second]) {
        ii dst;
        if (x.first.second + i.first.first <= i.first.second) dst = ii(x.first.first, x.first.second + i.first.first);
        else dst = ii(x.first.first + 1, i.first.first);
        if (dst < dist[i.second]) {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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