oj.uz

답안 #475478

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
475478 2021-09-22T15:21:03 Z fredbr Cities (BOI16_cities) C++17
100 / 100
 2357 ms 33844 KB 
#include <bits/stdc++.h>

#define ff first
#define ss second

#define pb push_back
#define eb emplace_back
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define clr(x, c) memset((x), (c), sizeof((x)))

using namespace std;

template<class T> void DBG(T&& x) { cerr << x << " "; }
template<class T, class...Args> void DBG(T&& x, Args&&... args) { DBG(x); DBG(args...); }
#define DBG(...) do {cerr << "[" << #__VA_ARGS__ << "]: "; DBG(__VA_ARGS__); cerr << endl; } while (0) 

#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif

template<class num> inline void rd(num& x) {
	char c, neg = 0; while(isspace(c = getchar_unlocked()));
	if(!isdigit(c)) neg = (c == '-'), x = 0;
	else x = c - '0';
	while(isdigit(c = getchar_unlocked())) x = (x << 3) + (x << 1) + c - '0';
	x = neg ? -x : x; }
template <class Ty, class... Args> inline void rd(Ty& x, Args&... args) { rd(x); rd(args...); }


using ll = long long;
using ii = pair<ll, ll>;

using Gr = vector<vector<ii>>;

template<typename T = int>
constexpr T inf = 0x3f3f3f3f;

template<>
constexpr ll inf<ll> = 0x3f3f3f3f3f3f3f3f;

seed_seq seq {
    (uint64_t) chrono::duration_cast<chrono::nanoseconds>(
    	chrono::high_resolution_clock::now().
    	time_since_epoch()).count(),
    (uint64_t) __builtin_ia32_rdtsc(),
    (uint64_t) random_device{}(),
    (uint64_t) 17
};

mt19937 rng{seq};
template<class Ty> Ty randint(Ty a, Ty b) { return uniform_int_distribution<Ty>(a, b)(rng); }

// vector<ll> sssp(Gr const& g, int src = 0) {
// 	int const n = g.size();
// 	vector<ll> dist(n, inf<ll>);
// 	vector<char> vis(n);

// 	priority_queue<ii, vector<ii>, greater<ii>> pq;
// 	pq.push({0, src});
// 	dist[src] = 0;

// 	while (!pq.empty()) {
// 		auto [d, u] = pq.top();
// 		pq.pop();

// 		if (vis[u]) continue;
// 		vis[u] = 1;

// 		for (auto [v, w] : g[u]) {
// 			auto cost = d + w;

// 			if (cost < dist[v]) {
// 				dist[v] = cost;
// 				pq.emplace(cost, v);
// 			}
// 		}
// 	}
// 	return dist;
// }

vector<ll> sssp(Gr const& g, int src = 0) {
	int const n = g.size();
	vector<ll> dist(n, inf<ll>);

	deque<int> pq;
	pq.push_back(src);
	dist[src] = 0;

	while (!pq.empty()) {
		auto u = pq.front();
		pq.pop_front();

		for (auto [v, w] : g[u]) {
			auto cost = dist[u] + w;

			if (cost < dist[v]) {
				dist[v] = cost;

				if (pq.empty() or cost <= dist[pq.front()])
					pq.emplace_front(v);
				else
					pq.emplace_back(v);
			}
		}
	}
	return dist;
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(nullptr);

	int n, k, m;
	cin >> n >> k >> m;

	vector<int> cities(k);
	for (auto& i : cities) cin >> i;

	Gr g(n+1);
	for (int i = 0; i < m; i++) {
		int a, b, w;
		cin >> a >> b >> w;

		g[a].eb(b, w);
		g[b].eb(a, w);
	}

	if (k <= 2) {
		vector<vector<ll>> d;
		for (auto src : cities) d.push_back(sssp(g, src));

		ll ans = inf<ll>;

		for (int i = 1; i <= n; i++) {
			ll cost = d[0][i] + d[1][i] + (k == 3? d[2][i] : 0);

			ans = min(ans, cost);
		}

		cout << ans << "\n";
	}
	else {
		vector<int> perm(k);
		iota(all(perm), 0);

		ll ans = inf<ll>;

		vector<vector<ll>> d(k);
		for (int i = 0; i < k; i++) d[i] = sssp(g, cities[i]);

		do {
			if (k == 5) {
				if (perm[0] > perm[1] or perm[3] > perm[4] or perm[0] > perm[3]) continue;
			}
			if (k == 4) {
				if (perm[0] > perm[1]) continue;
			}
			
			vector<ll> ld = d[perm[0]];

			for (int i = 1; i < k-2; i++) {
				int at = perm[i];

				auto ng = g;
				for (int u = 1; u <= n; u++) ng[0].eb(u, ld[u] + d[at][u]);

				ld = sssp(ng);
			}

			for (int u = 1; u <= n; u++) {
				ll cost = ld[u] + d[perm[k-2]][u] + d[perm[k-1]][u];

				ans = min(ans, cost);
			}

		} while (next_permutation(all(perm)));

		cout << ans << "\n";
	}
}

Subtask #1
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 223 ms 16352 KB Output is correct
2 Correct 216 ms 16176 KB Output is correct
3 Correct 113 ms 10988 KB Output is correct
4 Correct 85 ms 9152 KB Output is correct
5 Correct 169 ms 14860 KB Output is correct
6 Correct 81 ms 9116 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 2 ms 460 KB Output is correct

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 588 KB Output is correct
2 Correct 4 ms 588 KB Output is correct
3 Correct 3 ms 460 KB Output is correct
4 Correct 3 ms 460 KB Output is correct

Subtask #4
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 918 ms 30856 KB Output is correct
2 Correct 727 ms 30124 KB Output is correct
3 Correct 956 ms 22632 KB Output is correct
4 Correct 554 ms 23300 KB Output is correct
5 Correct 205 ms 16532 KB Output is correct
6 Correct 147 ms 17736 KB Output is correct

Subtask #5
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2007 ms 33844 KB Output is correct
2 Correct 2139 ms 32604 KB Output is correct
3 Correct 1432 ms 32324 KB Output is correct
4 Correct 2357 ms 24252 KB Output is correct
5 Correct 1180 ms 23760 KB Output is correct
6 Correct 329 ms 16636 KB Output is correct
7 Correct 241 ms 17752 KB Output is correct