fork download 
  1. /*#include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <vector>
  5. #include <map>
  6. #include <set>
  7. #include <stack>
  8. #include <queue>
  9. #include <cmath>
  10. #include <algorithm>
  11.  */
  12. #include <bits/stdc++.h>
  13. using namespace std;
  14.  
  15. typedef long long ll;
  16. typedef vector<int> vi;
  17. typedef pair<int, int> ii;
  18. typedef vector<ii> vii;
  19. typedef set<int> si;
  20. typedef map<string, int> msi;
  21. typedef stack<long long> ss;
  22. #define get(a) #a
  23.  
  24. //#define DEBUG
  25. //#define local
  26.  
  27. #define endl '\n'
  28.  
  29. #ifdef DEBUG
  30.  
  31. #define debug(args...) {dbg,args; cerr<<endl;}
  32.  
  33. #else
  34.  
  35. #define debug(args...) // Just strip off all debug tokens
  36.  
  37. #endif
  38.  
  39. struct debugger
  40.  
  41. {
  42.  
  43. template<typename T> debugger& operator , (const T& v)
  44.  
  45. {
  46.  
  47. cerr<<v<<" ";
  48.  
  49. return *this;
  50.  
  51. }
  52.  
  53. } dbg;
  54.  
  55. #define INF 1000000000
  56. int main(){
  57. 	std::ios::sync_with_stdio(false);
  58. 	#ifdef local
  59. 		freopen("in.txt","r",stdin);
  60. 	#endif
  61.  
  62. 	int n,m;
  63. 	cin>>n>>m;
  64.  
  65. 	int min_sum = INF;
  66.  
  67. 	vector< vector<int> > arr;
  68. 	vector< pair<int,int> > p;
  69. 	for(int i = 0;i < n;i++){
  70. 		vector<int> q(m,0);
  71. 		arr.push_back(q);
  72. 	}
  73.  
  74.  
  75. 	int a,b,c;
  76. 	for (int i = 0; i < m; ++i)
  77. 	{
  78. 		cin>>a>>b;
  79.  
  80. 		a--;
  81. 		b--;
  82. 		arr[a][b] = 1;
  83. 		arr[b][a] = 1;
  84. 		p.push_back(make_pair(a,b));
  85. 	}
  86.  
  87.  
  88. 	vector<vector<int> > v;
  89.  
  90. 	int sum[n];
  91.  
  92. 	for(int i = 0;i < n;i++){
  93. 		int sums = 0;
  94. 		vector<int> q;
  95. 		//q.push_back(-1);
  96. 		for(int j = 0;j < m;j++){
  97. 			sums += arr[i][j];
  98. 			if(arr[i][j])
  99. 				q.push_back(j);
  100. 		}
  101. 		v.push_back(q);
  102. 		sum[i] = sums;
  103. 	}	
  104.  
  105. 	arr.clear();
  106. 	vector<int>::iterator it;
  107. 	for(int i = 0;i < p.size();i++){
  108. 		a = p[i].first;
  109. 		b = p[i].second;
  110. 		for(int j = i+1;j < p.size();j++){
  111. 			if(p[j].first == a){
  112. 				if(v[b].size() > 0){
  113. 					it = lower_bound(v[b].begin(),v[b].end(),p[j].second);
  114. 					if(*it == p[j].second){
  115. 						//cout<<a<<" "<<b<<" "<<p[j].second<<endl;
  116. 						min_sum = min(min_sum,sum[a] + sum[b] + sum[p[j].second] - 6);
  117. 					}
  118. 				}
  119. 			}
  120. 			if(p[j].second == a){
  121. 				if(v[b].size() > 0){
  122. 					it = lower_bound(v[b].begin(),v[b].end(),p[j].first);
  123. 					if(*it == p[j].first){
  124. 						//cout<<a<<" "<<b<<" "<<p[j].first<<" minsum = "<<min_sum<<endl;
  125. 						min_sum = min(min_sum,sum[a] + sum[b] + sum[p[j].first] - 6);
  126. 					}
  127. 				}
  128. 			}
  129. 		}
  130. 	}
  131.  
  132. 	if(min_sum == INF){
  133. 		cout<<"-1\n";
  134. 	}
  135. 	else{
  136. 		cout<<min_sum<<endl;
  137. 	}
  138.  
  139. }
Success #stdin #stdout 0s 3412KB
comments (?)
stdin 
3 2
2 3
2 1
stdout 
-1
https://ideone.com/JTSkfy
language:
C++14 (gcc 8.3)
created:
9 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!