Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <queue>
- #include <vector>
- #include <climits>
- using namespace std;
- struct prots{
- int ans, data, st;
- vector <int> prev;
- };
- int main()
- {
- prots temp1, p;
- vector <vector <int> > dp;
- vector <int> a, ans;
- queue <prots> q;
- int n, m;
- cin >> n >> m;
- a.reserve(n + 1);
- a.resize(n + 1);
- dp.reserve(n + 1);
- ans.reserve(n + 1);
- ans.resize(n + 1);
- dp.resize(n + 1);
- for (int i = 1; i <= n; i++){
- cin >> a[i];
- ans[i] = INT_MAX - 20;
- if (a[i] != 0){
- temp1.data = i;
- temp1.st = i;
- temp1.prev.push_back(i);
- temp1.ans = 0;
- q.push(temp1);
- }
- }
- int x, y;
- for (int i = 1; i <= m; i++){
- cin >> x >> y;
- dp[x].push_back(y);
- dp[y].push_back(x);
- }
- int data1;
- bool bol;
- while (!q.empty()){
- p = q.front();
- q.pop();
- for (int i = 0; i < dp[p.data].size(); i++){
- data1 = dp[p.data][i];
- bol = true;
- for (int j = 0; j < p.prev.size(); j++)
- if (data1 == p.prev[j])
- bol = false;
- if (bol){
- if (a[data1] == 0){
- temp1.data = data1;
- temp1.st = p.st;
- temp1.prev = p.prev;
- temp1.prev.push_back(data1);
- temp1.ans = p.ans + 1;
- q.push(temp1);
- }
- else
- if (a[data1] != a[p.st]){
- ans[data1] = min(ans[data1], p.ans + 1);
- ans[p.st] = min(ans[p.st], ans[data1]);
- }
- }
- }
- }
- int min2 = ans[1];
- for (int i = 2; i <= n; i++)
- if (ans[i] < min2)
- min2 = ans[i];
- cout << min2 << "\n";
- return 0;
- }
- /*16 24
- 2 0 0 0 0 0 0 4 0 1 0 0 0 0 0 0
- 1 2
- 1 3
- 1 4
- 1 7
- 2 4
- 2 7
- 2 5
- 2 6
- 3 4
- 4 7
- 5 8
- 5 9
- 5 10
- 5 11
- 6 12
- 6 13
- 6 14
- 6 15
- 6 16
- 12 5
- 13 5
- 14 5
- 15 5
- 16 5*/
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement