fork(2) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define FOR(i,a,b) for(int i = (a); i <= (b); ++i)
  4. #define FORD(i,a,b) for(int i = (a); i >= (b); --i)
  5. #define RI(i,n) FOR(i,1,(n))
  6. #define REP(i,n) FOR(i,0,(n)-1)
  7. #define mini(a,b) a=min(a,b)
  8. #define maxi(a,b) a=max(a,b)
  9. #define mp make_pair
  10. #define pb push_back
  11. #define st first
  12. #define nd second
  13. #define sz(w) (int) w.size()
  14. typedef vector<int> vi;
  15. typedef long long ll;
  16. typedef long double ld;
  17. typedef pair<int,int> pii;
  18. const int inf = 1e9 + 5;
  19. const int nax = 1e6 + 5;
  20.  
  21. vector<pii> w[nax];
  22. bool vis[nax];
  23.  
  24. void dfs(int a, int answer) {
  25. 	vis[a] = true;
  26. 	for(pii edge : w[a]) {
  27. 		int b = edge.first;
  28. 		if(vis[b]) continue;
  29. 		int cost = edge.second;
  30. 		if((answer | cost) == answer)
  31. 			dfs(b, answer);
  32. 	}
  33. }
  34.  
  35. bool are_connected(int a, int b, int answer, int n) {
  36. 	RI(i, n) vis[i] = false;
  37. 	dfs(a, answer);
  38. 	return vis[b];
  39. }
  40.  
  41. int main() {
  42. 	int n, m;
  43. 	scanf("%d%d", &n, &m);
  44. 	REP(_, m) {
  45. 		int a, b, c;
  46. 		scanf("%d%d%d", &a, &b, &c);
  47. 		w[a].pb(mp(b,c));
  48. 		w[b].pb(mp(a,c));
  49. 	}
  50. 	int x, y;
  51. 	scanf("%d%d", &x, &y);
  52. 	const int K = 10; // the maximum number of bits
  53. 	int answer = (1 << K) - 1; // 1023
  54. 	if(!are_connected(x, y, answer, n)) {
  55. 		puts("-1");
  56. 		return 0;
  57. 	}
  58. 	for(int i = K - 1; i >= 0; --i)
  59. 		if(are_connected(x, y, answer - (1 << i), n))
  60. 			answer -= 1 << i;
  61. 	printf("%d\n", answer);
  62. 	return 0;
  63. }
  64.  
Runtime error #stdin #stdout 0.01s 16152KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Bv0eHj
Hackerrank, 101 Hack Feb, Minimum Penalty Path (min or)
language:
C++14 (gcc 8.3)
created:
8 years 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!