fork(1) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <string.h>
  5. #include <deque>
  6. using namespace std;
  7.  
  8. vector<pair<int,int>> tree[10000];
  9. int path[10000][501];
  10. char tr[10000];
  11.  
  12. struct vert{
  13. 	int value;
  14. 	int ver;
  15. 	int cruel;
  16. 	vert(int a,int b, int c):value(a),ver(b),cruel(c){}
  17. 	const bool operator < (const vert& x) const{
  18. 		return value < x.value;
  19. 	}
  20. };
  21.  
  22.  
  23. int main() {
  24. 	// your code goes here
  25. 	int K,N,M,S,F;
  26. 	cin >> K >> N >> M >> S >> F;
  27. 	S--;
  28. 	F--;
  29. 	for (int i=0; i < M; i++){
  30. 		int u,v,l;
  31. 		u = i+1;
  32. 		v = (i+1)%N+1;
  33. 		l = i%500 + 1;
  34. 		//cin >> u >> v >> l;
  35. 		u--;
  36. 		v--;
  37. 		if (l <= K){
  38. 			tree[u].push_back( make_pair(v,l) );
  39. 			tree[v].push_back( make_pair(u,l) );
  40. 		}
  41. 	}
  42. 	int Q;
  43. 	cin >> Q;
  44. 	for (int i=0; i < Q; i++){
  45. 		int a;
  46. 		a = i+1;
  47. 		//cin >> a;
  48. 		tr[a-1] = 1;
  49. 	}
  50. 	memset(path, 0x7F , sizeof(path));
  51. 	path[S][K] = 0;
  52. 	deque<vert> Queue;
  53. 	//priority_queue<vert> Queue;
  54. 	Queue.push_front(vert(0,S,K));
  55. 	while (!Queue.empty()){
  56. 		vert cur = Queue.front();
  57. 		//cout << "? "<<cur.value<<" "<<cur.ver<<" "<<cur.cruel<<endl;
  58. 		Queue.pop_front();
  59. 		//if (cur.value != path[cur.ver][cur.cruel])
  60. 		//	continue;
  61. 		for (auto z : tree[cur.ver]){
  62. 			if (z.second <= cur.cruel)
  63. 				if (path[z.first][cur.cruel - z.second] > cur.value){
  64. 					path[z.first][cur.cruel - z.second] = cur.value;
  65. 					//cout << "+ "<<cur.value<<" "<<z.first<<" "<<cur.cruel - z.second<<endl;
  66. 					Queue.push_front( vert(cur.value, z.first, cur.cruel - z.second) );
  67. 					//for (int b=cur.cruel - z.second; b >=0; b--)
  68. 					//	path[z.first][b] = min(path[z.first][b], cur.value);
  69. 				}
  70. 			if (tr[cur.ver])
  71. 				if (path[z.first][K - z.second] > cur.value + 1){
  72. 					path[z.first][K - z.second] = cur.value + 1;
  73. 					//cout << "+ "<<cur.value+1<<" "<<z.first<<" "<<K - z.second<<endl;
  74. 					Queue.push_back( vert(cur.value+1, z.first, K - z.second) );
  75. 					//for (int b=K - z.second; b >=0; b--)
  76. 					//	path[z.first][b] = min(path[z.first][b], cur.value+1);
  77. 				}				
  78. 		}
  79. 	}
  80. 	int res = 0x7F7F7F7F;
  81. 	for (int i=0; i <= K; i++)
  82. 		res = min(res, path[F][i] );
  83. 	if (res == 0x7F7F7F7F)
  84. 		res = -1;
  85. 	cout << res;
  86. 	return 0;
  87. }
Success #stdin #stdout 0.02s 23568KB
comments (?)
stdin
copy 
500 10000 10000 1 5000
10000
stdout
copy 
3228
https://ideone.com/hYkXHN
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!