Submission #101143

#	Time	Username	Problem	Language	Result	Execution time	Memory
101143		E869120	007 (CEOI14_007)	C++14	100 / 100	648 ms	62580 KiB

007

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

long long N, M, p, q, a, b, dist1[1 << 18], dist2[1 << 18], dist3[1 << 18], dist4[1 << 18], dist[1 << 18]; bool used[1 << 18];
vector<int>X[1 << 18]; vector<pair<int, long long>>G[1 << 18];

vector<long long> 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<long long>vec;
	for (int i = 1; i <= N; i++) vec.push_back(dist[i]);
	return vec;
}

vector<long long> dijkstra2(int pos) {
	priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>>Q;
	for (int i = 1; i <= N; i++) dist[i] = (1LL << 60);
	Q.push(make_pair(0, pos)); dist[pos] = 0;

	while (!Q.empty()) {
		int pos = Q.top().second; Q.pop();
		for (int i = 0; i < G[pos].size(); i++) {
			int to = G[pos][i].first; long long cost = G[pos][i].second;
			if (dist[to] > dist[pos] + cost) {
				dist[to] = dist[pos] + cost;
				Q.push(make_pair(dist[to], to));
			}
		}
	}

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

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<long long> V1 = dijkstra(a); for (int i = 0; i < V1.size(); i++) dist1[i + 1] = V1[i];
	vector<long long> V2 = dijkstra(b); for (int i = 0; i < V2.size(); i++) dist2[i + 1] = V2[i];
	vector<long long> V3 = dijkstra(q); for (int i = 0; i < V3.size(); i++) dist3[i + 1] = V3[i];
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j < X[i].size(); j++) {
			long long cost = 1000001;
			if (dist1[X[i][j]] == dist2[X[i][j]]) cost = 1000000;
			G[i].push_back(make_pair(X[i][j], cost));
		}
	}
	vector<long long> V4 = dijkstra2(a); for (int i = 0; i < V1.size(); i++) dist4[i + 1] = V4[i];

	long long minx = (1 << 30);
	for (int i = 1; i <= N; i++) {
		if (dist1[i] < dist1[p] || dist2[i] < dist2[p] || (dist1[i] == dist1[p] && dist1[i] == dist2[i] && dist2[i] == dist2[p] && dist4[i] < dist4[p])) {
			minx = min(minx, dist3[i]);
		}
	}
	cout << minx - 1 << 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<long long 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 'std::vector<long long int> dijkstra2(int)':
007.cpp:38:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < G[pos].size(); i++) {
                   ~~^~~~~~~~~~~~~~~
007.cpp: In function 'int main()':
007.cpp:53:22: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
  scanf("%d%d", &N, &M);
                ~~    ^
007.cpp:53:22: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
007.cpp:54:34: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
  scanf("%d%d%d%d", &p, &q, &a, &b);
                    ~~            ^
007.cpp:54:34: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
007.cpp:54:34: warning: format '%d' expects argument of type 'int*', but argument 4 has type 'long long int*' [-Wformat=]
007.cpp:54:34: warning: format '%d' expects argument of type 'int*', but argument 5 has type 'long long int*' [-Wformat=]
007.cpp:60:56: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  vector<long long> V1 = dijkstra(a); for (int i = 0; i < V1.size(); i++) dist1[i + 1] = V1[i];
                                                      ~~^~~~~~~~~~~
007.cpp:61:56: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  vector<long long> V2 = dijkstra(b); for (int i = 0; i < V2.size(); i++) dist2[i + 1] = V2[i];
                                                      ~~^~~~~~~~~~~
007.cpp:62:56: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  vector<long long> V3 = dijkstra(q); for (int i = 0; i < V3.size(); i++) dist3[i + 1] = V3[i];
                                                      ~~^~~~~~~~~~~
007.cpp:64:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < X[i].size(); j++) {
                   ~~^~~~~~~~~~~~~
007.cpp:70:57: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  vector<long long> V4 = dijkstra2(a); for (int i = 0; i < V1.size(); i++) dist4[i + 1] = V4[i];
                                                       ~~^~~~~~~~~~~
007.cpp:53: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:54: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:56: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: 30 / 30
• Subtask 2: 70 / 70