Submission #681665

#	Time	Username	Problem	Language	Result	Execution time	Memory
681665		DP_196	Relay Marathon (NOI20_relaymarathon)	C++14	17 / 100	1162 ms	123708 KiB

RelayMarathon

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
#define sz(x) (int)x.size()
#define MASK(i) ((1LL) << (i))
#define all(x) x.begin(), x.end()
#define BIT(x, i) ((x) >> (i) & (1LL))
#define dbg(...) cerr << "#" << __LINE__ << ":[" << #__VA_ARGS__ \
<< "] = [" ,DBG(__VA_ARGS__)

string to_string(const string& s) { return '"' + s + '"'; }
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
        cerr << to_string(h); if(sizeof...(t)) cerr << ", "; DBG(t...);
}

template <class T>
inline bool maximize(T &a, const T &b) { return (a < b ? (a = b) : 0); }
template <class T>
inline bool minimize(T &a, const T &b) { return (a > b ? (a = b) : 0); }

const int MAXN = 1e5 + 6;
const int INF = 1e9;
const int MOD = 1e9 + 7;

int n, m, k, a[505], cost[505][505], head[MAXN], dist[MAXN];
vector<ii> adj[MAXN];

struct dat {
	int v1 = INF, id1 = 0, v2 = INF, id2 = 0;
	dat (int _v1 = INF, int _id1 = 0, int _v2 = INF, int _id2 = 0) {
		v1 = _v1, id1 = _id1, v2 = _v2, id2 = _id2;
	} 
};

struct Edge {
	int u, v, w;
	Edge (int _u = 0, int _v = 0, int _w = 0) {
		u = _u, v = _v, w = _w;
	}
};

dat best[505];

void sub1() {
	
	memset(cost, 0x3f, sizeof (cost));
	
	for (int i = 1; i <= m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		minimize(cost[u][v], w);
		minimize(cost[v][u], w);
	}
	
	for (int i = 1; i <= k; i++) cin >> a[i];
	
	for (int k = 1; k <= n; k++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				minimize(cost[i][j], cost[i][k] + cost[k][j]);

	for (int i = 1; i <= k; i++) {
		for (int j = 1; j <= k; j++) {
			if (i == j) continue;
			int u = a[i], v = a[j];
			
			if (best[u].v1 >= cost[u][v]) {
				best[u] = dat(cost[u][v], v, best[u].v1, best[u].id1);
			}
			else if (cost[u][v] < best[u].v2) {
				best[u].v2 = cost[u][v];
				best[u].id2 = v;
			}
		}
	}
	
	int res = INF;
	for (int i = 1; i <= k; i++) {
		for (int j = 1; j <= k; j++) {
			if (i == j) continue;
			int u = a[i], v = a[j], sum = INF;
			if (best[u].id1 != v && best[u].id1 != best[v].id1 && best[v].id1 != u) {
				minimize(sum, best[u].v1 + best[v].v1);
			}
			
			if (best[u].id1 != v && best[u].id1 != best[v].id2 && best[v].id2 != u) {
				minimize(sum, best[u].v1 + best[v].v2);
			}
			
			if (best[u].id2 != v && best[u].id2 != best[v].id1 && best[v].id1 != u) {
				minimize(sum, best[u].v2 + best[v].v1);
			}
			
			if (best[u].id2 != v && best[u].id2 != best[v].id2 && best[v].id2 != u) {
				minimize(sum, best[u].v2 + best[v].v2);
			}
			
			minimize(res, sum);
		}
	}
	
	cout << res;
}

void sub2() {
	vector<Edge> g;
	for (int i = 1; i <= m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		adj[u].push_back(make_pair(w, v));
		adj[v].push_back(make_pair(w, u));
		g.push_back(Edge(u, v, w));
	}
	
	memset(dist, 0x3f, sizeof (dist));
	int res = dist[0];
	priority_queue<ii, vector<ii>, greater<ii>> pq;
	
	for (int i = 1, x; i <= k; i++) {
		cin >> x;
		pq.push(make_pair(0, x));
		head[x] = x;
		dist[x] = 0;
	}
	
	while (sz(pq)) {
		int du = pq.top().fi;
		int u = pq.top().se;
		pq.pop();
		
		for (auto v : adj[u]) {
			if (dist[v.se] > du + v.fi) {
				dist[v.se] = du + v.fi;
				head[v.se] = head[u];
				pq.push(make_pair(dist[v.se], v.se));
			}
		}
	}
	
	for (auto it : g) {
		if (head[it.u] != head[it.v]) {
			if (dist[it.u] + dist[it.v] + it.w > 1) {
				minimize(res, dist[it.u] + dist[it.v] + it.w);
			}
		}
	}
	
	cout << res + 1 << '\n';
}

void solve() {
	cin >> n >> m >> k;
	
	if (n <= 500) sub1();
	else sub2();
}

#define TASK "4SPECIAL"
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen(TASK".inp", "r", stdin);
    //freopen(TASK".out", "w", stdout);

    int ntest = 1;
    //cin >> ntest;
    while (ntest--) solve();

    return 0;
}
//612

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