Guest User

Untitled

a guest
Dec 7th, 2019
110
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <algorithm>
  2. #include <assert.h>
  3. #include <chrono>
  4. #include <iostream>
  5. #include <limits>
  6. #include <random>
  7. #include <vector>
  8. #include <string>
  9. #include <utility>
  10. #include <queue>
  11. #include <unordered_map>
  12. #include <cmath>
  13. #include <unordered_set>
  14. #include <set>
  15. #include <list>
  16. #include <functional>
  17.  
  18. template <class T>
  19. class TimeMeasure {
  20. public:
  21. TimeMeasure () {
  22. point_ = std::chrono::steady_clock::now();
  23. }
  24. int GetTime() {
  25. std::chrono::steady_clock::time_point current = std::chrono::steady_clock::now();
  26. int result = std::chrono::duration_cast<T>(current - point_).count();
  27. point_ = std::chrono::steady_clock::now();
  28. return result;
  29. }
  30. void SetLast() {
  31. point_ = std::chrono::steady_clock::now();
  32. }
  33. private:
  34. std::chrono::steady_clock::time_point point_;
  35. };
  36.  
  37. struct Querry {
  38. int from = -1;
  39. int to = -1;
  40. };
  41.  
  42. template<typename T>
  43. std::ostream& operator<<(std::ostream& os, const std::vector<T>& vec) {
  44. os << "{";
  45. for (const auto& item : vec) {
  46. os << item << " ";
  47. }
  48. os << "}";
  49. return os;
  50. }
  51.  
  52. template<typename T>
  53. std::ostream& operator<<(std::ostream& os, const std::unordered_set<T>& vec) {
  54. os << "{";
  55. for (const auto& item : vec) {
  56. os << item << " ";
  57. }
  58. os << "}";
  59. return os;
  60. }
  61.  
  62. template<typename T, typename Q>
  63. std::ostream& operator<<(std::ostream& os, const std::pair<T, Q>& item) {
  64. os << "[" << item.first << " " << item.second << "] ";
  65. return os;
  66. }
  67.  
  68. std::vector<int> GenRandomArray(std::mt19937 *gen, int count, int from, int to) {
  69. std::uniform_int_distribution<int> dist(from, to);
  70. std::vector<int> data(count);
  71. for (auto& cur : data) {
  72. cur = dist(*gen);
  73. }
  74. return data;
  75. }
  76.  
  77.  
  78. struct Edge {
  79. int from = -1;
  80. int to = -1;
  81. int weight;
  82. };
  83.  
  84. std::ostream& operator<<(std::ostream& stream, const Edge& edge) {
  85. stream << "[ " << edge.from << ", " << edge.to << ", " << edge.weight << "] ";
  86. return stream;
  87. }
  88.  
  89. struct pair_hash
  90. {
  91. template <class P, class Q>
  92. std::size_t operator() (const std::pair<P, Q> &pair) const
  93. {
  94. return std::hash<P>()(pair.first) ^ std::hash<Q>()(pair.second);
  95. }
  96. };
  97.  
  98. std::vector<Edge> GenerateRandomGraph(std::mt19937 *gen,
  99. size_t graph_size,
  100. size_t edges_number, bool random_weight = false) {
  101. std::uniform_int_distribution<int> dist(0, graph_size - 1);
  102. std::uniform_int_distribution<int> dist_weight(0, 2);
  103.  
  104. std::unordered_set<std::pair<int, int>, pair_hash> edges;
  105. std::vector<Edge> result;
  106. while (result.size() < edges_number) {
  107. auto pair = std::make_pair(dist(*gen), dist(*gen));
  108. if (pair.first == pair.second) {
  109. continue;
  110. }
  111. // auto pair_second = std::make_pair(pair.second, pair.first);
  112. // if (edges.count(pair) == 0 && edges.count(pair_second) == 0) {
  113. edges.insert(pair);
  114.  
  115. result.push_back({pair.first + 1, pair.second + 1, 1000});
  116. if (random_weight) {
  117. result.back().weight = dist_weight(*gen);
  118. }
  119. // }
  120. }
  121. return result;
  122. }
  123.  
  124. std::vector<Edge> GenerateCycleGraph(std::mt19937 *gen,
  125. size_t graph_size, int number_of_cycles, int cycle_length,
  126. bool positive, std::unordered_set<int>& used_vertexes) {
  127. if (number_of_cycles * cycle_length + used_vertexes.size() > graph_size) {
  128. throw std::domain_error("WRONG PARAMS");
  129. }
  130. std::uniform_int_distribution<int> dist(0, graph_size - 1);
  131.  
  132. std::vector<Edge> result;
  133. for (int cycle_num = 1; cycle_num <= number_of_cycles; ++cycle_num) {
  134. int starting_vertex;
  135.  
  136. auto vert = dist(*gen);
  137. while (used_vertexes.count(vert) == 1) {
  138. vert = dist(*gen);
  139. }
  140.  
  141. starting_vertex = vert;
  142.  
  143. int last_vertex = starting_vertex;
  144. used_vertexes.insert(last_vertex);
  145.  
  146. for (int index = 1; index < cycle_length; ++index) {
  147. auto vert = dist(*gen);
  148. while (used_vertexes.count(vert) == 1) {
  149. vert = dist(*gen);
  150. }
  151.  
  152. result.push_back({last_vertex + 1, vert + 1, 1});
  153. last_vertex = vert;
  154. used_vertexes.insert(last_vertex);
  155. }
  156.  
  157. if (positive) {
  158. result.push_back({last_vertex + 1, starting_vertex + 1, 1});
  159. } else {
  160. result.push_back({last_vertex + 1, starting_vertex + 1, -cycle_length});
  161. }
  162. }
  163. return result;
  164. }
  165.  
  166. void Floyd(int vertex_number, const std::vector<Edge>& edges,
  167. std::vector<std::vector<int>>& distances) {
  168.  
  169. for (const auto& edge: edges) {
  170. distances.at(edge.from - 1).at(edge.to - 1) =
  171. std::min(distances.at(edge.from - 1).at(edge.to - 1), edge.weight);
  172. }
  173. for (int i = 0; i < vertex_number; ++i) {
  174. distances.at(i).at(i) = 0;
  175. }
  176.  
  177. for (int index_k = 0; index_k < vertex_number; ++index_k) {
  178. for (int index_i = 0; index_i < vertex_number; ++index_i) {
  179. for (int index_j = 0; index_j < vertex_number; ++index_j) {
  180. if (distances.at(index_i).at(index_k) == std::numeric_limits<int>::max()) {
  181. continue;
  182. }
  183. if (distances.at(index_k).at(index_j) == std::numeric_limits<int>::max()) {
  184. continue;
  185. }
  186. auto sum = distances.at(index_i).at(index_k) +
  187. distances.at(index_k).at(index_j);
  188. if (distances.at(index_i).at(index_j) > sum) {
  189. distances.at(index_i).at(index_j) = sum;
  190. }
  191. }
  192. }
  193. }
  194. }
  195.  
  196. int BellmanFord(int vertex_number, std::vector<Edge>& edges) {
  197. // std::cout<<edges<<std::endl;
  198. std::vector<int> distance(vertex_number + 1, std::numeric_limits<int>::max());
  199. std::vector<int> parent(vertex_number + 1, -1);
  200. for (int i = 1; i <=vertex_number; ++i) {
  201. edges.push_back({vertex_number + 1, i, 1});
  202. }
  203. // std::cout<<edges<<std::endl;
  204.  
  205.  
  206. distance.at(vertex_number) = 0;
  207.  
  208. for (int index = 0; index < vertex_number; ++index) {
  209.  
  210. for (const auto& edge : edges) {
  211. if (distance.at(edge.from - 1) == std::numeric_limits<int>::max()) {
  212. continue;
  213. }
  214. if (distance.at(edge.from - 1) + edge.weight < distance.at(edge.to - 1)) {
  215. distance.at(edge.to - 1) = distance.at(edge.from - 1) + edge.weight;
  216. parent.at(edge.to - 1) = edge.from - 1;
  217. }
  218. }
  219. }
  220.  
  221. std::unordered_set<int> problem_vertex;
  222. for (const auto& edge : edges) {
  223. if (distance.at(edge.from - 1) + edge.weight < distance.at(edge.to - 1)) {
  224. problem_vertex.insert(edge.from - 1);
  225. // std::cout << " NEGATIVE LOOP " << std::endl;
  226. }
  227. }
  228.  
  229. // std::cout<<":LK:LK "<<std::endl;
  230. int result = std::numeric_limits<int>::max();
  231. for (auto id : problem_vertex) {
  232. // std::cout<<edges<<std::endl;
  233. // std::cout<<problem_vertex<<std::endl;
  234. // std::cout<<parent<<std::endl;
  235. {
  236. std::unordered_set<int> path;
  237. auto current = id;
  238. path.insert(current);
  239. while (parent.at(current) != vertex_number && parent.at(current) != -1 &&
  240. path.count(parent.at(current)) == 0) {
  241. current = parent.at(current);
  242. // std::cout << "K:ffLK: "<< current<<std::endl;
  243. path.insert(current);
  244. }
  245. // std::cout<<":LK "<<std::endl;
  246. id = current;
  247. // id = parent.at(current);
  248. }
  249. auto current = id;
  250. if (current == -1) {
  251. // continue;
  252. }
  253. // std::cout<<":LK:L "<< current <<std::endl;
  254. // std::vector<int> path;
  255. // path.push_back(current);
  256.  
  257. if (current < result) {
  258. result = current;
  259. }
  260. while (id != parent.at(current) && current != parent.at(current) &&
  261. -1 != parent.at(current)) {
  262. // std::cout<<id<<" "<<current<<" "<<parent.at(current)<<std::endl;
  263. current = parent.at(current);
  264. // path.push_back(current);
  265. if (current < result) {
  266. result = current;
  267. }
  268. }
  269. // std::cout<<path<<std::endl;
  270. }
  271. // std::cout << result << std::endl;
  272. // std::cout<<problem_vertex<<std::endl;
  273.  
  274. // std::cout<<":LK:LK 2 "<<std::endl;
  275.  
  276. if (result == std::numeric_limits<int>::max()) {
  277. return -1;
  278. }
  279. return result + 1;
  280. }
  281.  
  282. std::vector<int> SolveSimple(int vertex_number, const std::vector<Edge>& edges,
  283. const std::vector<Querry>& querries) {
  284. std::vector<std::vector<int>> distances(vertex_number,
  285. std::vector<int>(vertex_number,
  286. std::numeric_limits<int>::max()));
  287. Floyd(vertex_number, edges, distances);
  288.  
  289. std::vector<int> result(querries.size());
  290. for (size_t i = 0; i < querries.size(); ++i) {
  291. result[i] = distances.at(querries.at(i).from - 1).at(querries.at(i).to - 1);
  292. if (result[i] == std::numeric_limits<int>::max()) {
  293. result[i] = -1;
  294. }
  295. }
  296. return result;
  297. }
  298.  
  299. class Graph {
  300. public:
  301. explicit Graph(int vertex_number) : vertex_number_(vertex_number),
  302. edges_(vertex_number) {
  303. }
  304.  
  305. void AddEdge(int from, int to, int weight) {
  306. edges_[from].push_back(std::make_pair(to, weight));
  307. }
  308.  
  309. std::vector<int> Dijkstra(int src, const std::vector<Querry>& querries,
  310. const std::vector<int>& querry_ind) {
  311. std::priority_queue<std::pair<int, int>,
  312. std::vector<std::pair<int, int>>,
  313. std::greater<std::pair<int, int>>> heap;
  314. std::vector<int> distances(vertex_number_, std::numeric_limits<int>::max());
  315.  
  316. heap.push(std::make_pair(0, src));
  317. distances[src] = 0;
  318. std::unordered_set<int> to_set;
  319. for (const auto& ind : querry_ind) {
  320. to_set.insert(querries.at(ind).to - 1);
  321. }
  322.  
  323. while (!heap.empty())
  324. {
  325. int u_vertex = heap.top().second;
  326. to_set.erase(u_vertex);
  327. heap.pop();
  328. if (to_set.empty()) {
  329. break;
  330. }
  331.  
  332. for (auto it = edges_[u_vertex].begin(); it != edges_[u_vertex].end(); ++it) {
  333. auto dist = distances[u_vertex] + it->second;
  334. if (distances[it->first] > dist)
  335. {
  336. distances[it->first] = dist;
  337. heap.push(std::make_pair(distances[it->first], it->first));
  338. }
  339. }
  340. }
  341.  
  342. return distances;
  343. }
  344.  
  345. private:
  346. int vertex_number_;
  347. std::vector<std::vector<std::pair<int, int>>> edges_;
  348. };
  349.  
  350. template <class T>
  351. class Heap {
  352. public:
  353. explicit Heap(bool min_or_max) : min_or_max_(min_or_max) {
  354. }
  355.  
  356. void Add(const T& value) {
  357. auto position = values_.size();
  358. values_.push_back(value);
  359. auto current_position = SiftUpStep(position);
  360. while (position != current_position) {
  361. position = current_position;
  362. current_position = SiftUpStep(current_position);
  363. }
  364. }
  365.  
  366. T ExtractMin() {
  367. auto result = values_.at(0);
  368. DeleteByPosition(0);
  369. return result;
  370. }
  371.  
  372. const T& GetTop() const {
  373. assert(!values_.empty());
  374. return values_.front();
  375. }
  376.  
  377. bool Empty() const {
  378. return values_.empty();
  379. }
  380.  
  381. size_t GetSize() const {
  382. return values_.size();
  383. }
  384.  
  385. void DecreasePriority(const T& item) {
  386. bool found = false;
  387. for (size_t ind = 0; ind < values_.size(); ++ind) {
  388. if (values_[ind].key == item.key) {
  389. values_[ind].priority = item.priority;
  390. auto position = ind;
  391. auto current_position = SiftUpStep(position);
  392. while (position != current_position) {
  393. position = current_position;
  394. current_position = SiftUpStep(current_position);
  395. }
  396. found = true;
  397. break;
  398. }
  399. }
  400.  
  401. if (!found) {
  402. Add(item);
  403. }
  404. }
  405.  
  406. const auto& GetValues() const {
  407. return values_;
  408. }
  409.  
  410. private:
  411. bool min_or_max_;
  412. const size_t heap_arity_ = 2;
  413. std::vector<T> values_;
  414. std::vector<T> deleted_values_;
  415.  
  416. inline bool compare_(const T& lhs, const T& rhs) const {
  417. if (min_or_max_) {
  418. return lhs.priority > rhs.priority;
  419. } else {
  420. return lhs.priority < rhs.priority;
  421. }
  422. }
  423.  
  424. void DeleteByPosition(size_t position) {
  425. if (position + 1 == values_.size()) {
  426. values_.pop_back();
  427. return;
  428. }
  429. values_.at(position) = values_.back();
  430. values_.pop_back();
  431.  
  432. auto current_position = SiftUpStep(position);
  433. while (position != current_position) {
  434. position = current_position;
  435. current_position = SiftUpStep(current_position);
  436. }
  437.  
  438. current_position = SiftDownStep(position);
  439. while (position != SiftDownStep(position)) {
  440. position = current_position;
  441. current_position = SiftDownStep(current_position);
  442. }
  443. }
  444.  
  445. size_t SiftUpStep(size_t position) {
  446. if (position == 0) {
  447. return position;
  448. } else {
  449. auto parent = GetParent(position);
  450. if (compare_(values_.at(position), values_.at(parent))) {
  451. std::swap(values_.at(position), values_.at(parent));
  452. return parent;
  453. } else {
  454. return position;
  455. }
  456. }
  457. }
  458.  
  459. size_t SiftDownStep(size_t position) {
  460. auto child = GetBestChild(position);
  461. if (child != std::numeric_limits<size_t>::max()) {
  462. if (compare_(values_.at(child), values_.at(position))) {
  463. std::swap(values_.at(child), values_.at(position));
  464. }
  465. return child;
  466. } else {
  467. return position;
  468. }
  469. }
  470.  
  471. size_t GetBestChild(size_t position) const {
  472. size_t result = std::numeric_limits<size_t>::max();
  473. for (size_t i = 0; i < heap_arity_; ++i) {
  474. auto child_ind = GetKthChild(position, i);
  475. if (child_ind < values_.size()) {
  476. if (i == 0) {
  477. result = child_ind;
  478. } else {
  479. if (compare_(values_.at(child_ind), values_.at(result))) {
  480. result = child_ind;
  481. }
  482. }
  483. }
  484. }
  485. return result;
  486. }
  487. size_t GetParent(size_t ind) const {
  488. return (ind - 1) / heap_arity_;
  489. }
  490.  
  491. size_t GetKthChild(size_t ind, size_t k_num) const {
  492. assert(k_num < heap_arity_);
  493. return heap_arity_ * ind + k_num + 1;
  494. }
  495. };
  496.  
  497. struct HeapItem {
  498. int key = -1;
  499. int priority = -1;
  500. };
  501.  
  502. template <class T>
  503. std::ostream& operator<<(std::ostream& os, const Heap<T>& heap) {
  504. for (const auto& item : heap.GetValues()) {
  505. os << item << " | ";
  506. }
  507. return os;
  508. }
  509.  
  510. std::ostream& operator<<(std::ostream& os, const HeapItem& item) {
  511. os << "[" << item.key << ", " << item.priority << "]";
  512. return os;
  513. }
  514.  
  515. bool operator==(const HeapItem& lhs, const HeapItem& rhs) {
  516. return lhs.key == rhs.key && lhs.priority == rhs.priority;
  517. }
  518.  
  519. class PriorityQueue {
  520. public:
  521. void AddItem (const HeapItem& item) {
  522. // std::cout<<":LK:dfdL "<<item.key<<" "<<item.priority<<std::endl;
  523.  
  524. values_.push_back(item);
  525. }
  526.  
  527. HeapItem ExtractMin() {
  528. assert(!values_.empty());
  529. // std::cout<<"VALS "<<values_<<std::endl;
  530. int lowest_proirity = values_.front().priority;
  531. HeapItem result = values_.front();
  532. for (const auto& item : values_) {
  533. if (item.priority < lowest_proirity) {
  534. lowest_proirity = item.priority;
  535. result = item;
  536. }
  537. }
  538. // assert(lowest_proirity != std::numeric_limits<int>::max());
  539. // std::cout<<":LK:L "<<result.key<<" "<<result.priority<<std::endl;
  540. // std::cout<<"LKL "<<values_.size()<<std::endl;
  541. auto it = std::find(values_.begin(), values_.end(), result);
  542. assert(it != values_.end());
  543.  
  544. // std::cout<<":LK:L "<<it - values_.begin()<<std::endl;
  545. values_.erase(it);
  546. // std::cout<<"LKL0 "<<values_.size()<<std::endl;
  547.  
  548. return result;
  549. }
  550.  
  551. void DecreasePriority(const HeapItem& item) {
  552. for (auto& val : values_) {
  553. if (item.key == val.key) {
  554. val.priority = item.priority;
  555. }
  556. }
  557. }
  558.  
  559. bool Empty() const {
  560. return values_.empty();
  561. }
  562.  
  563. private:
  564. std::vector<HeapItem> values_;
  565. };
  566.  
  567. std::vector<int> Dijkstra(int vertex_number, int source,
  568. const std::vector<std::vector<Edge>>& edges) {
  569. // std::cout<<":LK:LK :1"<<std::endl;
  570. // PriorityQueue queue;
  571. Heap<HeapItem> heap(false);
  572. std::vector<int> distances(vertex_number, std::numeric_limits<int>::max());
  573. distances.at(source) = 0;
  574.  
  575. heap.Add({source, 0});
  576. for (int i = 0; i < vertex_number; ++i) {
  577. // queue.AddItem({i, distances.at(i)});
  578. // heap.Add({i, distances.at(i)});
  579. }
  580. // std::cout<<":LK:LK :10"<<std::endl;
  581.  
  582. std::unordered_set<int> all_vertices;
  583. while (!heap.Empty()) {
  584. auto item = heap.ExtractMin();
  585. for (const auto& neighbor : edges.at(item.key)) {
  586. if (item.priority == std::numeric_limits<int>::max()) {
  587. continue;
  588. }
  589. int current_dist = item.priority + neighbor.weight;
  590. if (current_dist < distances.at(neighbor.to - 1)) {
  591. distances.at(neighbor.to - 1) = current_dist;
  592. heap.DecreasePriority({neighbor.to - 1, current_dist});
  593. }
  594. }
  595. }
  596. return distances;
  597. }
  598.  
  599. std::vector<int> Solve(int vertex_number, const std::vector<Edge>& edges,
  600. const std::vector<Querry>& querries) {
  601. Graph graph(vertex_number);
  602. for (const auto& item : edges) {
  603. graph.AddEdge(item.from - 1, item.to - 1, item.weight);
  604. }
  605. std::vector<std::vector<int>> querries_sorted(vertex_number);
  606. for (size_t i = 0; i < querries.size(); ++i) {
  607. querries_sorted.at(querries.at(i).from - 1).push_back(i);
  608. }
  609.  
  610. std::vector<int> result_second(querries.size());
  611. uint64_t total_time = 0;
  612. for (int i = 0; i < vertex_number; ++i) {
  613. auto row = graph.Dijkstra(i, querries, querries_sorted.at(i));
  614. for (const auto& ind : querries_sorted.at(i)) {
  615. if (row.at(querries.at(ind).to - 1) == std::numeric_limits<int>::max()) {
  616. result_second[ind] = -1;
  617. } else {
  618. result_second[ind] = row.at(querries.at(ind).to - 1);
  619. }
  620. }
  621. }
  622. total_time/=1000;
  623. // std::cout<<":LK:LK:L "<<total_time<<std::endl;
  624. return result_second;
  625. }
  626.  
  627.  
  628. std::vector<int> SolveThi(int vertex_number, const std::vector<Edge>& edges,
  629. const std::vector<Querry>& querries) {
  630.  
  631. std::vector<std::vector<Edge>> edges_sorted(vertex_number);
  632. for (const auto& item : edges) {
  633. edges_sorted.at(item.from - 1).push_back(item);
  634. }
  635. std::vector<std::vector<int>> querries_sorted(vertex_number);
  636. for (size_t i = 0; i < querries.size(); ++i) {
  637. querries_sorted.at(querries.at(i).from - 1).push_back(i);
  638. }
  639.  
  640. std::vector<int> result_second(querries.size());
  641. uint64_t total_time = 0;
  642. for (int i = 0; i < vertex_number; ++i) {
  643. auto row = Dijkstra(vertex_number, i, edges_sorted);
  644. for (const auto& ind : querries_sorted.at(i)) {
  645. if (row.at(querries.at(ind).to - 1) == std::numeric_limits<int>::max()) {
  646. result_second[ind] = -1;
  647. } else {
  648. result_second[ind] = row.at(querries.at(ind).to - 1);
  649. }
  650. }
  651. }
  652. total_time/=1000;
  653. // std::cout<<":LK:LK:L "<<total_time<<std::endl;
  654. return result_second;
  655. }
  656.  
  657. void StressTest() {
  658. {
  659. std::mt19937 generator(72874);
  660.  
  661. for (size_t loop_index = 0; loop_index < 10000; ++loop_index) {
  662. // std::cout<<loop_index<<std::endl;
  663. int vertex_number = 20;
  664. auto edges = GenerateRandomGraph(&generator, vertex_number,
  665. 2 * vertex_number, true);
  666. int querry_size = 100;
  667. auto from = GenRandomArray(&generator, querry_size, 1, vertex_number);
  668. auto to = GenRandomArray(&generator, querry_size, 1, vertex_number);
  669.  
  670. std::vector<Querry> querries(querry_size);
  671. for (int i = 0; i < querry_size; ++i) {
  672. querries[i].from = from.at(i);
  673. querries[i].to = to.at(i);
  674. }
  675.  
  676. auto result = Solve(vertex_number, edges, querries);
  677. auto true_result = SolveSimple(vertex_number, edges, querries);
  678. if (true_result != result) {
  679. throw std::runtime_error("Stress test failed");
  680. }
  681. }
  682.  
  683. std::cout << "STRESS TEST OK" << std::endl;
  684. }
  685. }
  686.  
  687. void SpeedTest() {
  688. {
  689. std::mt19937 generator(72874);
  690.  
  691. for (size_t loop_index = 0; loop_index < 100; ++loop_index) {
  692. int vertex_number = 2000;
  693. auto edges = GenerateRandomGraph(&generator, vertex_number, 20000, true);
  694. int querry_size = 10000;
  695. auto from = GenRandomArray(&generator, querry_size, 1, vertex_number);
  696. auto to = GenRandomArray(&generator, querry_size, 1, vertex_number);
  697.  
  698. std::vector<Querry> querries(querry_size);
  699. for (int i = 0; i < querry_size; ++i) {
  700. querries[i].from = from.at(i);
  701. querries[i].to = to.at(i);
  702. }
  703.  
  704. TimeMeasure<std::chrono::milliseconds> timer;
  705. Solve(vertex_number, edges, querries);
  706.  
  707. std::cout << "TIME DIFF " << timer.GetTime() << std::endl;
  708. }
  709. }
  710. }
  711.  
  712. void TestSolution() {
  713. {
  714. int vertex_number = 1;
  715. std::vector<Edge> edges;
  716. edges.push_back({1, 1, 1});
  717. std::vector<Querry> querry;
  718. querry.push_back({1, 1});
  719. auto result = Solve(vertex_number, edges, querry);
  720. std::vector<int> true_result;
  721. true_result.push_back(0);
  722. if (result != true_result) {
  723. throw std::runtime_error("TEST FAILED 1");
  724. }
  725. }
  726.  
  727. {
  728. int vertex_number = 5;
  729. std::vector<Edge> edges;
  730. edges.push_back({1, 2, 2});
  731. edges.push_back({2, 3, 0});
  732. edges.push_back({2, 4, 2});
  733. edges.push_back({3, 4, 1});
  734.  
  735. std::vector<Querry> querry;
  736. querry.push_back({1, 4});
  737. querry.push_back({2, 5});
  738.  
  739. auto result = Solve(vertex_number, edges, querry);
  740. std::vector<int> true_result;
  741. true_result.push_back(3);
  742. true_result.push_back(-1);
  743.  
  744. if (result != true_result) {
  745. throw std::runtime_error("TEST FAILED 2");
  746. }
  747. }
  748.  
  749. std::cout << "TESTS OK " << std::endl;
  750. }
  751.  
  752. int main() {
  753. TestSolution();
  754. StressTest();
  755. SpeedTest();
  756. return 0;
  757. std::ios_base::sync_with_stdio(false);
  758. std::cin.tie(nullptr);
  759. int vertex_number;
  760. int edge_number;
  761. std::cin >> vertex_number >> edge_number;
  762. std::vector<Edge> edges(edge_number);
  763. for (auto& edge : edges) {
  764. std::cin >> edge.from >> edge.to >> edge.weight;
  765. }
  766. int querry_number;
  767. std::cin >> querry_number;
  768. std::vector<Querry> querries(querry_number);
  769. for (auto& item : querries) {
  770. std::cin >> item.from >> item.to;
  771. }
  772. auto result = Solve(vertex_number, edges, querries);
  773. for (const auto& item : result) {
  774. std::cout << item << "\n";
  775. }
  776. }
RAW Paste Data