Submission #14145227

---

Source Code Expand

/* cmd
	g++ "$F"
*/
#include <algorithm>
#include <iostream>
#include <iterator>
#include <queue>
#include <utility>
#include <vector>
using namespace std;

int main()
{
// Inputs
	int N,M; cin >> N >> M;

	vector<vector<int>> E(N+1);
	for (int i = 0; i < M; ++i) {
		int u,v; cin >> u >> v;
		E[u].push_back(v);
		E[v].push_back(u);
	}

	int S,K; cin >> S >> K;

	vector<int> T(K+1);
	for (int i = 0; i < K; ++i) {
		cin >> T[i];
	}
	T[K] = S;

// Prepare
	vector<vector<pair<int,int>>> E2(K+1);
	auto C = [&](int s, int t){
		int cost = 0;
		vector<bool> visited(N+1,false);
		for (int u: T) {
			visited[u] = true;
		}
		visited[t] = false;
		vector<int> q = {s};
		while (! q.empty() && ! visited[t]) {
			vector<int> q2;
			for (int u: q) {
				for (int v: E[u]) {
					if (! visited[v]) {
						visited[v] = true;
						q2.push_back(v);
					}
				}
			}
			q.swap(q2);
			cost += 1;
		}
		return visited[t] ? cost : 1<<30;
	};
	for (int i = 0; i < K; ++i) {
		for (int j = i+1; j < K+1; ++j) {
			int c = C(T[i],T[j]);
			E2[i].emplace_back(j,c);
			E2[j].emplace_back(i,c);
		}
	}

// Run
	const unsigned WOU = (1U<<K+1)-1;
	vector<bool> Visited(1<<K+6,false);
	priority_queue<
		pair<int,unsigned>,
	        vector<pair<int,unsigned>>,
	        greater<pair<int,unsigned>>
	> q;
	q.emplace(0,K<<K+1|1<<K); // S(=T[K])
	while (! q.empty()) {
		if (Visited[q.top().second]) {
			q.pop();
			continue;
		}
		Visited[q.top().second] = true;
		int      c = q.top().first;
		int      u = q.top().second>>K+1;
		unsigned v = q.top().second&WOU;
		q.pop();

		if (v == WOU) {
			cout << c << endl;
			break;
		}

		for (auto p: E2[u]) {
			unsigned v2 = v|p.first<<K+1|1<<p.first;
			if (! Visited[v2]) {
				q.emplace(c+p.second,v2);
			}
		}
	}
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:66:29: warning: suggest parentheses around ‘+’ inside ‘<<’ [-Wparentheses]
   66 |  const unsigned WOU = (1U<<K+1)-1;
      |                            ~^~
./Main.cpp:67:27: warning: suggest parentheses around ‘+’ inside ‘<<’ [-Wparentheses]
   67 |  vector<bool> Visited(1<<K+6,false);
      |                          ~^~
./Main.cpp:73:18: warning: suggest parentheses around ‘+’ inside ‘<<’ [-Wparentheses]
   73 |  q.emplace(0,K<<K+1|1<<K); // S(=T[K])
      |                 ~^~
./Main.cpp:81:33: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   81 |   int      u = q.top().second>>K+1;
      |                                ~^~
./Main.cpp:91:30: warning: suggest parentheses around ‘+’ inside ‘<<’ [-Wparentheses]
   91 |    unsigned v2 = v|p.first<<K+1|1<<p.first;
      |                             ~^~

Judge Result