Submission #82367

#	Time	Username	Problem	Language	Result	Execution time	Memory
82367		combi1k1	007 (CEOI14_007)	C++14	0 / 100	229 ms	15884 KiB

007

#pragma GCC optimize "-O3"
#include<bits/stdc++.h>

using namespace std;

#define pb  push_back

int read()  {
	char c = getchar();
	int res = 0;
	while (c < '0' || c > '9')  c = getchar();
	while (48 <= c && c <= 57)  {
		res = res * 10 + c - '0';
		c = getchar();
	}
	return res;
}

const int   N   = 2e5 + 1;

vector<int> g[N];

int n, m;
int X, S, A, B;
int d[N];

int  bfs(int s) {
	queue<int>  q;
	for(int i = 1 ; i <= n ; ++i)
		d[i] = N;
	d[s] = 0;   q.push(s);
	
	while(q.size()) {
		int u = q.front();  q.pop();
		for(int v : g[u])
			if (d[v] > d[u] + 1)    {
				d[v] = d[u] + 1;
				q.push(v);
			}
	}
	
	if (d[X] > d[S])    {
		puts("-1");
		exit(0);
	}
	
	return d[S] - d[X];
}

int main()  {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	//freopen("SPY.inp","r",stdin);
	//freopen("SPY.out","w",stdout);
	
	n = read(); m = read();
	X = read(); S = read();
	A = read(); B = read();
	
	while(m--)  {
		int x = read();
		int y = read();
		g[x].pb(y);
		g[y].pb(x);
	}
	
	cout << min(bfs(A),bfs(B));
}

• Subtask 1: 0 / 30
• Subtask 2: 0 / 70