Ledger Nano X - The secure hardware wallet
SHARE
TWEET

Untitled

a guest Apr 8th, 2020 100 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4.  
  5. int findShortestWay(int numOfVertices, int a, int b, int start, int end) {
  6.     int k = std::max(a, b);
  7.     std::vector<std::queue<int>> queues(k + 1, std::queue<int>());
  8.     long long currentVertex = start;
  9.     std::vector<int> distance(numOfVertices, -1);
  10.     distance[start] = 0;
  11.     queues[0].push(start);
  12.     int currentQueue = 0;
  13.     while (currentVertex != end) {
  14.         while (!queues[currentQueue].empty()) {
  15.             currentVertex = queues[currentQueue].front();
  16.             queues[currentQueue].pop();
  17.             if (currentVertex % numOfVertices == currentVertex * currentVertex % numOfVertices) {
  18.                 if (distance[(currentVertex + 1) % numOfVertices] == -1) {
  19.                     int minEdge = std::min(a, b);
  20.                     distance[(currentVertex + 1) % numOfVertices] = distance[currentVertex] + minEdge;
  21.                     queues[(currentQueue + minEdge) % (k + 1)].push((currentVertex + 1) % numOfVertices);
  22.                 }
  23.             } else {
  24.                 if (distance[(currentVertex + 1) % numOfVertices] == -1) {
  25.                     distance[(currentVertex + 1) % numOfVertices] = distance[currentVertex] + a;
  26.                     queues[(currentQueue + a) % (k + 1)].push((currentVertex + 1) % numOfVertices);
  27.                 }
  28.                 if (distance[(currentVertex * currentVertex + 1) % numOfVertices] == -1) {
  29.                     distance[(currentVertex * currentVertex + 1) % numOfVertices] = distance[currentVertex] + b;
  30.                     queues[(currentQueue + b) % (k + 1)].push((currentVertex * currentVertex + 1) % numOfVertices);
  31.                 }
  32.             }
  33.             if (distance[end] != -1) {
  34.                 return distance[end];
  35.             }
  36.         }
  37.         ++currentQueue;
  38.         currentQueue %= k + 1;
  39.     }
  40.     return distance[end];
  41. }
  42.  
  43. int main() {
  44.     int numOfVertices;
  45.     int a;
  46.     int b;
  47.     int x;
  48.     int y;
  49.     std::cin >> a >> b >> numOfVertices >> x >> y;
  50.     std::cout << findShortestWay(numOfVertices, a, b, x, y);
  51. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top