oj.uz

답안 #680704

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
680704 2023-01-11T14:49:27 Z SanguineChameleon Relay Marathon (NOI20_relaymarathon) C++17
25 / 100
 1408 ms 94412 KB 
// BEGIN BOILERPLATE CODE

#include <bits/stdc++.h>
using namespace std;

#ifdef KAMIRULEZ
	const bool kami_loc = true;
	const long long kami_seed = 69420;
#else
	const bool kami_loc = false;
	const long long kami_seed = chrono::steady_clock::now().time_since_epoch().count();
#endif

const string kami_fi = "kamirulez.inp";
const string kami_fo = "kamirulez.out";
mt19937_64 kami_gen(kami_seed);

long long rand_range(long long rmin, long long rmax) {
	uniform_int_distribution<long long> rdist(rmin, rmax);
	return rdist(kami_gen);
}

long double rand_real(long double rmin, long double rmax) {
	uniform_real_distribution<long double> rdist(rmin, rmax);
	return rdist(kami_gen);
}

void file_io(string fi, string fo) {
	if (fi != "" && (!kami_loc || fi == kami_fi)) {
		freopen(fi.c_str(), "r", stdin);
	}
	if (fo != "" && (!kami_loc || fo == kami_fo)) {
		freopen(fo.c_str(), "w", stdout);
	}
}

void set_up() {
	if (kami_loc) {
		file_io(kami_fi, kami_fo);
	}
	ios_base::sync_with_stdio(0);
	cin.tie(0);
}

void just_do_it();

void just_exec_it() {
	if (kami_loc) {
		auto pstart = chrono::steady_clock::now();
		just_do_it();
		auto pend = chrono::steady_clock::now();
		long long ptime = chrono::duration_cast<chrono::milliseconds>(pend - pstart).count();
		string bar(50, '=');
		cout << '\n' << bar << '\n';
		cout << "Time: " << ptime << " ms" << '\n';
	}
	else {
		just_do_it();
	}
}

int main() {
	set_up();
	just_exec_it();
	return 0;
}

// END BOILERPLATE CODE

// BEGIN MAIN CODE

const int ms = 1e5 + 20;
const int inf = 1e9 + 20;
vector<pair<int, int>> adj[ms];
int ds[ms];
int du[ms];
int dv[ms];
int h[ms];
int g[ms];
bool f[ms];
int n;

void dijk(int d[]) {
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
	for (int i = 1; i <= n; i++) {
		if (d[i] == 0) {
			h[i] = i;
			q.push({0, i});
		}
	}
	while (!q.empty()) {
		int cd = q.top().first;
		int u = q.top().second;
		q.pop();
		if (d[u] != cd) {
			continue;
		}
		for (auto x: adj[u]) {
			int v = x.first;
			if (f[v]) {
				continue;
			}
			int w = x.second;
			if (d[u] + w < d[v]) {
				d[v] = d[u] + w;
				h[v] = h[u];
				q.push({d[v], v});
			}
		}
	}
}

bool cmp(int u, int v) {
	return dv[u] < dv[v];
}

void just_do_it() {
	//file_io("4special.inp", "4special.out");
	int m, k;
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++) {
		ds[i] = inf;
		du[i] = inf;
		dv[i] = inf;
	}
	for (int i = 0; i < m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
	}
	for (int i = 0; i < k; i++) {
		int u;
		cin >> u;
		g[i] = u;
		ds[u] = 0;
	}
	dijk(ds);
	int mi = inf;
	int fu = -1;
	int fv = -1;
	for (int i = 1; i <= n; i++) {
		for (auto x: adj[i]) {
			int j = x.first;
			int w = x.second;
			if (h[i] != h[j]) {
				if (ds[i] + ds[j] + w < mi) {
					mi = ds[i] + ds[j] + w;
					fu = h[i];
					fv = h[j];
				}
			}
		}
	}
	du[fu] = 0;
	dijk(du);
	dv[fv] = 0;
	dijk(dv);
	sort(g, g + k, cmp);
	int res = inf;
	for (int i = 0; i < k; i++) {
		if (g[i] == fu || g[i] == fv) {
			continue;
		}
		for (int j = 0; j < k; j++) {
			if (g[j] != g[i] && g[j] != fu && g[j] != fv) {
				res = min(res, mi + du[g[i]] + dv[g[j]]);
				break;
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		ds[i] = inf;
	}
	for (int i = 0; i < k; i++) {
		ds[g[i]] = 0;
	}
	ds[fu] = inf;
	ds[fv] = inf;
	f[fu] = true;
	f[fv] = true;
	dijk(ds);
	for (int i = 1; i <= n; i++) {
		for (auto x: adj[i]) {
			int j = x.first;
			int w = x.second;
			if (h[i] != h[j]) {
				res = min(res, mi + ds[i] + ds[j] + w);
			}
		}
	}
	cout << res;
}

// END MAIN CODE

Compilation message

RelayMarathon.cpp: In function 'void file_io(std::string, std::string)':
RelayMarathon.cpp:30:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |   freopen(fi.c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
RelayMarathon.cpp:33:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |   freopen(fo.c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 53 ms 8052 KB Output is correct
2 Correct 6 ms 4548 KB Output is correct
3 Correct 1292 ms 85272 KB Output is correct
4 Correct 558 ms 48472 KB Output is correct
5 Correct 145 ms 13232 KB Output is correct
6 Correct 131 ms 11224 KB Output is correct
7 Correct 156 ms 14156 KB Output is correct
8 Correct 70 ms 8128 KB Output is correct
9 Correct 99 ms 10616 KB Output is correct
10 Correct 81 ms 8928 KB Output is correct
11 Correct 1296 ms 89812 KB Output is correct
12 Correct 83 ms 9296 KB Output is correct
13 Correct 349 ms 31400 KB Output is correct
14 Correct 165 ms 14300 KB Output is correct
15 Correct 1246 ms 88216 KB Output is correct
16 Correct 55 ms 7644 KB Output is correct
17 Correct 859 ms 75228 KB Output is correct
18 Correct 9 ms 4692 KB Output is correct
19 Correct 1408 ms 94412 KB Output is correct
20 Correct 152 ms 13640 KB Output is correct
21 Correct 151 ms 12568 KB Output is correct
22 Correct 75 ms 8780 KB Output is correct
23 Correct 20 ms 6692 KB Output is correct
24 Correct 942 ms 82656 KB Output is correct
25 Correct 107 ms 10816 KB Output is correct
26 Correct 54 ms 8128 KB Output is correct
27 Correct 106 ms 9688 KB Output is correct
28 Correct 12 ms 5716 KB Output is correct
29 Correct 162 ms 13916 KB Output is correct
30 Correct 348 ms 24436 KB Output is correct

Subtask #4
0 / 58.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -