Submission #695132

#	Time	Username	Problem	Language	Result	Execution time	Memory
695132		NeroZein	Railway (BOI17_railway)	C++17	0 / 100	6 ms	16084 KiB

railway

#include <bits/stdc++.h>
using namespace std; 

const int N = 2003;
const int M = 30004; 

int n, m;
int b[M];
int p[M];
int cost[N][N];

set<int> v[N];

inline void bfs() {
  queue<pair<int, int>> q;
  memset(cost, -1, sizeof cost);
  q.emplace(b[0], 0);
  cost[b[0]][p[0]] = 0; 
  while (!q.empty()) {
    auto src = q.front();
    q.pop();
    if (src.first == b[1]) {
      cout << src.second; 
      exit(0);
    }
    for (auto c : v[src.first]) {
      int l = src.first - c;
      int r = src.first + c;
      if (l >= 0 && cost[l][c] == -1) {
        cost[l][c] = src.second + 1; 
        q.emplace(l, cost[l][c]);
        v[l].insert(c);
      }
      if (r <= n && cost[r][c] == -1) {
        cost[r][c] = src.second + 1;
        q.emplace(r, cost[r][c]);
        v[r].insert(c);
      }
    }
  }
}

signed main() {
  cin >> n >> m;
  for (int i = 0; i < m; ++i) {
    cin >> b[i] >> p[i];
    v[b[i]].insert(p[i]);
  }
  bfs();
  cout << -1 << '\n';
  return 0; 
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 15
• Subtask 3: 0 / 7
• Subtask 4: 0 / 29
• Subtask 5: 0 / 16
• Subtask 6: 0 / 25