Submission #678444

#	Time	Username	Problem	Language	Result	Execution time	Memory
678444		thanhdanh436	Relay Marathon (NOI20_relaymarathon)	C++17	5 / 100	34 ms	52108 KiB

RelayMarathon

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define getbit(x, i) (((x) >> (i)) & 1)
#define bit(x) (1 << (x))
#define file "4special"
using namespace std;

mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
long long rand(long long l, long long r) {
    return l + rd() % (r - l + 1);
}

const int N = 1e6 + 5;
const int mod = 1e9 + 7; // 998244353;
const int inf = INT_MAX;
const long long llinf = LLONG_MAX;
const int lg = 25; // lg + 1

template<class T> bool minimize(T &a, T b) { 
	return a > b ? (a = b, true) : false; 
}
template<class T> bool maximize(T &a, T b) { 
	return a < b ? (a = b, true) : false; 
}
template<class T> bool add(T &a, T b) { 
	a += b; 
	while (a > mod) a -= mod; 
	return true; 
}

int n, m, k;
int g[505][505];
vector<pair<int, int> > adj[N];
int id[N];
bool special[N];

namespace sub1 {
	void floyd(void) {
		for (int k = 1; k <= n; ++k) for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) {
			minimize(g[i][j], g[i][k] + g[k][j]);
		}
	}
	void solve(void) {
		floyd();
		int ans = g[0][0];
		for (int a = 1; a <= k; ++a)
		for (int b = 1; b <= k; ++b)
		for (int c = 1; c <= k; ++c)
		for (int d = 1; d <= k; ++d) {
			if (a == b || a == c || a == d || b == c || b == d || c == d) continue;
			int x = id[a], y = id[b], z = id[c], t = id[d];
			if (g[x][y] + g[z][t] < ans && g[x][y] != g[0][0] && g[z][t] != g[0][0]) 
				minimize(ans, g[x][y] + g[z][t]);
		}
		cout << ans;
	}	
}

namespace full {
	int d[N], from[N];
	typedef pair<int, int> node;
	pair<int, pair<int, int> > dijkstra_special(void) { // from special to another
		memset(d, 0x3f, sizeof d);
		memset(from, 0, sizeof from);
		priority_queue<node, vector<node>, greater<node> > q;
		for (int i = 1; i <= n; ++i) {
			if (special[i]) {
				q.push({0, i});
				from[i] = i;
				d[i] = 0;
			}
		}
		while (q.size()) {
			int u = q.top().se; q.pop();
			for (auto i : adj[u]) {
				int v = i.fi, l = i.se;
				if (d[u] + l < d[v]) {
					d[v] = d[u] + l;
					from[v] = from[u];
					q.push({d[v], v});
				}
			}
		}
		int ans = d[0], s = 1, t = 1;
		for (int u = 1; u <= n; ++u) {
			for (auto [v, w] : adj[u]) if (from[u] != from[v]) {
				if (minimize(ans, d[u] + d[v] + w)) s = u, t = v;
			}
		}
		return {ans, {s, t}};
	}	
	pair<int, int> dijstra(int s) { // shortest path from source
		memset(d, 0x3f, sizeof d);
		priority_queue<node, vector<node>, greater<node> > q;
		q.push({0, s});
		d[s] = 0;
		while (q.size()) {
			int u = q.top().se; q.pop();
			if (special[u]) return {d[u], u};
			for (auto i : adj[u]) {
				int v = i.fi, l = i.se;
				if (d[u] + l < d[v]) {
					d[v] = d[u] + l;
					q.push({d[v], v});
				}
			}
		}
		return {inf, 0};
	}
	void solve(void) {
		int dis1, dis2, s1, t1, s2, t2;
		// int ans = inf;
		auto ans1 = dijkstra_special();
		dis1 = ans1.fi, s1 = ans1.se.fi, t1 = ans1.se.se;
		special[s1] = special[t1] = false;
		auto ans2 = dijkstra_special();
		dis2 = ans2.fi, s2 = ans2.se.fi, t2 = ans2.se.se;
		cout << dis1 + dis2;
	}
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	// freopen(file".inp", "r",stdin);
	// freopen(file".out", "w",stdout);

	cin >> n >> m >> k;
	memset(g, 0x3f, sizeof g);
	for (int i = 1; i <= m; ++i) {
		int u, v, c;
		cin >> u >> v >> c;
		adj[u].push_back({v, c});
		adj[v].push_back({u, c});
		g[u][v] = c;
		g[v][u] = c;
	}

	for (int i = 1; i <= k; ++i) {
		int x;
		cin >> x;
		id[i] = x;
		special[x] = true;
	}

	if (n <= 50) {
		sub1::solve();
		return 0;
	}

	full::solve();

	return 0;
}

Compilation message (stderr)

RelayMarathon.cpp: In function 'void full::solve()':
RelayMarathon.cpp:114:27: warning: variable 's2' set but not used [-Wunused-but-set-variable]
  114 |   int dis1, dis2, s1, t1, s2, t2;
      |                           ^~
RelayMarathon.cpp:114:31: warning: variable 't2' set but not used [-Wunused-but-set-variable]
  114 |   int dis1, dis2, s1, t1, s2, t2;
      |                               ^~

• Subtask 1: 5 / 5
• Subtask 2: 0 / 12
• Subtask 3: 0 / 25
• Subtask 4: 0 / 58