fork(1) download
copy 
  1. #include <iostream>
  2. #include <tuple>
  3. #include <cstdint>
  4. #include <vector>
  5. #include <memory>
  6. //#include <algorithm>
  7.  
  8. typedef std::tuple<std::uint64_t, std::uint64_t, std::uint64_t> Road;
  9. typedef std::vector<Road> Roads;
  10. typedef std::vector<std::uint64_t> Mountain;
  11. typedef std::tuple<std::uint64_t,std::uint64_t, Mountain, Roads> Input;//money,mountain,roads.
  12. //---
  13.  
  14. typedef std::shared_ptr < std::uint64_t > Cost;
  15. typedef std::tuple<std::uint64_t, Cost> Line;//MovePos,cost
  16.  
  17. struct  Node{
  18. 	std::uint64_t V = 0;
  19. 	std::vector<Line> Road;
  20. };
  21.  
  22. typedef std::vector< Node > Graph;
  23. Input GetInput() {
  24. 	std::uint64_t N = 0;
  25. 	std::uint64_t W = 0;
  26.  
  27. 	Mountain M;
  28.  
  29. 	std::cin >> N;
  30. 	std::cin >> W;
  31.  
  32. 	std::uint64_t T = 0;
  33.  
  34. 	for (std::size_t i = 0; i < N; i++) {
  35. 		std::cin >> T;
  36. 		M.push_back(T);
  37. 	}
  38.  
  39. 	std::uint64_t u = 0;
  40. 	std::uint64_t v = 0;
  41. 	std::uint64_t c = 0;
  42.  
  43. 	Roads R;
  44.  
  45. 	for (std::size_t i = 0; i < N; i++) {
  46. 		std::cin >> u>>v>>c;
  47. 		R.push_back({u,v,c});
  48. 	}
  49.  
  50. 	return { N,W,M,R };
  51. }
  52.  
  53. Graph Converte(const Input& I) {
  54. 	Graph G(std::get<0>(I));
  55.  
  56. 	auto& m = std::get<2>(I);
  57.  
  58. 	for (std::size_t i = 0; i < std::get<0>(I); i++) {
  59. 		G[i].V = m[i];
  60. 	}
  61. 	for (std::size_t i = 0; i < std::get<0>(I)-1; i++) {
  62. 		Cost C = std::make_shared<std::uint64_t>(std::get<2>(std::get<3>(I)[i]));
  63. 		G[std::get<0>(std::get<3>(I)[i]) - 1].Road.push_back({std::get<1>(std::get<3>(I)[i]) - 1, C });
  64. 		G[std::get<1>(std::get<3>(I)[i]) - 1].Road.push_back({std::get<0>(std::get<3>(I)[i]) - 1, C });
  65. 	}
  66.  
  67. 	return G;
  68. }
  69.  
  70. std::uint64_t Solve_rec(Graph G, std::size_t IdxA,std::size_t IdxB, std::size_t Depth,std::int64_t Cost,const std::int64_t& Hand,std::int64_t& Max) {
  71.  
  72. 	if (Cost < 0) return 0;
  73. 	if (Hand < 0) return 0;
  74. 	if (Depth > G.size()*2) return 0;
  75. 	if (Max < Cost) {
  76. 		Max = Cost;
  77. 	}
  78.  
  79. 	for (std::size_t i = IdxB; i < G[IdxA].Road.size(); i++) {
  80. 		std::int64_t MC = *std::get<1>(G[IdxA].Road[i]);
  81. 		if (MC > Hand) continue;
  82.  
  83. 		(*std::get<1>(G[IdxA].Road[i])) = 0;
  84. 		std::int64_t MV = G[IdxA].V;
  85. 		G[IdxA].V = 0;
  86. 		Solve_rec(G, std::get<0>(G[IdxA].Road[i]), 0, Depth + 1, Cost + MV, Hand - MC, Max);
  87. 		(*std::get<1>(G[IdxA].Road[i])) = MC;
  88. 		G[IdxA].V = MV;
  89. 	}
  90.  
  91. 	return 0;
  92. }
  93.  
  94.  
  95. std::uint64_t Solve(Graph G, std::uint64_t Money) {
  96. 	std::int64_t Max = 0;
  97.  
  98. 	for (std::size_t i = 0; i < G.size(); i++) {
  99. 		std::int64_t V = G[i].V;
  100. 		G[i].V = 0;
  101. 		Solve_rec(G, i, 0, 0,V,Money,Max);
  102. 		G[i].V = V;
  103. 	}
  104.  
  105. 	return Max;
  106. }
  107.  
  108.  
  109. int main() {
  110.  
  111. 	Input I = GetInput();
  112.  
  113. 	Graph G = Converte(I);
  114.  
  115.  
  116. 	std::int64_t Max = Solve(G, std::get<1>(I));
  117.  
  118.  
  119. 	std::cout << Max << std::endl;
  120. 	return 0;
  121.  
  122. }
  123.  
  124.  
Success #stdin #stdout 0s 4408KB
comments (?)
stdin
copy 
3 10 6 8 2 1 2 3 2 3 8
stdout
copy 
14
https://ideone.com/K6220K
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!