fork download
copy 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. const int N = 255;   
  12.  
  13. int n, m, s, t;   
  14. vector<int> adj[N]; 
  15.  
  16. // Nếu lưu đỉnh ở dạng (u, v) thì chi phí duyệt cạnh để chuyển sang (nxt_u, nxt_v) khá lớn. ~ O(n^4)
  17. // Nên ta sẽ thêm chiều turn, (u, v, turn): sếp 1 đang ở đỉnh u, sếp 2 đang ở đỉnh v, và ở lượt này sếp 1 hay sếp 2 sẽ đi (turn = 0/1)
  18. // Số đỉnh tăng lên nhưng đổi lại thì chi phí duyệt cạnh (hay số cạnh) sẽ ít hơn. ~ O(n^3)
  19.  
  20. struct Node {
  21. 	int u, v; 
  22. 	bool turn; 
  23. };
  24.  
  25. bool vis[N][N][2]; 
  26. int dist[N][N][2];
  27.  
  28. int bfs(int s, int t) {
  29. 	memset(vis, 0, sizeof vis);  
  30. 	memset(dist, -1, sizeof dist); 
  31.  
  32. 	queue<Node> q; 
  33. 	vis[s][t][0] = true;  
  34. 	dist[s][t][0] = 0; 
  35. 	q.push({s, t, 0});   
  36.  
  37. 	while (!q.empty()) {
  38. 		Node front = q.front(); q.pop();  
  39. 		int u = front.u, v = front.v; bool turn = front.turn;  
  40. 		int d = dist[u][v][turn];   
  41.  
  42. 		if (u == v && turn == 0) {
  43. 			return d / 2;
  44. 		}
  45.  
  46. 		if (turn == 0) {
  47. 			for (int nxt_u : adj[u]) {
  48. 				if (!vis[nxt_u][v][1]) {
  49. 					vis[nxt_u][v][1] = true; 
  50. 					dist[nxt_u][v][1] = d + 1;  
  51. 					q.push({nxt_u, v, 1}); 
  52. 				}
  53. 			}
  54. 		}
  55. 		else {
  56. 			for (int nxt_v : adj[v]) {
  57. 				if (!vis[u][nxt_v][0]) {
  58. 					vis[u][nxt_v][0] = true;  
  59. 					dist[u][nxt_v][0] = d + 1;  
  60. 					q.push({u, nxt_v, 0}); 
  61. 				}
  62. 			}
  63. 		}
  64. 	}
  65.  
  66. 	return -1; 
  67. }
  68.  
  69. int main() {
  70. 	ios::sync_with_stdio(false); 
  71. 	cin.tie(nullptr); 	
  72. 	cin >> n >> m; 
  73. 	cin >> s >> t; 
  74.  
  75. 	for (int i = 0; i < m; i++) {
  76. 		int u, v; 
  77. 		cin >> u >> v; 
  78. 		adj[u].push_back(v); 
  79. 	}
  80.  
  81. 	int ans = bfs(s, t); 
  82.  
  83. 	cout << ans << '\n'; 
  84. }
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
6 7
1 5
1 2
4 5
2 3
3 4
4 1
5 4
5 6
stdout
copy 
3
https://ideone.com/HmCpQG
language:
C++14 (gcc 8.3)
created:
291 days ago
visibility:
secret

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!