Submission #38801254

---

Source Code Expand

//#include "bits/stdc++.h"

#define _USE_MATH_DEFINES

#include <iostream>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <functional>
#include <utility>
#include <tuple>
#include <vector>
#include <string>
#include <list>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <queue>
#include <deque>
#include <stack>
#include <iterator>
#include <bitset>
#include <complex>
#include <limits>
#include <random>
#include<fstream>
#include<array>
#include<assert.h>


using namespace std;

#define rep(i,a,b) for(int i=(a), i##_len=(b);i<i##_len;i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)

#define int ll
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<double, double> pdd;
typedef vector< vector<int> > mat;

template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return true; } return false; }

const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
//const int MOD =  (int)1e9 + 7;
const int MOD = 998244353;

const double EPS = 1e-9;

struct P
{
	int l, r, c;
	P(int l = 0, int r = 0, int c = 0) :l(l), r(r), c(c) {}
	bool operator<(const P& other)const
	{
		return c > other.c;
	}
};

signed main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);

	int T;
	cin >> T;

	while (T--)
	{
		int N, M;
		cin >> N >> M;

		vector<int> C(N);
		rep(i, 0, N)cin >> C[i];

		vector<vector<int>> G(N);
		rep(i, 0, M)
		{
			int u, v;
			cin >> u >> v;
			u--, v--;
			G[u].push_back(v);
			G[v].push_back(u);
		}

		vector<vector<int>> DP(N, vector<int>(N, INF));
		DP[0][N - 1] = 0;
		priority_queue<P> pq;
		pq.push(P(0, N - 1, 0));

		while (!pq.empty())
		{
			auto p = pq.top();
			pq.pop();
			if (DP[p.l][p.r] < p.c)continue;
			for (auto le : G[p.l])for (auto re : G[p.r])
			{
				if (C[le] ^ C[re] == 0)continue;
				if (chmin(DP[le][re], p.c + 1))
				{
					pq.push(P(le, re, DP[le][re]));
				}
			}
		}

		if (DP[N - 1][0] == INF)cout << -1 << endl;
		else cout << DP[N - 1][0] << endl;
	}

	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:113:23: warning: suggest parentheses around comparison in operand of ‘^’ [-Wparentheses]
  113 |     if (C[le] ^ C[re] == 0)continue;

Judge Result