Submission #101141

#	Time	Username	Problem	Language	Result	Execution time	Memory
101141		E869120	007 (CEOI14_007)	C++14	30 / 100	391 ms	21640 KiB

007

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
#pragma warning (disable: 4996)

int N, M, p, q, a, b, dist1[1 << 18], dist2[1 << 18], dista[1 << 18], dist[1 << 18];
vector<int>X[1 << 18];

vector<int> dijkstra(int pos) {
	queue<int>Q;
	for (int i = 1; i <= N; i++) dist[i] = (1 << 30);
	dist[pos] = 0; Q.push(pos);

	while (!Q.empty()) {
		int pos = Q.front(); Q.pop();
		for (int i = 0; i < X[pos].size(); i++) {
			if (dist[X[pos][i]] > dist[pos] + 1) {
				dist[X[pos][i]] = dist[pos] + 1;
				Q.push(X[pos][i]);
			}
		}
	}

	vector<int>vec;
	for (int i = 1; i <= N; i++) vec.push_back(dist[i]);
	return vec;
}

int main() {
	scanf("%d%d", &N, &M);
	scanf("%d%d%d%d", &p, &q, &a, &b);
	for (int i = 1; i <= M; i++) {
		int v1, v2; scanf("%d%d", &v1, &v2);
		X[v1].push_back(v2);
		X[v2].push_back(v1);
	}
	vector<int> V1 = dijkstra(a); for (int i = 0; i < V1.size(); i++) dist1[i + 1] = V1[i];
	vector<int> V2 = dijkstra(b); for (int i = 0; i < V2.size(); i++) dist2[i + 1] = V2[i];
	vector<int> V3 = dijkstra(q); for (int i = 0; i < V3.size(); i++) dista[i + 1] = V3[i];

	int minx = (1 << 30);
	for (int i = 1; i <= N; i++) {
		if (dist1[i] < dist1[p] || dist2[i] < dist2[p]) minx = min(minx, dista[i]);
	}
	cout << max(-1, minx - 2) << endl;
	return 0;
}

Compilation message (stderr)

007.cpp:6:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning (disable: 4996)
 
007.cpp: In function 'std::vector<int> dijkstra(int)':
007.cpp:18:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < X[pos].size(); i++) {
                   ~~^~~~~~~~~~~~~~~
007.cpp: In function 'int main()':
007.cpp:39:50: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  vector<int> V1 = dijkstra(a); for (int i = 0; i < V1.size(); i++) dist1[i + 1] = V1[i];
                                                ~~^~~~~~~~~~~
007.cpp:40:50: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  vector<int> V2 = dijkstra(b); for (int i = 0; i < V2.size(); i++) dist2[i + 1] = V2[i];
                                                ~~^~~~~~~~~~~
007.cpp:41:50: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  vector<int> V3 = dijkstra(q); for (int i = 0; i < V3.size(); i++) dista[i + 1] = V3[i];
                                                ~~^~~~~~~~~~~
007.cpp:32:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~
007.cpp:33:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d", &p, &q, &a, &b);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
007.cpp:35:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int v1, v2; scanf("%d%d", &v1, &v2);
               ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 9 / 30
• Subtask 2: 21 / 70